Overview

This is a problem where you sort participants based on three criteria — “score earned,” “rating,” and “participant number” — with a defined priority order, and produce a standings table.

Analysis

In this problem, you need to sort based on multiple conditions.

Organizing the Problem

Listing the three rules for determining rank in order of priority: 1. Higher score \(B_i\) → higher rank 2. Higher rating \(A_i\) → higher rank (when scores are the same) 3. Smaller participant number \(i\) → higher rank (when both score and rating are the same)

Thinking Through a Concrete Example

For example, suppose we have the following three participants: - Participant 1: Rating=100, Score=200 - Participant 2: Rating=150, Score=200 - Participant 3: Rating=100, Score=300

In this case: - Participant 3 has the highest score of 300, so they are 1st place - Participants 1 and 2 have the same score of 200, so we compare by rating - Participant 2 has rating 150 > Participant 1’s rating 100, so they are 2nd place - Participant 1 is 3rd place

Comparison with a Naive Approach

Since this problem can be solved with straightforward sorting, there are no particular pitfalls that would easily lead to TLE or WA. However, it is important to set the sorting conditions correctly.

Algorithm

We use Python’s sort() function to perform sorting with composite keys.

Designing the Sort Key

Python’s sort() sorts in ascending order (smallest first) by default. However, in this problem: - \(B\) (score): descending order → use -B - \(A\) (rating): descending order → use -A - \(i\) (participant number): ascending order → use i as is

Therefore, by setting the sort key to (-B, -A, i), we can obtain the correct ranking with a single sort.

Processing Flow

1. Read the input and store each participant’s information as a tuple (number, rating, score) in a list
2. Sort using the sort key (-score, -rating, number)
3. Output the participant numbers in order from the sorted list

Complexity

• Time complexity: \(O(N \log N)\)
  • Due to sorting \(N\) participants
• Space complexity: \(O(N)\)
  • Required for the list storing participant information

Implementation Notes

1. Participant numbers start from 1: Use for i in range(1, N + 1) to manage numbers with 1-indexed numbering.

2. Pay attention to the sign of sort keys: Attach - (minus) to items you want in “descending order.” This achieves a descending effect even with ascending sort.

3. Comparison order of tuples: Python tuples are compared element by element from left to right, so specifying the order as (-B, -A, i) sorts exactly according to the priority described in the problem statement.

4. Fast input: Since \(N\) can be as large as \(2 \times 10^5\), we use sys.stdin.readline to speed up input reading.

   Source Code

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    participants = []
    for i in range(1, N + 1):
        A, B = map(int, input().split())
        participants.append((i, A, B))
    
    # ソートキー: (-B, -A, i) で昇順ソート
    # Bが大きい順 → Aが大きい順 → 番号が小さい順
    participants.sort(key=lambda x: (-x[2], -x[1], x[0]))
    
    for p in participants:
        print(p[0])

if __name__ == "__main__":
    main()

---

This editorial was generated by claude4.5opus.