Overview

Extract only the participants who qualify for the finals and sort them in “descending order of total score, ascending order of participant ID”. Assign seed numbers in this sorted order, and output the answers in the order of participant IDs.

Analysis

Let \(S_i = A_i + B_i\) be the total score of participant \(i\). The condition to qualify for the finals is \(S_i \ge K\).

One might consider counting the number of participants with higher priority than oneself by comparing each participant with all others. However, this approach takes \(O(N^2)\) time, which will exceed the time limit for \(N \le 10^5\).

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

The priority is as follows:

• Higher total score comes first.
• If the total scores are equal, smaller participant ID comes first.

In the implementation, to achieve this ordering, we store pairs of \((-S_i, i)\). When sorting pairs in ascending order, the first elements are compared first, and if they are equal, the second elements are compared.

By negating the score, a larger score results in a smaller first element, allowing us to achieve the desired order using standard ascending sort.

For example, suppose \(K = 100\) and the total scores are as follows:

Participant ID	Total Score
1	120
2	90
3	150
4	120

The order of qualifying participants is participants \(3, 1, 4\). Since participants \(1\) and \(4\) have the same score, participant \(1\) with the smaller ID comes first.

Therefore, the answers in the order of participant IDs are \(2, -1, 1, 3\).

Algorithm

1. Prepare an array answer to store the answers, initialized with \(-1\) for all elements.
2. Calculate the total score \(S_i = A_i + B_i\) for each participant.
   • If \(S_i \ge K\), add \((-S_i, i)\) to qualified.
   • If \(S_i < K\), do not add it.
3. Sort qualified in ascending order.
4. Assign seed number \(j+1\) to the \(j\)-th participant (\(0\)-indexed) in the sorted list.
   • Store it in the element of answer corresponding to the original participant ID.
5. Output answer in order from the beginning.

Sorting arranges the qualifying participants according to the problem’s priority rules, so assigning numbers sequentially from the beginning gives the correct seed numbers. In addition, participants who do not qualify retain their initial value of \(-1\), yielding the correct results for all participants.

Complexity

Let \(M\) be the number of qualifying participants. Input and output take \(O(N)\), and sorting takes \(O(M \log M)\). Since \(M \le N\), the overall 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 check with A + B >= K.

• Seed numbers are not duplicated even if scores are tied. Tied participants are ordered by their participant IDs, and each is assigned a distinct number.

• The output order is by participant ID, not by seed number. Keep the original participant ID during sorting and write the result into the corresponding position in answer.

• Participant IDs are \(0\)-indexed in the code, but this does not change their relative ordering, so they can be compared directly. Since seed numbers are \(1\)-indexed, add \(1\) to their sorted position.

• The maximum total score is \(2 \times 10^9\). The code uses long long to safely handle the scores and their negated values without overflow.

• Even if there are \(0\) qualifying participants, all elements in answer remain \(-1\), so no special case handling is needed.

  Source Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    long long K;
    cin >> N >> K;

    vector<pair<long long, int>> qualified;
    qualified.reserve(N);
    vector<int> answer(N, -1);

    for (int i = 0; i < N; ++i) {
        long long A, B;
        cin >> A >> B;
        if (A + B >= K) {
            qualified.emplace_back(-(A + B), i);
        }
    }

    sort(qualified.begin(), qualified.end());

    for (int i = 0; i < static_cast<int>(qualified.size()); ++i) {
        answer[qualified[i].second] = i + 1;
    }

    for (int seed : answer) {
        cout << seed << '\n';
    }

    return 0;
}

---

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