Overview

The tournament bracket is completely fixed, and “the stronger player always wins,” so we can simply advance the winners round by round.
We record “which round each player lost in” for the loser of each match, and set the answer to \(0\) for the last remaining player.

Analysis

The two key points of this problem are:

• The match result is determined by a single comparison of strengths
• The ordering in the tournament bracket is fixed from start to finish

Key Observation

In round \(1\):

• Player \(1\) vs Player \(2\)
• Player \(3\) vs Player \(4\)
• …

Then in the next round, the winners play:

• Winner of match 1 vs Winner of match 2
• Winner of match 3 vs Winner of match 4
• …

In other words, if we keep the remaining players in tournament order, we can construct the next round simply by having adjacent pairs compete against each other.

Naive Approach

For each player, we could individually consider:

• Which opponent they face
• In which round they encounter a player stronger than themselves

However, investigating this per player becomes complex and tends to lead to heavy implementations.

How to Solve It

In practice, the total number of matches in the entire tournament is only \(N-1\).
Therefore, simulating every match one by one is sufficient.

In each round:

1. Look at the current list of remaining players current
2. Compare them in pairs of two
3. Set the loser’s answer to the current round number
4. Add only the winners to nxt

Repeat this until only one player remains, and the answers are obtained.

Example

For example, with \(N=8\), suppose the survivors of the current round are:

[0, 1, 2, 3, 4, 5, 6, 7]

(0-indexed internally).

In round \(1\):

• 0 vs 1
• 2 vs 3
• 4 vs 5
• 6 vs 7

We have them compete and add only the winners to nxt in order.
Then nxt becomes exactly the lineup for the next round.

The key point is lining up the winners while preserving the order.

Algorithm

1. Prepare current = [0, 1, 2, ..., N-1]
   
   • This stores the indices of the players remaining in the current round, in order
2. Initialize ans as an array of length \(N\) filled with \(0\)
   
   • The champion is never updated, so their value naturally stays \(0\)
3. Set round_num = 1
4. Repeat the following until the length of current becomes 1:
   • Create an empty array nxt
   • Process current in pairs of two
   • Compare the strengths S[a] and S[b] of players a and b
   • Add the stronger player to nxt
   • Record round_num in the loser’s ans
   • After the round ends, set current = nxt
   • round_num += 1
5. Output ans

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Why the Time Complexity is \(O(N)\)

Each match is processed exactly once.
The total number of matches in a single-elimination tournament is:

\(N/2 + N/4 + \cdots + 1 = N-1\)

Therefore, the overall complexity is \(O(N)\).

Implementation Notes

• Store player indices in current, not their strengths
  This way:

  • Strength comparison is simply S[a] > S[b]
  • Recording answers is simply ans[a], ans[b]

• It is crucial to add winners to nxt while preserving the original order.
  If the order is disrupted, the matchups in the next round will be incorrect.

• In this code, ans is initialized entirely with \(0\) at the start, so the champion who never loses automatically remains at \(0\).

• Using array('I') helps save memory for large inputs.

  Source Code

import sys
from array import array

def main():
    input = sys.stdin.buffer.readline
    N = int(input())
    S = array('I', map(int, input().split()))
    ans = array('I', [0]) * N

    current = list(range(N))
    round_num = 1

    while len(current) > 1:
        nxt = []
        append = nxt.append
        for i in range(0, len(current), 2):
            a = current[i]
            b = current[i + 1]
            if S[a] > S[b]:
                ans[b] = round_num
                append(a)
            else:
                ans[a] = round_num
                append(b)
        current = nxt
        round_num += 1

    sys.stdout.write(' '.join(map(str, ans)))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.