← 返回题目列表

AtCoder · cf17_final_i

I. 完整锦标赛

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

分数: 1600 点

问题陈述

2^N 玩家参加了一场锦标赛。 每个玩家都有一个唯一的ID号 1 通过 2^N。当两个玩家进行比赛时,ID较小的玩家总是获胜。

这场比赛有点特别,其中失败者不会被淘汰,以对所有玩家进行全面排名。

我们将这样的锦标赛称为 2^n 玩家a 级别完整锦标赛 n。 在一场完整的级别锦标赛中 n,选手排名如下:

  • 在完整的级别锦标赛中 0,唯一的玩家排名第一。
  • 在完整的级别锦标赛中 n\ (1 \leq n),最初全部 2^n 玩家排成一排。然后:
  • 首先从最左边的两名玩家开始,依次将玩家分为 2^{n-1} 两名玩家配对。
  • 每对进行一场比赛。获胜者进入“获胜”组,失败者进入“失败”组。
  • “获胜”组的玩家排成一排,保持前一排的相对顺序。然后就是一场完整的等级赛 n-1 的举办是为了对这些玩家进行全面排名。
  • “迷失”组的玩家也按照同样的方式排名,那么这些玩家的排名每人增加 2^{n-1}.

例如,下图显示了一场完整的级别锦标赛 3 当八名玩家按顺序排列时进行 3,4,8,6,2,1,7,5。根据最终排名排序的选手名单如下: 1,3,5,6,2,4,7,8.

高桥有一张纸,上面写着按照锦标赛最终排名排序的选手名单,但其中一些已经模糊,无法辨认。 您将按顺序获得工作表上的信息 A 长度 N。当 A_i is 1 或更大,这意味着 i排名第 3 的玩家有 ID A_i。如果 A_i is 0,表示该ID i排名第 3 的玩家丢失。

判断比赛第一阶段是否存在与表一致的有效订单。如果存在,请提供一份此类订单。

约束

  • 1 \leq N \leq 18
  • 0 \leq A_i \leq 2^N
  • 没有整数,除了 0,出现多次 A_i.

输入

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

N
A_1 A_2 ... A_{2^N}

输出

如果锦标赛第一阶段存在有效订单,则打印 首先是 YES ,然后在下一行中打印按照最终排名排序的玩家ID,中间用空格隔开。 如果没有这样的订单,则打印 NO 。


示例输入 1

3
0 3 0 6 0 0 0 8

示例输出 1

YES
3 4 8 6 2 1 7 5

这与声明中的顺序相同。


示例输入 2

1
2 1

示例输出 2

NO