Overview

This is a problem where you calculate each player’s final score as the sum of judges’ scores excluding the highest and lowest scores, and find the player with the highest score (in case of a tie, the one with the smaller number).

Analysis

If we straightforwardly implement the problem’s requirements, the following processing is needed for each player: 1. Find the highest and lowest scores among the judges’ scores 2. Exclude them and calculate the sum of the remaining scores

However, since scores are at most 100 (a small value) and the input size satisfies \(N \times M \leq 10^6\), sorting each player’s score list is sufficiently efficient. By sorting, the minimum and maximum values are placed at both ends, making them easy to exclude.

Algorithm

1. For each player \(i\) (\(1 \leq i \leq N\)):
   • Receive \(M\) scores
   • Sort the score list in ascending order
   • Calculate the sum of the sorted list excluding the first element (minimum) and the last element (maximum)
2. Compare the final scores of all players and record the player with the maximum score (in case of a tie, prioritize the player with the smaller number)

Complexity

• Time complexity: \(O(N \times M \log M)\)
  • Sorting each player’s score list takes \(O(M \log M)\), and this is done \(N\) times
  • However, given the constraint \(N \times M \leq 10^6\), even in the worst case it is approximately \(10^6 \log 10^6 \approx 2 \times 10^7\), which is fast enough
• Space complexity: \(O(N \times M)\)
  • Memory for storing the input data

Implementation Notes

• Efficiency can be improved by reading all input data at once

• After sorting, the minimum and maximum can be easily excluded using scores[1:-1]

• Don’t forget to implement the tie-breaking logic (only update if the player’s number is smaller than the current highest scorer)

• Note that player numbers are 1-indexed (since the code processes them as 0-indexed, add +1)

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    n = int(data[0])
    m = int(data[1])
    index = 2
    
    max_score = -1
    best_player = -1
    
    for player in range(n):
        scores = list(map(int, data[index:index+m]))
        index += m
        
        scores.sort()
        total = sum(scores[1:-1])
        
        if total > max_score:
            max_score = total
            best_player = player + 1
        elif total == max_score:
            if player + 1 < best_player:
                best_player = player + 1
                
    print(best_player)

if __name__ == "__main__":
    main()

---

This editorial was generated by deepseekv3.