Overview

This is a problem where you select \(K\) players from \(N\) players in order of highest overall rating (\(A_i + B_i\)), with ties broken by smallest jersey number, and output the jersey numbers of the selected players in ascending order.

Approach

This problem can be solved by sorting the players according to the instructions in the problem statement and selecting the top \(K\) players.

The rules for determining rankings are as follows: 1. In descending order of overall rating (\(A_i + B_i\)) 2. If overall ratings are equal, in ascending order of jersey number \(i\)

Standard sorting functions in programming languages (such as Python’s sort()) sort data with multiple elements (tuples or arrays) by comparing the first element, and if they are equal, comparing the second element, and so on, all in ascending order.

However, in this problem’s rules, “overall rating is in descending order” while “jersey number is in ascending order” — the sorting directions differ. Implementing this directly would require the overhead of defining a custom comparison function.

A useful technique here is to multiply the overall rating by minus (\(-1\)) for comparison. For example, if the overall ratings are \(100\) and \(80\), multiplying by minus gives \(-100\) and \(-80\). Sorting these in ascending order (smallest first) gives \(-100, -80\), which produces the same result as sorting the original overall ratings in descending order (largest first).

Therefore, by creating a pair (tuple) of (-overall_rating, jersey_number) for each player and simply sorting these in ascending order, the ranking is completed exactly according to the problem’s conditions.

Algorithm

1. Prepare an empty list to store player data.
2. For each player \(i \ (1 \leq i \leq N)\), calculate the overall rating \(S_i = A_i + B_i\).
3. Add the tuple (-S_i, i) to the list.
4. Sort the list in ascending order. This arranges players in descending order of overall rating, with ties broken by ascending jersey number.
5. Extract the jersey numbers of the first \(K\) players from the sorted list and store them in a new list.
6. To output the jersey numbers of the selected \(K\) players in ascending order, sort the extracted list in ascending order.
7. Output the sorted jersey numbers, one per line.

Complexity

• Time complexity: \(O(N \log N)\)
  • Creating the player list takes \(O(N)\)
  • Sorting the \(N\) players takes \(O(N \log N)\)
  • Sorting the jersey numbers of the selected \(K\) players takes \(O(K \log K)\)
  • The heaviest operation overall is sorting the \(N\) players, so the total is \(O(N \log N)\). This runs sufficiently fast for the constraint \(N \leq 2 \times 10^5\).
• Space complexity: \(O(N)\)
  • \(O(N)\) space is used for the list holding the data of \(N\) players and for storing the input data.

Implementation Notes

• Fast input: Since \(N\) can be as large as \(2 \times 10^5\), using sys.stdin.read().split() in Python to read all input at once can significantly improve execution speed.

• Sorting trick: As described above, by creating tuples of (-overall_rating, jersey_number), Python’s built-in sort() method can be used directly, making the code both simple and fast.

• Fast output: Using print('\n'.join(...)) reduces the overhead of calling the print function multiple times, speeding up the output.

  Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    K = int(input_data[1])
    
    players = []
    it = iter(input_data[2:])
    for i in range(1, N + 1):
        score = int(next(it)) + int(next(it))
        players.append((-score, i))
        
    players.sort()
    
    selected = [players[i][1] for i in range(K)]
    selected.sort()
    
    print('\n'.join(map(str, selected)))

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3.1-pro-thinking.