Overview

In this problem, we need to filter out the participants whose total score \(A_i + B_i\) is at least \(K\), sort them in descending order of total score (breaking ties in ascending order of participant index), and output each participant’s rank (seed number) in the original order of participant indices.

This is a typical “filter by condition \(\to\) sort with multiple keys \(\to\) assign rankings” problem.

Analysis

Key Observation

The only information essentially needed in this problem is each participant’s total score \(S_i = A_i + B_i\). There is no need to store \(A_i\) and \(B_i\) separately.

What we need to do can be broken down into the following three steps:

1. Collect participants who satisfy \(S_i \ge K\) (the qualifiers).
2. Sort the collected participants in descending order of \(S_i\), breaking ties in ascending order of \(i\).
3. Assign seed numbers \(1, 2, 3, \dots\) in that sorted order, and write them back to the positions corresponding to their original participant indices.

Note that the output must be given in order from participant \(1\) onward. Since sorting loses the original order, we need to keep track of the participant indices along with their scores.

Pitfalls of a Naive Approach

If we straightforwardly implement an approach that “counts for each participant how many participants have higher priority than them,” it will take \(O(N^2)\) time because we would compare each participant against all others. Since \(N \le 10^5\), this requires around \(10^{10}\) comparisons and will definitely result in TLE.

On the other hand, using sorting takes only \(O(N \log N)\) time, which is around \(10^5 \times 17 \approx 2 \times 10^6\) operations and easily passes within the time limit.

Beware of Integer Overflow

Since \(A_i, B_i \le 10^9\), \(A_i + B_i\) can be up to \(2 \times 10^9\). This is very close to the upper limit of a signed 32-bit integer, \(2147483647 \approx 2.1 \times 10^9\), and the same applies to \(K \le 2 \times 10^9\). While it may seem to barely fit, it is risky, so it is safer to handle the total scores and \(K\) using 64-bit integers (long long). You do not need to worry about this in Python, but it is an important point to watch out for in C++ and Java.

Concrete Example

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

\(i\)	\(A_i\)	\(B_i\)	\(S_i\)
1	50	60	110
2	30	30	60
3	70	40	110
4	90	90	180
5	10	90	100

The qualifiers satisfying \(S_i \ge 100\) are \(\{1, 3, 4, 5\}\). Sorting these by priority gives:

• \(S = 180\): Participant \(4\) \(\to\) Seed \(1\)
• \(S = 110\): Participants \(1\) and \(3\) (tied, so participant \(1\) with the smaller index comes first) \(\to\) Participant \(1\) gets Seed \(2\), Participant \(3\) gets Seed \(3\)
• \(S = 100\): Participant \(5\) \(\to\) Seed \(4\)

Participant \(2\) failed to qualify, so their result is \(-1\). The output from top to bottom will be 2, -1, 3, 1, 4.

Algorithm

1. While reading the input, store \(S_i = A_i + B_i\) into an array s (it is convenient to use \(0\)-based indexing).
2. Create a list idx containing only the indices \(i\) that satisfy \(S_i \ge K\).
3. Sort idx using the following comparison rule:
   • If \(S_x \ne S_y\), then \(S_x > S_y\) (descending order of score)
   • If \(S_x = S_y\), then \(x < y\) (ascending order of index)
4. Initialize the answer array ans with all \(-1\)s, and iterate through the sorted idx from the beginning, setting ans[idx[r]] = r + 1.
5. Output ans sequentially from the beginning.

The operation in Step 4 of “writing back to the original positions” is the key to this solution. The participant at position \(r\) (\(0\)-indexed) in the sorted result gets seed number \(r + 1\), so we assign this value to that participant’s original index.

Regarding Step 3, note that while C++’s std::sort is not a stable sort, there is no issue because the comparison function explicitly specifies ascending order of indices in case of a tie. (If you use a stable sort such as stable_sort, assuming indices are initially in ascending order, you can just compare scores in descending order).

Complexity

• Time complexity: \(O(N \log N)\) (Dominated by sorting. Reading input and printing output take \(O(N)\))
• Space complexity: \(O(N)\) (Total score array, index list, and answer array)

Key Implementation Points

• Use 64-bit integers: \(A_i + B_i\) can be up to \(2 \times 10^9\) and \(K\) can also be up to \(2 \times 10^9\), which is near the limit of 32-bit integers. Use long long in C++ and long in Java.

• Preserve participant indices: It is clean and concise to sort the “indices” rather than the “values themselves.” By storing indices in a vector<int> idx and referencing s[x] inside the comparator, you do not have to create pairs of values and indices. (Storing \((-S_i, i)\) in a pair<long long, int> and sorting in ascending order is also a standard approach.)

• Fast I/O: There are up to \(N \le 10^5\) lines of input and output. When using cin/cout in C++, include ios::sync_with_stdio(false); cin.tie(nullptr);, or use scanf as in the example code. For output, buffering the text and writing it all at once can be faster than calling printf line by line.

• Case where everyone fails to qualify: If \(K\) is very large and no one qualifies, idx will be empty, but since ans is initialized with all \(-1\)s, the code will work correctly as is. No special handling is required.

• Case where \(K = 0\): Since everyone’s score is non-negative (\(0\) or greater), all participants are guaranteed to qualify. Note that the boundary condition is “\(\ge K\)” (not “\(>\)”).

  Source Code

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

int main(){
    int N; long long K;
    scanf("%d %lld", &N, &K);
    vector<long long> s(N);
    for(int i=0;i<N;i++){
        long long a,b; scanf("%lld %lld",&a,&b);
        s[i]=a+b;
    }
    vector<int> idx;
    idx.reserve(N);
    for(int i=0;i<N;i++) if(s[i]>=K) idx.push_back(i);
    sort(idx.begin(), idx.end(), [&](int x,int y){
        if(s[x]!=s[y]) return s[x]>s[y];
        return x<y;
    });
    vector<int> ans(N,-1);
    for(int r=0;r<(int)idx.size();r++) ans[idx[r]]=r+1;
    string out;
    out.reserve(N*8);
    for(int i=0;i<N;i++){
        out += to_string(ans[i]);
        out += '\n';
    }
    fputs(out.c_str(), stdout);
    return 0;
}

---

This editorial was generated by claude5opus-high.