Overview

This is a problem where we simulate a single-elimination tournament with \(N\) players to determine in which round each player is eliminated.

Analysis

The tournament format in this problem follows a standard “single-elimination” structure. - \(N\) is a power of \(2\), and the number of players is halved in each round. - The player with the greater strength always wins, so the outcome of each match is uniquely determined. - As rounds progress, the winners from the previous round face each other in order.

For example, when \(N=4\): 1. Round 1: (Player 1 vs Player 2), (Player 3 vs Player 4) 2. Round 2: (Winner of the first match vs Winner of the second match)

Although \(N\) can be as large as \(2^{19} \approx 5.2 \times 10^5\), which is relatively large, if we consider the total number of matches played across all rounds: \(\frac{N}{2} + \frac{N}{4} + \dots + 1 = N-1\) The total number of matches is proportional to \(N\). Therefore, naively simulating all matches is sufficiently fast.

Algorithm

We perform the simulation with the following steps.

1. Initialization:

   • Initialize an array ans to store the elimination round for each player, filled with \(0\).
   • Prepare a list current_indices to manage the indices of players still remaining in the tournament. Initially, all players (\(0\) to \(N-1\)) are included.

2. Simulation:

   • Repeat the following process until only \(1\) player remains (let \(r\) denote the current round number).
   • Take consecutive pairs of \(2\) players from current_indices and have them compete.
   • Compare their strengths \(S\); for the player with the smaller value (the loser), record \(r\) in ans[loser].
   • Add the player with the larger value (the winner) to the list next_indices for the next round.
   • Update current_indices with next_indices and increment the round number \(r\) by \(1\).

3. Output:

   • Finally, output the ans array. The player who never lost (the champion) will remain at the initial value of \(0\).

Complexity

• Time Complexity: \(O(N)\)
  • The total number of matches in the tournament is \(N-1\). Since determining the winner of each match and appending to the list can be done in \(O(1)\), the overall complexity is \(O(N)\).
• Space Complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the players’ strengths, elimination rounds, and the list of currently remaining players.

Implementation Notes

• Index Management: Player numbers range from \(1\) to \(N\), but managing them as \(0\) to \(N-1\) to match array indexing in programming languages makes them easier to handle.

• Efficient I/O: Since \(N\) can be large, in Python, using sys.stdin.read().split() and sys.stdout.write can reduce I/O time.

  Source Code

import sys

def solve():
    # 標準入力から全てのデータを取得し、スペース区切りで分割します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N（参加人数）を取得します
    n = int(input_data[0])
    # 各選手の強さ S_1, S_2, ..., S_N をリストとして取得します
    s = list(map(int, input_data[1:]))
    
    # 各選手が敗退したラウンドを記録する配列（0で初期化、0は優勝者を意味する）
    # ans[i] は選手 i+1 の敗退ラウンドを格納します
    ans = [0] * n
    
    # 現在トーナメントに残っている選手のインデックス（0-indexed）をリストで管理します
    current_indices = list(range(n))
    
    round_num = 1
    # トーナメントの残り人数が1人になるまでシミュレーションを繰り返します
    while len(current_indices) > 1:
        next_indices = []
        # 隣り合う2人ずつを対戦させます
        # ラウンド r において、前のラウンドの第 2j-1 試合と第 2j 試合の勝者が対戦するルールに対応します
        for i in range(0, len(current_indices), 2):
            idx1 = current_indices[i]
            idx2 = current_indices[i+1]
            
            # 強さの値が大きい選手が勝ちます
            if s[idx1] > s[idx2]:
                # 選手 idx2 がこのラウンドで敗退
                ans[idx2] = round_num
                # 勝った選手 idx1 は次のラウンドへ進出
                next_indices.append(idx1)
            else:
                # 選手 idx1 がこのラウンドで敗退
                ans[idx1] = round_num
                # 勝った選手 idx2 は次のラウンドへ進出
                next_indices.append(idx2)
        
        # 次のラウンドに進む選手のリストを更新します
        current_indices = next_indices
        round_num += 1
        
    # 結果をスペース区切りで1行に出力します
    sys.stdout.write(" ".join(map(str, ans)) + "\n")

if __name__ == "__main__":
    solve()

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