Overview

Given the scores of \(N\) participants, the task is to identify the \(K\)-th highest score (the borderline) and find the total number of participants who scored at or above that score.

Analysis

As stated in the problem, we first need to find the \(K\)-th score \(B_K\) when the participants’ scores are arranged in descending order. This \(B_K\) becomes the “borderline” for being awarded.

We need to count the number of people with scores at or above the borderline. Note the constraint \(N \leq 2 \times 10^5\). If we use unnecessary nested loops for score comparison or counting, the time complexity becomes \(O(N^2)\), which would exceed the time limit (TLE).

Therefore, we take the approach of sorting the score array. The time complexity of sorting is \(O(N \log N)\), which is sufficiently fast for this constraint. Once the array is sorted, the borderline score can be easily identified. Furthermore, by leveraging the sorted array, we can use binary search to efficiently determine “how many people are at or above the borderline” in \(O(\log N)\). (※ Counting sequentially would also be \(O(N)\) and would pass within the time limit, but using binary search results in a more elegant and versatile implementation.)

Algorithm

1. Sort the participants’ score array \(A\) in ascending order (from smallest to largest).
2. When arranged in ascending order, the \(K\)-th highest score is the “\(K\)-th element from the end.” We call this the borderline (border).
3. Use a binary search algorithm to find the position (index) where scores greater than or equal to border first appear in array \(A\).
4. The number of participants with scores at or above the borderline is the total number of people \(N\) minus that index.

Concrete example: For scores A = [10, 20, 30, 40, 40, 50] with \(K=3\): - The 3rd score from the end is 40, so the borderline is 40. - The first occurrence of a value ≥ 40 is at index 3 (0-indexed). - Subtracting \(3\) from the total number of people \(6\) gives 3 people who are awarded.

Complexity

• Time complexity: \(O(N \log N)\)
  • Sorting the array takes \(O(N \log N)\).
  • Binary search (bisect_left) takes \(O(\log N)\).
  • Overall, this is \(O(N \log N)\), which comfortably fits within the time limit.
• Space complexity: \(O(N)\)
  • Used to store the scores of \(N\) participants in an array.

Implementation Notes

• Using negative indices In Python, you can use negative indices to access elements from the end of an array. In an ascending-sorted array, the \(K\)-th highest element can be intuitively obtained by writing A[-K].

• How bisect_left works The bisect_left(A, x) function from Python’s standard library bisect module returns the leftmost index where value x should be inserted into the sorted array A (i.e., the position where the first value ≥ x appears). By using this, the number of elements satisfying the condition can be easily calculated in a single line: N - bisect_left(A, border).

  Source Code

import sys
import bisect

def main():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    K = int(data[1])
    A = [int(x) for x in data[2:]]
    
    A.sort()
    border = A[-K]
    ans = N - bisect.bisect_left(A, border)
    print(ans)

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3.1-pro-thinking.