Overview

We divide the remaining students into groups of \(K\) in order of their student numbers, keep only the “strongest player (smallest number if tied)” from each group, and repeat this operation until one person remains. We need to find the winner (student number).

Analysis

What each round essentially does is “partition the current remaining sequence into blocks of \(K\) from left to right, and select one element with the maximum value in each block (leftmost = smallest number in case of ties).”

The key observation is as follows:

• Each round can be processed in \(O(M)\) where \(M\) is the number of remaining people
  (Each student is compared only once within their group)
• As rounds progress, the number of people decreases roughly as \(M \to \lceil M/K \rceil\), so the total work is a geometric series:
  $\(N + \left\lceil \frac{N}{K}\right\rceil + \left\lceil \frac{N}{K^2}\right\rceil + \cdots\)\( which sums to **approximately \)O(N)\(** (even in the worst case \)K=2\(, the total is \)<2N$).

Alternatively, naive approaches like “rebuilding groups every round” or “managing survivors with heavy data structures” can also solve the problem correctly, but in Python the constant factor tends to be large. This solution directly simulates the process but processes each round in linear time for efficiency.

For tie-breaking, “if strengths are equal, the one with the smaller student number wins,” so in 0-indexed internal representation: - The one with greater strength wins - If strengths are equal, the one with the smaller index (student number) wins
This is all we need for the comparison condition.

Algorithm

1. Maintain a list rem of remaining students, initially [0, 1, 2, ..., N-1] (0-indexed).
2. Repeat the following until the length of rem becomes 1:
   • Scan rem from left to right in blocks of \(K\), and for each block (the last block may have fewer than \(K\) elements):
     • Select the \(i\) that maximizes \((A_i, -i)\) within the block
       (maximum strength; if tied, smallest \(i\) = smallest student number)
     • Append the selected \(i\) to the next round’s list new
   • Set rem = new and proceed to the next round
3. Convert the last remaining person rem[0] back to 1-indexed and output.

For example, if \(K=3\) and the remaining list is [2,5,7, 1,4] (in student number order):
- Group 1: Select the winner from [2,5,7]
- Group 2: Select the winner from [1,4]
This process is performed every round.

Complexity

• Time complexity: \(O\!\left(N + \frac{N}{K} + \frac{N}{K^2} + \cdots\right) = O(N)\)
• Space complexity: \(O(N)\) (for storing the list of remaining student numbers)

Implementation Notes

• Tie-breaking: Use a condition like a2 > bestA or (a2 == bestA and idx2 < best) to select the smaller-numbered student when strengths are equal.

• Fast I/O: Since \(N \le 5\times 10^5\), we use sys.stdin.buffer.read() for bulk reading with manual parsing for speed.

• 0-index / 1-index: Internally we use 0-indexed (0..N-1) and add +1 at output time.

  Source Code

import sys

data = sys.stdin.buffer.read()
n_data = len(data)
i = 0

# Read N
while i < n_data and data[i] <= 32:
    i += 1
N = 0
while i < n_data and data[i] > 32:
    N = N * 10 + (data[i] - 48)
    i += 1

# Read K
while i < n_data and data[i] <= 32:
    i += 1
K = 0
while i < n_data and data[i] > 32:
    K = K * 10 + (data[i] - 48)
    i += 1

A = [0] * N
for t in range(N):
    while i < n_data and data[i] <= 32:
        i += 1
    num = 0
    while i < n_data and data[i] > 32:
        num = num * 10 + (data[i] - 48)
        i += 1
    A[t] = num

rem = list(range(N))
K_local = K
A_local = A

while len(rem) > 1:
    m = len(rem)
    new = []
    new_append = new.append
    rem_local = rem
    i = 0
    while i < m:
        best = rem_local[i]
        bestA = A_local[best]
        end = i + K_local
        if end > m:
            end = m
        j = i + 1
        while j < end:
            idx2 = rem_local[j]
            a2 = A_local[idx2]
            if a2 > bestA or (a2 == bestA and idx2 < best):
                best = idx2
                bestA = a2
            j += 1
        new_append(best)
        i = end
    rem = new

sys.stdout.write(str(rem[0] + 1) + "\n")

This editorial was generated by gpt-5.2-high.