Overview

In this problem, among \(N\) participants, we identify the finalists whose total score is at least \(K\), assign seed numbers (\(1, 2, \dots\)) to them according to the specified priority rules, and output each participant’s seed number (or \(-1\) if they did not advance) in their original index order.

Analysis

Naive Approach and Its Issues

One could consider counting, for each finalist, how many participants have a higher priority by comparing them with everyone else. However, this approach takes \(O(N)\) time per finalist, resulting in an overall time complexity of \(O(N^2)\). Since \(N \le 10^5\) in this problem, the number of operations would be around \(10^{10}\), leading to a Time Limit Exceeded (TLE).

Efficient Approach

To rank the finalists efficiently, we use sorting.

The condition for advancing to the finals is \(A_i + B_i \ge K\). After filtering out only the participants who satisfy this condition, we sort them according to the following priority rules: 1. Higher total score first (descending order) 2. In case of a tie in total score, smaller participant index first (ascending order)

When using Python’s standard sort (ascending order), it is effective to store the negated total score (\(- (A_i + B_i)\)) and the participant index \(i\) as a pair (-score, i) in a list. This way, the elements are sorted by the first value (\(-score\)) in ascending order (which corresponds to descending order of the original score), and ties are automatically broken by the second value (the participant index) in ascending order.

After sorting, we assign seed numbers \(1, 2, \dots\) starting from the first element. Since the output must be in the original participant index order (from \(1\) to \(N\)), we can easily satisfy the output format by preparing an array of length \(N\) initialized with \(-1\), and writing the assigned seed number at the corresponding participant’s position.

Algorithm

1. Initialize an answer array ans of length \(N\), with all elements set to \(-1\).
2. For each participant \(i\) (\(0 \le i < N\), 0-indexed), do the following:
   • Compute the total score \(S_i = A_i + B_i\).
   • If \(S_i \ge K\), append the tuple (-S_i, i) to the list.
3. Sort the list in ascending order.
4. Iterate through the sorted list from the beginning and store the rank (\(1, 2, \dots\)) at the corresponding participant’s position ans[i].
5. Output the elements of ans in order, separated by newlines.

Complexity

• Time Complexity: \(O(N \log N)\)
  • Filtering the finalists takes \(O(N)\).
  • Letting \(M\) (\(M \le N\)) be the number of finalists, sorting takes \(O(M \log M) \le O(N \log N)\).
  • Populating the result array and printing the output takes \(O(N)\).
  • Overall, it takes \(O(N \log N)\) time, which easily runs well within the time limit even for \(N = 10^5\).
• Space Complexity: \(O(N)\)
  • \(O(N)\) memory is used for the list of finalists and the result array ans.

Implementation Notes

• Concise Implementation of Multi-key Sorting: A sort order like “descending by one value, ascending by another” can be concisely achieved in a single sort operation by negating the value to be sorted in descending order and performing an ascending sort.

• Fast I/O: Since \(N\) can be as large as \(10^5\), in Python, reading the entire input at once using sys.stdin.read().split() and printing all output at once using sys.stdout.write('\n'.join(...)) can significantly reduce the execution time.

  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])
    
    qualifiers = []
    idx = 2
    for i in range(N):
        a = int(input_data[idx])
        b = int(input_data[idx+1])
        idx += 2
        s = a + b
        if s >= K:
            qualifiers.append((-s, i))
            
    qualifiers.sort()
    
    ans = [-1] * N
    for seed, (_, i) in enumerate(qualifiers, 1):
        ans[i] = seed
        
    sys.stdout.write('\n'.join(map(str, ans)) + '\n')

if __name__ == '__main__':
    main()

---

This editorial was generated by gemini-3.8-flash-high.