Overview

When scores are sorted in “descending order, with ties broken by ascending student ID,” find the student ID of the \(K\)-th student from the top.

Analysis

Since the “sorting rule” for this problem is clearly defined, a straightforward approach would be to sort students \((i, S_i)\) and take the \(K\)-th element. While \(N \le 2\times 10^5\) means a standard \(O(N\log N)\) sort would typically be fast enough, there is an important observation that allows for an even lighter solution.

• The range of possible scores \(S_i\) is very small: \(0 \le S_i \le 100\) (only 101 distinct values)
• When scores are tied, students are ordered by ascending student ID → within the same score group, we simply list student IDs in ascending order

Using this property, we can place students into “buckets” by score and count from the highest score downward, directly finding the \(K\)-th student without sorting.

For example, if the buckets by score are: - 90 points: [2, 5] - 80 points: [1, 4, 6]

then the ranking is 90 points [2, 5] → 80 points 1, 4, 6.

Algorithm

1. Prepare an array buckets[score] for each score from \(0\) to \(100\).
2. Iterate through students in order of student ID (\(1\) to \(N\)), and for each student with score score, append their student ID i to buckets[score].
   • Since we append in order of student ID, each bucket is automatically sorted in “ascending student ID order.”
3. Iterate through scores in descending order from \(100\) to \(0\), accumulating the count of students seen so far.
   • Let cnt be the number of students seen so far. For a bucket b at score score, the moment cnt + len(b) >= K, the \(K\)-th student exists within this bucket.
4. The position within the bucket is K - cnt - 1 (0-indexed), so output that element.

Complexity

• Time complexity: \(O(N + 101) \simeq O(N)\)
• Space complexity: \(O(N + 101) \simeq O(N)\) (since we store all student IDs in the buckets)

Implementation Notes

• To satisfy the “ascending student ID order” for ties, we iterate through the input in student ID order (enumerate(..., start=1)) and append to buckets in that order. This eliminates the need to sort within each bucket.

• When extracting the \(K\)-th element, be careful with 0-indexing: use b[K - cnt - 1].

• Since the input can be up to \(2\times 10^5\), using sys.stdin.buffer.read() in Python allows for faster input reading.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, K = data[0], data[1]
    S = data[2:]

    buckets = [[] for _ in range(101)]
    for i, score in enumerate(S, start=1):
        buckets[score].append(i)

    cnt = 0
    for score in range(100, -1, -1):
        b = buckets[score]
        if cnt + len(b) >= K:
            print(b[K - cnt - 1])
            return
        cnt += len(b)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.