Overview

This is a problem where you rank each player by their overall evaluation (the sum of their practice evaluation score and match evaluation score), and output the jersey numbers of the top K players in ascending order.

Analysis

To rank players according to the problem’s rules, we first need to calculate each player’s overall evaluation (\(A_i + B_i\)). When overall evaluations are the same, the player with the smaller jersey number ranks higher. As a straightforward approach, we can calculate the overall evaluation for all players and sort them according to the rules to easily determine the top K players. Since the constraint is \(N \leq 2 \times 10^5\), using an efficient sorting algorithm (\(O(N \log N)\)) is sufficiently fast.

Algorithm

1. For each player, calculate their overall evaluation (\(A_i + B_i\)).
2. Sort the players according to the ranking rules. Specifically, sort in descending order of overall evaluation (highest first), and when overall evaluations are the same, sort in ascending order of jersey number (smallest first).
3. Retrieve the jersey numbers of the top K players after sorting.
4. Sort the retrieved jersey numbers in ascending order (smallest first) and output them.

Complexity

• Time complexity: \(O(N \log N)\)
  • Computing the overall evaluations takes \(O(N)\), sorting the players takes \(O(N \log N)\), and sorting the jersey numbers takes \(O(K \log K)\) (where \(K \leq N\)), but overall \(O(N \log N)\) is dominant.
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used for the array storing the player information.

Implementation Notes

• When sorting, you need to specify descending order for overall evaluation and ascending order for jersey number simultaneously. In Python, you can use tuples like (-total, number) so that overall evaluation is sorted in descending order while jersey number is sorted in ascending order.

• Since the final output requires jersey numbers in ascending order, the jersey numbers of the top K players need to be sorted again.

  Source Code

def main():
    import sys
    data = sys.stdin.read().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])
        index += 2
        total = a + b
        players.append((total, i+1))
    
    players.sort(key=lambda x: (-x[0], x[1]))
    
    result = []
    for i in range(k):
        result.append(players[i][1])
    
    result.sort()
    for num in result:
        print(num)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.