Another Sorting Problem (Codeforces 1575A)
Tags: Others, strings

Andi and Budi were given an assignment to tidy up their bookshelf of $$$n$$$ books. Each book is represented by the book title — a string $$$s_i$$$ numbered from $$$1$$$ to $$$n$$$, each with length $$$m$$$. Andi really wants to sort the book lexicographically ascending, while Budi wants to sort it lexicographically descending.Settling their fight, they decided to combine their idea and sort it asc-desc-endingly, where the odd-indexed characters will be compared ascendingly, and the even-indexed characters will be compared descendingly.A string $$$a$$$ occurs before a string $$$b$$$ in asc-desc-ending order if and only if in the first position where $$$a$$$ and $$$b$$$ differ, the following holds:  if it is an odd position, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$;  if it is an even position, the string $$$a$$$ has a letter that appears later in the alphabet than the corresponding letter in $$$b$$$. 

Input: The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \cdot m \leq 10^6$$$).The $$$i$$$-th of the next $$$n$$$ lines contains a string $$$s_i$$$ consisting of $$$m$$$ uppercase Latin letters — the book title. The strings are pairwise distinct.

Output: Output $$$n$$$ integers — the indices of the strings after they are sorted asc-desc-endingly.

Note: The following illustrates the first example.  

Sample Inputs:
5 2
AA
AB
BB
BA
AZ

Sample Outputs:
5 2 1 3 4

Solution (Python):
def solution(ins):
    lines = ins.split('\n')
    (n, m) = map(int, lines[0].split())
    strs = []
    for i in range(1, n + 1):
        s = lines[i]
        flipped_s = ''
        for j in range(m):
            c = s[j]
            if j % 2 == 1:
                c = chr(25 - (ord(c) - ord('A')) + ord('A'))
            flipped_s += c
        strs.append((flipped_s, i))
    strs = sorted(strs)
    return ' '.join([str(s[1]) for s in strs])
if __name__ == '__main__':
    import sys
    all_stdin = sys.stdin.read()
    print(solution(all_stdin))

Solution (Python):
def solution(stdin: str) -> str:
    lines = stdin.splitlines()
    strings = lines[1:]
    temp = {}
    for (idx, s) in enumerate(strings):
        key = []
        for (i, c) in enumerate(s):
            if i % 2 == 0:
                key.append(c)
            else:
                key.append(chr(ord('Z') - ord(c) + ord('A')))
        key = ''.join(key)
        if key in temp:
            temp[key].append(idx)
        else:
            temp[key] = [idx]
    result = []
    for key in sorted(temp.keys()):
        for idx in temp[key]:
            result.append(idx + 1)
    return ' '.join(map(str, result))
import sys
data = sys.stdin.read()
print(solution(data))

Solution (Python):
def solution(stdin: str) -> str:
    lines = stdin.splitlines()
    strings = lines[1:]
    temp = {}
    for (idx, s) in enumerate(strings):
        key = []
        for (i, c) in enumerate(s):
            if i % 2 == 0:
                key.append(c)
            else:
                key.append(chr(ord('Z') - ord(c) + ord('A')))
        key = ''.join(key)
        if key in temp:
            temp[key].append(idx)
        else:
            temp[key] = [idx]
    result = []
    for key in sorted(temp.keys()):
        for idx in temp[key]:
            result.append(idx + 1)
    return ' '.join(map(str, result))
import sys
data = sys.stdin.read()
print(solution(data))