← 返回题目列表

AtCoder · past202004_i

I. 消除

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

分数: 6 点

警告

2020 年 5 月 2 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。

考试结束后,您可以向其他人透露您的总分和等级,但仅此而已(例如,您解决了哪些问题)。

问题陈述

2^N 具有整数 ID 的玩家 - 玩家 1,玩家 2, ..., 玩家 2^N - 排成一排,进行淘汰赛,如下:

  • 圆形 1:对于每个 i 这样 1 \leq i \leq 2^{N-1},玩家 2i-1 和玩家 2i 战斗,直到其中一人获胜并生存。
  • 圆形 i (i \geq 2): 玩家在回合中幸存 i-1 按照ID升序排列。然后,对于每个 左边的第 i 这样 1 \leq i \leq 2^{N-i}, (2i-1)和第 $(2i) 个玩家战斗,直到其中一人获胜并生存。

虽然每场战斗的记录现已丢失,但我们的记录表明玩家的实力 i 是 A_i。在这里,当两个玩家战斗时,力量较大的玩家获胜。

对于每个玩家,找到该玩家战斗的最后一轮。

约束

  • 1 \leq N \leq 16
  • 1 \leq A_i \leq 2^N
  • 的元素 A 是不同的。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \cdots A_{2^N}

输出

打印 2^N。的 i- 第行应包含代表玩家最后一轮的整数 i 战斗。


示例输入 1

2
2 4 3 1

示例输出 1

1
2
2
1
  • 圆形 1:玩家 2 (强度: 4) 与玩家战斗 1 (强度: 2)并获胜。还有,玩家 3 (强度: 3) 与玩家战斗 4 (强度: 1)并获胜。
  • 圆形 2:玩家 2 与玩家战斗 3 并获胜。

因此,玩家的最后几轮 1,2,3,4 战斗是圆形 1,2,2,1。


示例输入 2

1
2 1

示例输出 2

1
1

只有两名玩家,在这种情况下回合 1 是他们俩的最后一轮。


示例输入 3

3
4 7 5 1 6 3 2 8

示例输出 3

1
3
2
1
2
1
1
3