Overview

In this problem, among \(N\) participants, we need to extract those with a total score of at least \(K\) points, sort them in descending order of score (or in ascending order of participant ID in case of ties), assign seed numbers to them, and finally output the results in the original order of participant IDs.

Analysis

In this problem, we need to efficiently process the following two steps:

1. Extracting and ranking qualified participants
   • Collect only the participants who satisfy the condition \(A_i + B_i \ge K\).
   • Sort them according to the rules (primary key: total score in descending order, secondary key: participant ID in ascending order).
2. Outputting the results in the original order of participant IDs
   • The output must be printed not in the order of seed numbers, but in order of IDs: “result for participant \(1\), result for participant \(2\), …”.

Naive Approach and Its Issues

If, for each participant \(i\), we compare them against everyone else each time to count “how many qualified participants have a higher score (or the same score with a smaller ID)”, it would take \(O(N)\) time per participant, leading to \(O(N^2)\) overall. Since the constraint in this problem is \(N \le 10^5\), the number of operations for \(O(N^2)\) would be around \(10^{10}\), which exceeds the time limit and results in a TLE (Time Limit Exceeded).

Solution

We can collect only the qualified participants into a single array and use sorting. By sorting, we can determine the overall ranking in \(O(N \log N)\) time. Once the ranking is determined, we prepare an array of size \(N+1\) initialized to \(-1\), and write the corresponding seed number at the index of each qualified participant’s ID. Finally, by simply printing the elements from index \(1\) to \(N\), we can output the results in \(O(N)\) time.

Algorithm

1. For each participant \(i\) (\(1 \le i \le N\)), compute the sum of their scores, \(A_i + B_i\).
2. If \(A_i + B_i \ge K\), add the pair of “participant ID \(i\)” and “score \(A_i + B_i\)” to an array qualified.
3. Sort qualified according to the following priorities:
   • If total scores differ: in descending order of total score (largest first)
   • If total scores are equal: in ascending order of participant ID (smallest first)
4. Assign seed numbers \(1, 2, \dots\) in order from the beginning of the sorted array.
   • Create an array ans of size \(N + 1\) initialized with \(-1\), and record ans[qualifier's ID] = seed number.
5. Output ans[i] in order for \(i = 1, 2, \dots, N\).

Complexity

• Time Complexity: \(O(N \log N)\)
  • Letting \(M\) (\(M \le N\)) be the number of qualifiers, the time required for sorting is \(O(M \log M) \le O(N \log N)\).
  • Reading the input, checking qualification, and printing the answers can each be done in \(O(N)\), so the overall bottleneck is sorting at \(O(N \log N)\), which easily passes within the time limit.
• Space Complexity: \(O(N)\)
  • Storing the array of qualified participants’ information and the array of seed numbers for each participant requires \(O(N)\) memory.

Implementation Notes

• Variable Types (Overflow Prevention): Scores \(A_i\) and \(B_i\) can be up to \(10^9\), so the total score can reach up to \(2 \times 10^9\). Although this fits within the range of a 32-bit signed integer (approximately \(2.14 \times 10^9\)), it is safer to use a 64-bit integer type (such as long long in C++) for the total score and the threshold \(K\) to eliminate any concern of overflow.

• Sorting Comparison Condition: Because the score is sorted in “descending order” while the ID is sorted in “ascending order” (opposite directions), take care not to make mistakes when writing the comparison function (such as a lambda expression).

• Fast I/O: Since there can be up to \(10^5\) lines of output, in C++, you can significantly reduce I/O time by writing cin.tie(nullptr); ios::sync_with_stdio(false); and using "\n" instead of std::endl for newlines.

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Participant {
    int id;
    long long score;
};

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

    int n;
    long long k;
    if (!(cin >> n >> k)) return 0;

    vector<Participant> qualified;
    qualified.reserve(n);

    for (int i = 1; i <= n; ++i) {
        long long a, b;
        cin >> a >> b;
        long long score = a + b;
        if (score >= k) {
            qualified.push_back({i, score});
        }
    }

    sort(qualified.begin(), qualified.end(), [](const Participant& x, const Participant& y) {
        if (x.score != y.score) {
            return x.score > y.score;
        }
        return x.id < y.id;
    });

    vector<int> ans(n + 1, -1);
    for (size_t i = 0; i < qualified.size(); ++i) {
        ans[qualified[i].id] = i + 1;
    }

    for (int i = 1; i <= n; ++i) {
        cout << ans[i] << "\n";
    }

    return 0;
}

---

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