Overview

For each of the \(N\) players, compute the overall rating \(A_i + B_i\), then rank them in descending order of overall rating (with ties broken by ascending jersey number). Output the jersey numbers of the top \(K\) players in ascending order.

Analysis

The key points for this problem are as follows:

Setting the sort criteria correctly

Ranking is determined by two levels of criteria: 1. Higher overall rating ranks higher (descending order) 2. If overall ratings are equal, smaller jersey number ranks higher (ascending order)

For example, suppose there are 3 players with \((A_i + B_i, \text{jersey number})\) as follows:

Jersey Number	Overall Rating
1	10
2	15
3	10

In this case, the ranking is: “Player 2 (rating 15) → Player 1 (rating 10, smaller jersey number) → Player 3 (rating 10, larger jersey number)”.

Sort key trick

Python’s sort() sorts in ascending order by default. Since we want overall ratings in descending order, a useful technique is to use the negated overall rating as the sort key.

Represent each player as the tuple \((-(A_i + B_i),\ i)\): - First element: negated overall rating → sorting in ascending order places players with higher overall ratings first - Second element: jersey number → when the first elements are equal, players with smaller jersey numbers come first

This allows Python’s default tuple comparison to sort in the correct ranking order.

A straightforward approach is sufficient

Since \(N \leq 2 \times 10^5\), an \(O(N \log N)\) sort is fast enough. No special data structures are needed.

Algorithm

1. For each of the \(N\) players, create the tuple \((-(A_i + B_i),\ i)\).
2. Sort this list of tuples in ascending order.
3. The first \(K\) elements after sorting correspond to the top \(K\) players, so extract their jersey numbers.
4. Sort the extracted \(K\) jersey numbers in ascending order and output them.

Complexity

• Time complexity: \(O(N \log N)\)
  • Sorting all players takes \(O(N \log N)\), and sorting the jersey numbers of the top \(K\) players takes \(O(K \log K)\). Overall, this is \(O(N \log N)\).
• Space complexity: \(O(N)\)
  • The list storing tuples for all players requires \(O(N)\).

Implementation Notes

• Reversing sort order using negation: In Python, you could also use sort(reverse=True), but when you want only the first element in descending order while keeping the second element in ascending order, the technique of negating the first element is concise and convenient.

• Fast input: Since \(N\) can be as large as \(2 \times 10^5\), using sys.stdin.buffer.read() to read all input at once speeds up input processing.

• Pay attention to the output order: After selecting the top \(K\) players, remember that the final output must be in “ascending order of jersey number.” This is different from the sort order used during selection (overall rating order).

  Source Code

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    
    players = []
    for i in range(1, N + 1):
        A = int(input_data[idx]); idx += 1
        B = int(input_data[idx]); idx += 1
        players.append((-(A + B), i))
    
    players.sort()
    
    selected = sorted(players[j][1] for j in range(K))
    
    print('\n'.join(map(str, selected)))

main()

---

This editorial was generated by claude4.6opus-thinking.