Overview

Given \(N\) students, arrange them in “descending order of scores”, and if scores are the same, in “ascending order of student ID”. Find the student ID of the student who comes \(K\)-th from the top.

Analysis

To solve this problem, we need to sort the data considering multiple conditions (score and student ID).

1. Sorting Priority:

   • Primary: Score (higher is better)
   • Secondary: Student ID (smaller is better)

2. Sorting Trick: The standard sort function in most programming languages sorts in “ascending order (smallest first)”. Since the primary criterion here is “descending order of scores”, handling it directly requires a small trick. A convenient technique is to “multiply the score by \(-1\) to make it negative”. For example, if the scores are 100, 90, 100, multiplying by \(-1\) gives -100, -90, -100. Sorting these in ascending order gives -100, -100, -90, which corresponds to the original scores in “descending order”.

3. Data Management: To manage “score” and “student ID” as a pair, we use tuples (Python’s (a, b) format). When tuples are sorted, they are first compared by the 1st element, and if those are equal, by the 2nd element. This property naturally satisfies the conditions of this problem.

Algorithm

The problem can be solved with the following steps:

1. For student \(i\), pair their score \(S_i\) with their student ID \(i\), creating a tuple of the form (-S_i, i).
2. Read all created tuples into a list.
3. Sort the list in ascending order.
   • The first element -S_i is sorted in ascending order (= original scores in descending order).
   • If the first elements are the same, the second element i is sorted in ascending order (= student IDs in ascending order).
4. Retrieve the \(K\)-th element from the sorted list (index \(K-1\) in programming) and output its student ID.

Complexity

• Time Complexity: \(O(N \log N)\)
  • Reading the data takes \(O(N)\), and sorting takes \(O(N \log N)\). For \(N = 2 \times 10^5\), \(N \log N\) is approximately \(3.6 \times 10^6\), which is well within the time limit.
• Space Complexity: \(O(N)\)
  • Since we store data for \(N\) students in a list, the memory usage is proportional to the number of students.

Implementation Notes

• Fast I/O: Since \(N\) can be large, in Python we use sys.stdin.read().split() instead of input() to improve input speed.

• 0-indexed: When accessing the \(K\)-th element of the list, since indices start from 0, we specify students[k - 1].

• Student ID: Student IDs in the problem start from \(1\). By using the loop variable \(i\) and writing i + 1, we can manage them correctly.

  Source Code

import sys

def solve():
    # 標準入力から全てのデータを読み込み、空白で分割してリストに格納します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N（生徒数）とK（求めたい順位）を取得します
    n = int(input_data[0])
    k = int(input_data[1])
    
    # 各生徒の情報を (-得点, 出席番号) のタプルとしてリストに格納します
    # 得点を負の値にすることで、昇順ソートした際に出席番号の昇順を保ちつつ、
    # 得点の高い順（得点の絶対値が大きい順）に並べることができます
    students = [(-int(input_data[i + 2]), i + 1) for i in range(n)]
    
    # タプルをソートします。第一要素（-得点）の昇順、
    # 第一要素が同じなら第二要素（出席番号）の昇順で並びます
    students.sort()
    
    # 上からK番目（インデックス K-1）の生徒の出席番号を出力します
    sys.stdout.write(str(students[k - 1][1]) + '\n')

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-preview.