← 返回题目列表

AtCoder · awc0085_a

A. 锦标赛淘汰赛

中文机器翻译题面 查看原题

分数: 266 分

问题陈述

举行单败淘汰赛 N 玩家。在这里, N 是 2.

每个玩家都被分配了一个号码 1 to N,以及玩家的实力 i is S_i。所有玩家都有独特的优势,在任何比赛中,力量值较大的玩家总是获胜。输掉比赛的玩家将被淘汰,比赛继续进行,直到决出冠军为止。

自从 N 是 2,比赛包括 R = \log_2 N 回合。每轮比赛的对阵确定如下:

  • 圆形 1: 玩家 2i-1 和玩家 2i 互相对战。这就是所谓的匹配 i 圆 1 (i = 1, 2, \ldots, N/2).
  • 圆形 r (r \geq 2): 比赛获胜者 2j-1 和比赛获胜者 2j 上一轮(轮 r-1) 互相对抗。这就是所谓的匹配 j 圆 r (j = 1, 2, \ldots, N/2^r).

每轮比赛号码从 1 每轮都会重新分配。回合中 R,只有一场比赛,获胜者就是冠军。

对于每个玩家,确定该玩家被击败的轮数。然而,由于冠军从未被击败,输出 0 为冠军。回合编号从 1.

约束

  • 2 \leq N \leq 2^{19}
  • N 是 2
  • 1 \leq S_i \leq N (1 \leq i \leq N)
  • 全部 S_i 是不同的
  • 所有输入值均为整数

输入

N
S_1 S_2 \ldots S_N

第一行给出玩家数量 N.

第二行给出了优点 每个玩家的 S_1, S_2, \ldots, S_N ,以空格分隔。

输出

输出 N 单行上用空格分隔的整数。的 i-th 值是玩家所在的回合数 i 被击败。为了冠军,输出 0.


示例输入 1

4
1 4 3 2

示例输出 1

1 0 2 1

示例输入 2

8
8 1 6 2 5 3 7 4

示例输出 2

0 1 2 1 2 1 3 1

示例输入 3

16
5 12 1 16 9 3 14 7 10 2 15 6 13 4 11 8

示例输出 3

1 2 1 0 2 1 3 1 2 1 4 1 3 1 2 1

示例输入 4

32
32 1 24 9 16 17 8 25 31 2 23 10 15 18 7 26 30 3 22 11 14 19 6 27 29 4 21 12 13 20 5 28

示例输出 4

0 1 2 1 1 2 1 3 4 1 2 1 1 2 1 3 5 1 2 1 1 2 1 3 4 1 2 1 1 2 1 3

示例输入 5

2
1 2

示例输出 5

1 0