Overview

This is a problem where \(N\) students are divided into groups of \(K\), and the winner of each group (the one with the highest skill value, or the smallest student number in case of a tie) advances to the next round. We simulate this process until a single person (the champion) remains.

Analysis

At first glance, it may seem that the computation is heavy since we repeat many rounds, but let’s consider how the number of surviving students changes each round.

In each round, the number of participants becomes approximately \(\frac{1}{K}\) of the previous count. Since \(K \geq 2\), the total number of participants across all rounds is: $\(N + \frac{N}{K} + \frac{N}{K^2} + \frac{N}{K^3} + \dots\)\( By the geometric series sum formula, this is at most around \)2N\(. Therefore, even if we naively simulate each round's matches, the overall computation fits within linear time in \)N$, which is well within the time limit.

Regarding the winner determination rule: “the person with the highest skill value, or the smallest student number in case of a tie.” If we scan through the group in order of increasing student number and only update when a skill value strictly greater than the current maximum appears, the student with the smallest student number is naturally selected in case of ties.

Algorithm

The simulation proceeds as follows:

1. Initialization: Set the current survivor list survivors to \([0, 1, \dots, N-1]\) (student numbers minus 1).
2. Round iteration: While the number of elements in survivors is greater than 1, repeat the following: a. Create an empty list next_survivors for the next round’s survivors. b. Take groups of \(K\) people at a time from the front of survivors. c. Within each group, find the student with the maximum skill value \(A_i\).

      - If skill values are equal, prioritize the student appearing earlier in the group (= with a smaller student number).
   

   d. Add the group’s winner to next_survivors. e. Update survivors with next_survivors.
3. Output: Add 1 to the student number of the last remaining person and output it.

Complexity

• Time complexity: \(O(N)\)
  • As described above, the total number of comparisons across all rounds is bounded by a constant multiple of \(N\).
• Space complexity: \(O(N)\)
  • The array \(A\) storing skill values and the list managing survivors use \(O(N)\) memory.

Implementation Notes

• Efficient input: Since \(N\) can be as large as \(5 \times 10^5\), in Python it is faster to read all input at once using sys.stdin.read().split() rather than calling input() repeatedly.

• Tiebreak handling: When determining the winner within a group, by using the comparison operator > as in if A[curr_idx] > max_strength:, we ensure that when skill values are equal, the student who appeared first (= with the smaller student number) is retained.

• Memory management: When updating the survivor list, being mindful of freeing the old list when it is no longer needed provides peace of mind for problems with strict memory limits. In Python, reassigning the list variable makes the old list automatically eligible for garbage collection.

  Source Code

import sys
import itertools

def solve():
    # 全ての入力を一度に読み込み、空白で分割してリストにする
    # sys.stdin.read().split() は大量の入力を高速に読み込むのに適している
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 生徒の人数 N と、グループの人数 K
    N = int(input_data[0])
    K = int(input_data[1])
    
    # 各生徒の実力値を整数リスト A に変換
    # itertools.islice を使うことで、スライスによる新しいリスト作成を避け、メモリを節約する
    A = list(map(int, itertools.islice(input_data, 2, None)))
    
    # 不要になった文字列リストを削除してメモリを解放
    del input_data
    
    # 現在残っている生徒の出席番号（0-indexed）を管理するリスト
    # 最初は 0, 1, ..., N-1 で、これは出席番号の昇順になっている
    survivors = list(range(N))
    
    # 生徒が1人になるまでラウンドを繰り返す
    while len(survivors) > 1:
        next_survivors = []
        n_surv = len(survivors)
        
        # 現在の生存者を K 人ずつのグループに分ける
        for i in range(0, n_surv, K):
            # 各グループ内での勝者を決定する
            # グループの範囲は survivors[i] から survivors[limit-1]
            limit = i + K
            if limit > n_surv:
                limit = n_surv
            
            # グループの最初の生徒を暫定的な勝者とする
            best_idx = survivors[i]
            max_strength = A[best_idx]
            
            # グループ内の他の生徒と比較
            for j in range(i + 1, limit):
                curr_idx = survivors[j]
                # 実力値が高い生徒がいれば更新
                # 実力値が同じ場合は、出席番号が小さい（先に出現した）生徒を優先するため、
                # 厳密に大きい場合のみ更新する
                if A[curr_idx] > max_strength:
                    max_strength = A[curr_idx]
                    best_idx = curr_idx
            
            # グループの勝者を次のラウンドの生存者リストに追加
            next_survivors.append(best_idx)
        
        # 生存者リストを更新
        survivors = next_survivors
        
    # 最終的な優勝者の出席番号（1-indexed）を出力
    sys.stdout.write(str(survivors[0] + 1) + '\n')

if __name__ == '__main__':
    solve()

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