Overview

In a quiz competition where \(N\) students compete in a group tournament, each round selects the strongest player from each group (highest skill value, and smallest student ID in case of ties), and they continue competing until only one person remains. Find the student ID of the last remaining student.

Analysis

In this problem, we need to repeatedly divide students into groups of \(K\), and have the strongest player from each group advance to the next round.

The key points are as follows:

• How to store student data: We need to store not just the skill value but also the student ID. This is because when skill values are equal, we want to select the student with the smaller ID.
• Efficient simulation: Naively creating a new list every time could be too slow, especially when \(N\) is large. However, by making good use of Python’s list or deque, we can simulate this sufficiently fast.
• How to divide into groups: Since students are already ordered by student ID, we simply take \(K\) students at a time from the front. No sorting is needed since the order is already guaranteed.

Algorithm

1. Store students in a list as (skill value, student ID) pairs.
2. Repeat the following until only one student remains:
   • Divide the current student list into groups of \(K\).
   • For each group, select the student with the highest skill value and smallest student ID, and add them to the next round’s list.
3. Output the student ID of the last remaining student.

Specifically, each round is processed as follows: - Extract a group using students[i:i+K], - Select the strongest player satisfying the conditions using min(group, key=lambda x: (-x[0], x[1])).

Complexity

• Time complexity: \(O(N)\)
  Each round examines every remaining student exactly once, and the number of rounds is at most \(\log_K N\), so the overall order is close to linear time.
• Space complexity: \(O(N)\)
  A list is needed to hold the student information.

Implementation Notes

• Managing students as (skill value, student ID) tuples makes selecting the winner straightforward.

• By specifying a key for min(), we compare with the priority order “descending skill value → ascending student ID”.

• Instead of creating a new list every round, overwriting the existing one improves memory efficiency, so the technique of reusing next_round is important.

  Source Code

from collections import deque

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

    # 生徒を (実力値, 出席番号) で管理 (出席番号は1-indexed)
    students = [(A[i], i+1) for i in range(N)]
    
    while len(students) > 1:
        next_round = []
        # K人ずつグループに分ける
        for i in range(0, len(students), K):
            group = students[i:i+K]
            # 実力値の最大値を持つ生徒を選ぶ
            # 実力値が同じなら出席番号が小さい人を選ぶ
            winner = min(group, key=lambda x: (-x[0], x[1]))
            next_round.append(winner)
        students = next_round
    
    print(students[0][1])

if __name__ == "__main__":
    main()

---

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