codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1575A.md (1695B)


      1 Source: https://codeforces.com/problemset/problem/1575/A
      2 
      3 A. Another Sorting Problem
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 512 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 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.
     22 
     23 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.
     24 
     25 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:
     26 
     27 * if it is an odd position, the string $a$ has a letter that appears earlier in the alphabet than the corresponding letter in $b$;
     28 * if it is an even position, the string $a$ has a letter that appears later in the alphabet than the corresponding letter in $b$.
     29 
     30 Input
     31 
     32 The first line contains two integers $n$ and $m$ ($1 \leq n \cdot m \leq 10^6$).
     33 
     34 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.
     35 
     36 Output
     37 
     38 Output $n$ integers — the indices of the strings after they are sorted asc-desc-endingly.
     39 
     40 Example
     41 
     42 Input
     43 
     44 ```
     45 5 2
     46 AA
     47 AB
     48 BB
     49 BA
     50 AZ
     51 ```
     52 
     53 Output
     54 
     55 ```
     56 5 2 1 3 4
     57 ```
     58 
     59 Note
     60 
     61 The following illustrates the first example.
     62 
     63  ![](https://espresso.codeforces.com/fdb08c6639d17941c538ade36ceffd0bb810320d.png)