Overview

This problem requires determining rankings based on participants’ scores and ratings according to specified rules, and outputting participant numbers in order from the highest rank.

Analysis

The ranking rules in this problem are the following three: 1. A higher score \(B_i\) means a higher rank 2. If scores are the same, a higher rating \(A_i\) means a higher rank 3. If both score and rating are the same, a smaller participant number means a higher rank

We can obtain the correct order by simply comparing and sorting each participant’s data. However, we need to consider multiple keys simultaneously when sorting.

Algorithm

1. Store each participant’s data as a tuple \((B_i, A_i, i+1)\) in a list
2. Sort with the following sort keys in descending/ascending order:
   • First key: Score \(B_i\) (descending: -x[0])
   • Second key: Rating \(A_i\) (descending: -x[1])
   • Third key: Participant number (ascending: x[2])
3. Output the participant numbers from the sorted list in order

Complexity

• Time complexity: \(O(N \log N)\)
  • The sorting algorithm’s complexity is dominant
• Space complexity: \(O(N)\)
  • A list is needed to store participant data

Implementation Notes

• Python’s sorted function and list.sort() method can easily implement sorting with multiple keys

• For keys that need descending order, using negative values (-x[0]) allows expressing descending order through ascending sort

• For reading input data, reading all data at once is an efficient approach

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    participants = []
    index = 1
    for i in range(n):
        a = int(data[index])
        b = int(data[index+1])
        index += 2
        participants.append((b, a, i+1))
    
    participants.sort(key=lambda x: (-x[0], -x[1], x[2]))
    
    for p in participants:
        print(p[2])

if __name__ == "__main__":
    main()

---

This editorial was generated by deepseekv3.