Overview

This is a problem where you sort each participant by the priority order “highest score first → highest rating first → smallest number first” and output the participant numbers from top to bottom.

Analysis

The way rankings are determined is exactly “sorting by multiple keys.” In other words, we need to compare each participant \(i\) by the following priorities:

1. Higher \(B_i\) ranks above (descending order)
2. If \(B_i\) is the same, higher \(A_i\) ranks above (descending order)
3. If both \(B_i\) and \(A_i\) are the same, smaller number \(i\) ranks above (ascending order)

Here, if we naively “determine the ranking from 1st place onward” by searching through all remaining participants each time to find the maximum, repeating this \(N\) times results in \(O(N^2)\). Since \(N \le 2 \times 10^5\), \(O(N^2)\) is too slow (causes TLE).

This problem can be solved by sorting all at once, and sorting runs in \(O(N \log N)\), which is fast enough.

※ The constraint \(B_i \ge A_i\) only guarantees the consistency of the input and requires no special handling for the ranking process itself.

Algorithm

1. For each participant \(i\), create a comparison key and store it in an array.
2. Sort that array.
3. Output participant numbers in the sorted order.

Python’s sort() performs “ascending sort,” so for items we want in descending order (\(B_i\), \(A_i\)), we negate their signs to form (-B_i, -A_i, i).

• Example: Suppose there are the following 3 participants
  • 1: \((A,B)=(100,200)\) → key \((-200,-100,1)\)
  • 2: \((A,B)=(150,200)\) → key \((-200,-150,2)\) (if tied at score 200, rating 150 ranks higher)
  • 3: \((A,B)=(120,180)\) → key \((-180,-120,3)\) Sorting these in ascending order gives the order 2 → 1 → 3, which matches the required ranking.

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting)
• Space complexity: \(O(N)\) (array for participant information)

Implementation Notes

• Use the sort key ( -B, -A, i ) so that “ascending sort = highest rank first.”

• Since \(N\) can be large, use sys.stdin.readline for fast input.

• Outputting with "\n".join(...) all at once is also faster.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    people = []
    for i in range(1, N + 1):
        a, b = map(int, input().split())
        people.append((-b, -a, i))
    people.sort()
    out = "\n".join(str(p[2]) for p in people)
    sys.stdout.write(out)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.