Overview

This problem asks us to filter only the participants whose total score \(A_i + B_i\) is at least \(K\), sort them in “descending order of total score, and in ascending order of participant ID in case of a tie”, and find their rank (seed number). This is a typical practice problem for “sorting with multiple keys”.

Analysis

Key Observations

1. No need to handle the first-half and second-half scores separately
   Both qualifying for the finals and the priority order for seed numbers are determined solely by the total score \(S_i = A_i + B_i\). Therefore, once we calculate \(S_i\) upon reading the input, we only need to consider the pair of “value \(S_i\) and participant ID \(i\)” going forward.

2. The seed number is simply the “order after sorting”
   When the qualifiers are sorted in order of priority, their seed numbers are simply assigned from the beginning as \(1, 2, 3, \dots\). There is no need for complex rank calculations; we just need to sort them and number them sequentially from the front.

Note that even if participants have the same score, they do not share the “same rank” (seed numbers are uniquely assigned without duplicates). If there is a tie, the participant with the smaller participant ID comes first, so tie-breaking must strictly be done in ascending order of participant ID. Forgetting this will result in a WA on test cases with ties.

The Issue with a Naive Approach

If we directly implement the definition by “counting how many qualifiers have a higher priority than oneself for each participant”, it requires scanning all participants for each person, leading to an \(O(N^2)\) time complexity. Since \(N \le 10^5\), this would require around \(10^{10}\) comparisons, which will definitely result in TLE.

We can solve this by realizing that we want to determine the ranks of all participants at once, and sorting once allows us to determine everyone’s rank simultaneously. Sorting takes only \(O(N \log N)\).

Preserving the Original Positions

If we simply sort the scores, the participant ID information is lost, making it impossible to produce the output in the original order. Therefore, the key is to keep track of the original indices by either: - Sorting pairs of (total score, participant ID), or - Sorting a list of participant IDs (indices) using the score as the key.

We can then write the answers back into an array ans[i] of length \(N\), and finally output each element \(1\) line at a time.

Concrete Example

For \(N = 5\) and \(K = 100\):

\(i\)	\(A_i\)	\(B_i\)	\(S_i\)	Qualified?
1	50	60	110	Yes
2	30	40	70	No
3	100	20	120	Yes
4	60	50	110	Yes
5	0	0	0	No

The qualifiers are \(\{1, 3, 4\}\). Sorting them by priority gives \(3 (120), 1 (110), 4 (110)\) (since \(1\) and \(4\) are tied, participant \(1\) with the smaller ID comes first). Thus, the seed numbers are \(3 \to 1\), \(1 \to 2\), and \(4 \to 3\), yielding the answers 2, -1, 1, 3, -1 in order.

Algorithm

1. Read the input and compute \(S_i = A_i + B_i\) for each \(i\).
2. Collect only the indices of participants satisfying \(S_i \ge K\) to create a list cand.
3. Sort cand in ascending order of the key \((-S_i,\ i)\) (i.e., descending order of \(S_i\), and ascending order of \(i\) in case of a tie).
4. Initialize an answer array of length \(N\) with \(-1\), and assign \(1, 2, 3, \dots\) to the corresponding indices in cand from front to back.
5. Output the answer array from the beginning.

Note that since Python’s sort is a stable sort (the original order of elements with equal keys is preserved), using just key=lambda i: -tot[i] would also work correctly if cand was initially constructed in ascending order of indices. However, explicitly using \((-S_i, i)\) as the key is safer to make the intention clear.

Complexity

• Time Complexity: \(O(N \log N)\) (dominated by sorting; reading input and computing \(S_i\) takes \(O(N)\))
• Space Complexity: \(O(N)\)

Implementation Notes

• Risk of Overflow: \(A_i + B_i\) can reach up to \(2 \times 10^9\), exceeding the range of a 32-bit signed integer. In languages like C++, please use long long (Python supports arbitrary-precision integers, so it is not an issue). \(K\) can also be up to \(2 \times 10^9\).

• Writing Descending Sort: In Python, it is easy to negate the value in key, such as key=lambda i: (-tot[i], i). Because the directions differ (“scores in descending order, IDs in ascending order”), simply adding reverse=True would also reverse the order of the IDs, leading to a WA. Be careful here.

• Fast I/O: Since there are up to \(N \le 10^5\) lines of input and output, in Python it is safest to read all at once using sys.stdin.buffer.read().split(), and join the output with "\n".join(...) to write using sys.stdout.write. Repeated calls to input() and print() tend to be slow.

• Boundary Conditions: The condition is \(S_i \ge K\) (“at least” \(K\) points). When \(K = 0\), all participants qualify, and when \(0\) participants qualify, all lines should be -1. Make sure not to mishandle the inequality/equality.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); k = int(data[1])
    tot = [0] * n
    idx = 2
    for i in range(n):
        tot[i] = int(data[idx]) + int(data[idx + 1])
        idx += 2
    cand = [i for i in range(n) if tot[i] >= k]
    cand.sort(key=lambda i: (-tot[i], i))
    ans = [-1] * n
    r = 1
    for i in cand:
        ans[i] = r
        r += 1
    sys.stdout.write("\n".join(map(str, ans)))

main()

---

This editorial was generated by claude5opus-high.