Overview

We filter out only the participants with a total score of \(K\) or more, and sort them in descending order of total score, breaking ties in ascending order of participant ID. We then assign seed numbers in that order and output them in ascending order of participant ID.

Analysis

Let \(S_i = A_i + B_i\) be the total score of participant \(i\). Participants who satisfy \(S_i \ge K\) advance to the finals.

For each participant, we could determine their seed number by checking all qualifying participants who have higher priority than them. However, this approach takes \(O(N^2)\) time in the worst case, which will not pass within the time limit for \(N \le 10^5\).

Therefore, we consider sorting the qualifying participants according to their priority. If we number them \(1, 2, \dots\) from the beginning of the sorted list, these will be their seed numbers.

In Python, sorting a list of tuples orders them first in ascending order of the first element, and then in ascending order of the second element if the first elements are equal. Taking advantage of this, we store each qualifying participant in the following form:

(-total, i)

• Negating the total score ensures that participants with higher scores come first.
• If the total scores are equal, participants with a smaller i (corresponding to the participant ID) come first.

For example, when \(K = 100\) and participants \(1, 2, 3, 4\) have total scores of \(120, 90, 150, 120\) respectively, the priority order of the qualifying participants is as follows:

Participant ID	Total Score	Seed Number
\(3\)	\(150\)	\(1\)
\(1\)	\(120\)	\(2\)
\(4\)	\(120\)	\(3\)

Participants \(1\) and \(4\) are tied, so participant \(1\) with the smaller ID takes priority. Participant \(2\) does not advance to the finals, so the answer for participant \(2\) is \(-1\).

Note that the output must be in ascending order of participant ID, not in order of seed number. Therefore, we record the assigned seed numbers into an array corresponding to the original participants.

Algorithm

1. Initialize an array answers of length \(N\) with all elements set to \(-1\).
2. For each participant, compute their total score total = a + b.
   • If total >= k, append (-total, i) to the list qualified.
   • Otherwise, do nothing.
3. Sort qualified in ascending order.
4. Assign seed numbers \(1, 2, \dots\) sequentially from the beginning of the sorted list, and record them in the corresponding answers[i].
5. Output the elements of answers from beginning to end, one per line.

The order after sorting matches the priority order specified in the problem. Therefore, the numbers assigned from the beginning are the correct seed numbers. In addition, participants who did not qualify will retain the initial value of \(-1\), producing the correct answer for all participants.

Complexity

Let \(M\) be the number of participants advancing to the finals. Processing the input and output takes \(O(N)\) time, and sorting takes \(O(M \log M)\) time. Since \(M \le N\), the worst-case complexity is as follows:

• Time complexity: \(O(N \log N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• The qualification condition is “greater than or equal to”, so use total >= k. Participants with a total score of exactly \(K\) also qualify for the finals.

• In the code, participants are managed using 0-based index i. Although the actual participant IDs are \(i+1\), their relative order does not change, so i can be used directly for tie-breaking.

• Using enumerate(qualified, 1) allows obtaining seed numbers sequentially starting from \(1\).

• In addition to sorting by total score in descending order, we must also satisfy the condition that ties are broken by participant ID in ascending order. Sorting (-total, i) in standard ascending order achieves both simultaneously.

• Even if no participants qualify for the finals, all values in answers remain \(-1\) and will be output as such, so no special handling is required.

  Source Code

import sys


def main():
    input = sys.stdin.buffer.readline
    n, k = map(int, input().split())
    qualified = []
    answers = [-1] * n

    for i in range(n):
        a, b = map(int, input().split())
        total = a + b
        if total >= k:
            qualified.append((-total, i))

    qualified.sort()

    for seed, (_, i) in enumerate(qualified, 1):
        answers[i] = seed

    sys.stdout.write("\n".join(map(str, answers)))


if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-6-astra-medium.