Overview

A problem where you rank players based on their overall rating and jersey number, select the top \(K\) players, and output their jersey numbers in ascending order.

Analysis

In this problem, we need to calculate each player’s “overall rating” as \(A_i + B_i\) and rank them accordingly. However, when multiple players have the same overall rating, the one with the smaller jersey number ranks higher. This relates to how we define sorting priorities: we need to sort by “primary key: overall rating (descending)” and “secondary key: jersey number (ascending).”

A straightforward approach would be to calculate the overall rating for all players, determine their rankings, and select the top \(K\) players. However, if we naively sort using list operations each time, it could become \(O(N^2)\) in the worst case, which may not finish in time given the constraint \(N \leq 2 \times 10^5\).

By using Python’s built-in sort (Timsort), we can perform the sorting efficiently. This sort is stable and fast, and by specifying the appropriate key, we can achieve the desired ordering.

Furthermore, since we need to output the jersey numbers of the selected top \(K\) players in ascending order, we need to sort the selected players by jersey number once more.

Algorithm

1. Calculate each player’s overall rating \(A_i + B_i\) and store it along with the jersey number as a tuple \((\text{overall rating}, \text{jersey number})\) in a list.
2. Sort the list as follows:
   • Primary key: overall rating (descending)
   • Secondary key: jersey number (ascending)
3. Extract the first \(K\) entries from the sorted list.
4. Re-sort the jersey numbers of the extracted \(K\) players in ascending order.
5. Output the jersey numbers in order.

Example

Given the following input:

5 3
80 90
70 80
90 80
80 80
90 90

Each player’s overall rating is: - Player 1: \(80 + 90 = 170\) - Player 2: \(70 + 80 = 150\) - Player 3: \(90 + 80 = 170\) - Player 4: \(80 + 80 = 160\) - Player 5: \(90 + 90 = 180\)

The list of \((\text{overall rating}, \text{jersey number})\) is: $\( [(170, 1), (150, 2), (170, 3), (160, 4), (180, 5)] \)$

After sorting: $\( [(180, 5), (170, 1), (170, 3), (160, 4), (150, 2)] \)$

The top 3 players have jersey numbers 5, 1, 3. Arranging these by jersey number: $\( [1, 3, 5] \)$

Output:

1
3
5

Complexity

• Time complexity: \(O(N \log N)\)
  (dominated by the list sorting)
• Space complexity: \(O(N)\)
  (list storing player information)

Implementation Notes

• Use tuples to enable sorting by multiple keys.

• By setting the sort key to (-overall_rating, jersey_number), we can express descending and ascending order simultaneously.

• Don’t forget to re-sort by jersey number for the final output after selecting the top \(K\) players.

  Source Code

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    K = int(data[1])
    
    players = []
    index = 2
    for i in range(N):
        A = int(data[index])
        B = int(data[index+1])
        total = A + B
        players.append((total, i+1))  # (総合評価, 背番号)
        index += 2
    
    # 総合評価の降順、背番号の昇順でソート
    players.sort(key=lambda x: (-x[0], x[1]))
    
    # 上位K人を取得し、背番号で再ソート
    selected = players[:K]
    selected.sort(key=lambda x: x[1])
    
    for _, num in selected:
        print(num)

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.