Overview

This is a problem where you rank players in descending order of their overall rating \(A_i+B_i\) (breaking ties by smaller jersey number first), then output the jersey numbers of the top \(K\) players in ascending order.

Analysis

The ranking rule can be directly handled as a “sort with two keys.”

• First, compute the overall rating \(S_i = A_i + B_i\).
• The ranking is determined by:
  1. Higher \(S_i\) ranks higher
  2. If \(S_i\) is the same, smaller jersey number \(i\) ranks higher

So sorting by “(\(S_i\) descending, \(i\) ascending)” uniquely determines the ranking.

A naive approach of “finding the top players one by one (scanning for the maximum each time)” would result in \(O(NK)\) for \(K\) searches, which can be close to \((2\times10^5)^2\) at maximum and won’t be fast enough. Instead, sorting all players just once to determine the rankings is sufficient, running in \(O(N\log N)\) which is fast enough.

Finally, the required output is “the jersey numbers of the selected \(K\) players in ascending order,” so after extracting the top \(K\) players, we sort their jersey numbers in ascending order once more.

Algorithm

1. Read the input and compute the overall rating \(S_i=A_i+B_i\) for each player \(i\).
2. Store each player as a tuple (-S_i, i) in an array.
   • Since Python’s sort() sorts in ascending order, using -S_i achieves “descending order of overall rating.”
   • In case of ties, the second element of the tuple i (jersey number) with the smaller value comes first, satisfying the condition.
3. Sort the array and extract the jersey numbers from the first \(K\) elements (these are ranks \(1\) through \(K\)).
4. Sort the extracted jersey numbers in ascending order and output them one per line.

(Example) If the overall ratings are [10 (jersey #2), 10 (jersey #5), 9 (jersey #1)], then among tied players, jersey #2 ranks higher than #5 since 2 is smaller — this behavior is naturally achieved by tuple sorting.

Complexity

• Time complexity: \(O(N\log N)\) (overall sort) + \(O(K\log K)\) (sorting jersey numbers after selection)
• Space complexity: \(O(N)\) (array of player information)

Implementation Notes

• By using the sort key (- (A_i+B_i), i), “descending order of overall rating, ascending order of jersey number” is expressed in a single sort.

• Since the input size can be large, using sys.stdin.buffer.read() to read all at once is faster.

• The output must be “in ascending order of jersey number,” so after selecting the top \(K\) players, an additional selected_ids.sort() is needed.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, K = data[0], data[1]
    players = []
    idx = 2
    for i in range(1, N + 1):
        a = data[idx]
        b = data[idx + 1]
        idx += 2
        players.append((-(a + b), i))  # sort by score desc, id asc

    players.sort()
    selected_ids = [pid for _, pid in players[:K]]
    selected_ids.sort()

    sys.stdout.write("\n".join(map(str, selected_ids)))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.