分数: 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