Overview

This problem asks you to find the student ID of the \(K\)-th student when students are sorted by score in descending order (with ties broken by student ID in ascending order).

Analysis

This problem requires “compound sorting” based on two criteria.

Key observations: 1. We need to maintain both “score” and “student ID” for each student 2. The sorting priority is: “score (descending)” as primary, “student ID (ascending)” as secondary 3. After sorting, we simply extract the \(K\)-th element

Working through a concrete example:

For instance, with \(N = 5\), \(K = 3\), and scores \(S = [80, 90, 80, 70, 90]\):

After sorting: 1. Student ID 2 (score 90) 2. Student ID 5 (score 90) ← Same score but larger student ID, so ranked 2nd 3. Student ID 1 (score 80) 4. Student ID 3 (score 80) 5. Student ID 4 (score 70)

Therefore, the \(K = 3\)rd student has student ID 1.

Why a straightforward approach works: Since \(N \leq 2 \times 10^5\) and the time complexity of sorting is \(O(N \log N)\), this can be processed fast enough.

Algorithm

1. Prepare the data structure: Create a list of (score, student ID) tuples for each student
2. Sort: Sort by score in descending order, with ties broken by student ID in ascending order
   • In Python, this is achieved with key=lambda x: (-x[0], x[1])
   • By negating the score -x[0], ascending sort becomes descending sort
3. Output the answer: Extract the student ID from the \((K-1)\)-th element (0-indexed) of the sorted list

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting)
• Space complexity: \(O(N)\) (for the list storing student information)

Implementation Notes

1. Student IDs are 1-indexed: Since Python lists are 0-indexed, create student IDs as i + 1
2. Compound sort key: By using a tuple (-score, student ID) as the key, we can achieve descending order by score and ascending order by student ID in a single sort
3. Extracting the K-th element: Don’t forget to extract the \((K-1)\)-th element (0-indexed) from the sorted list

Source Code

N, K = map(int, input().split())
S = list(map(int, input().split()))

# Create a list of (score, student ID)
# Student IDs start from 1
students = [(S[i], i + 1) for i in range(N)]

# Sort by score in descending order, ties broken by student ID in ascending order
students.sort(key=lambda x: (-x[0], x[1]))

# Output the student ID of the K-th student (K-1 in 0-indexed)
print(students[K - 1][1])

This editorial was generated by claude4.5opus.