Overview

This problem asks us to determine, for each round, whether some player’s score is at least twice the highest score among all other players, and to count the number of such rounds.

Analysis

From the problem definition, to determine whether a standout player exists in each round, we need the following two pieces of information: 1. The highest score in that round 2. The highest score excluding the player with the highest score (the second-highest score)

This is because the condition for being a standout is “highest score ≥ 2 × (second-highest score)”. The data size for each round is the number of players N, and given the constraint N×T ≤ 10^6, it is efficient enough to find the highest and second-highest scores by linear search for each round.

Algorithm

1. For each round, receive the list of scores
2. Find the highest score (max1) and the second-highest score (max2) for that round
   • When updating the highest score, move the previous highest score to the second-highest score
   • When a score is less than or equal to the highest score but greater than the second-highest score, update the second-highest score
3. Check whether the condition “max1 ≥ 2 × max2” is satisfied
   • If satisfied, a standout player exists in that round, so increment the count
4. After processing all rounds, output the count

Complexity

• Time complexity: \(O(N \times T)\)
  • Since we perform \(O(N)\) processing for each round, the total is \(O(N \times T)\)
  • This is sufficiently fast given the constraint \(N \times T \leq 10^6\)
• Space complexity: \(O(N \times T)\)
  • Space for holding the input data (up to \(10^6\) elements given the problem constraints)

Implementation Notes

• In processing each round, track the highest and second-highest scores simultaneously

• To handle the case where a second-highest score does not exist (when all players have the same score), initialize max2 to -1 and treat it as 0 during the condition check

• Efficiency is improved by reading the input data all at once

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print(0)
        return
        
    n = int(data[0])
    t = int(data[1])
    index = 2
    count = 0
    
    for _ in range(t):
        round_scores = list(map(int, data[index:index+n]))
        index += n
        
        max1 = -1
        max2 = -1
        max_index = -1
        
        for i, score in enumerate(round_scores):
            if score > max1:
                max2 = max1
                max1 = score
                max_index = i
            elif score > max2:
                max2 = score
        
        if max2 == -1:
            max2 = 0
        
        if max1 >= 2 * max2:
            count += 1
            
    print(count)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.