Overview

Given students’ scores and their student IDs, we need to find the student ID of the \(K\)-th student when sorted in descending order of scores (with ties broken by ascending student ID).

Analysis

In this problem, we need to sort students in descending order of their scores. However, when multiple students have the same score, they must be ordered by ascending student ID.

A naive approach, such as repeatedly finding the student with the highest score (e.g., selection sort), would require \(O(N^2)\) computation time in the worst case, which is too slow for the constraint \(N \leq 2 \times 10^5\) (TLE).

Instead, we consider sorting all students at once. By treating each student as a pair of “score” and “student ID” and carefully choosing the sort key, we can efficiently sort them in the required order.

Algorithm

1. Create a list of pairs consisting of “score” and “student ID” for each student.
2. Sort this list as follows:
   • In descending order of score
   • For equal scores, in ascending order of student ID
3. After sorting, output the student ID corresponding to the \(K\)-th element from the beginning.

For example, given the input:

N = 5, K = 3
S = [80, 90, 90, 70, 80]

The student information is: - Student 1: 80 points - Student 2: 90 points - Student 3: 90 points - Student 4: 70 points - Student 5: 80 points

As pairs:

[(80, 1), (90, 2), (90, 3), (70, 4), (80, 5)]

After sorting:

[(90, 2), (90, 3), (80, 1), (80, 5), (70, 4)]

The 3rd from the top is (80, 1), so the answer is student ID 1.

Complexity

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

Implementation Notes

• By setting the sort key as (-score, student_ID), we can achieve descending order of scores and ascending order of student IDs simultaneously.

• Since student IDs are 1-indexed, be careful not to shift the indices (in the code, this is handled with i+1).

  Source Code

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

# (得点, 出席番号) のリストを作成し、得点の降順、出席番号の昇順でソート
students = [(S[i], i + 1) for i in range(N)]
students.sort(key=lambda x: (-x[0], x[1]))

# K番目の生徒の出席番号を出力
print(students[K - 1][1])

---

This editorial was generated by qwen3-coder-480b.