/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 1600 点
問題文
2^N 人の選手でトーナメント戦を行いました。 各選手には 1 〜 2^N の番号がついており、2 人が対戦したときは番号が小さい方の選手が必ず勝ちます。
行ったトーナメント戦は少し変わっていて、敗者どうしも対戦をすることで全員の順位を決めるものでした。
ここで、2^n 人で行うこのようなトーナメント戦を「レベル n のフルトーナメント」と呼ぶことにします。 レベル n のフルトーナメントの順位は以下のように決定されます。
- レベル 0 のフルトーナメントでは参加者が 1 人であり、この人が 1 位となる。
- レベル n\ (1 \leq n) のフルトーナメントは、2^n 人の選手が横 1 列に並んだ状態から始まり、以下のように順位を決定する。
- まず、端から 2 人ずつに区切り、2^{n-1} 組の 2 人組を作る。
- それぞれの 2 人組で対戦を行い、勝った方が勝ちグループに、負けた方が負けグループに入る。
- 勝ちグループに入った選手を元の列での順序を保ったまま並べ、レベル n-1 のフルトーナメントを行い、各選手の順位を決定する。
- 負けグループについても同様に順位をつけ、その後に負けグループの各選手の順位に 2^{n-1} を足す。
例えば、8 人の選手を 3,4,8,6,2,1,7,5 の順に並べてレベル 3 のフルトーナメントを行うと下図のようにトーナメントが行われ、結果の順位順に選手を並べると 1,3,5,6,2,4,7,8 となります。
高橋君は、選手の番号をトーナメントの結果の順位順に書いた紙を持っていましたが、いくつかの場所が汚れて読めなくなってしまいました。 この紙の情報は長さ N の数列 A として与えられ、A_i が 1 以上のときは i 位の選手の番号が A_i であったことを表し、0 のときは i 位の選手の番号が分からなくなってしまったことを表します。
最初の選手の並び順として考えられるものが存在するかどうかを判定し、存在するならば例を 1 つ答えてください。
制約
- 1 \leq N \leq 18
- 0 \leq A_i \leq 2^N
- A_i には 0 以外の整数は重複して含まれていない。
入力
入力は以下の形式で標準入力から与えられる。
N
A_1 A_2 ... A_{2^N}
出力
最初の選手の並び順として考えられるものが存在する場合は YES と出力し、2 行目に選手の番号を順番に空白区切りで出力せよ。
存在しない場合は代わりに 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
Score : 1600 points
Problem Statement
2^N players competed in a tournament. Each player has a unique ID number from 1 through 2^N. When two players play a match, the player with the smaller ID always wins.
This tournament was a little special, in which losers are not eliminated to fully rank all the players.
We will call such a tournament that involves 2^n players a full tournament of level n. In a full tournament of level n, the players are ranked as follows:
- In a full tournament of level 0, the only player is ranked first.
- In a full tournament of level n\ (1 \leq n), initially all 2^n players are lined up in a row. Then:
- First, starting from the two leftmost players, the players are successively divided into 2^{n-1} pairs of two players.
- Each of the pairs plays a match. The winner enters the "Won" group, and the loser enters the "Lost" group.
- The players in the "Won" group are lined up in a row, maintaining the relative order in the previous row. Then, a full tournament of level n-1 is held to fully rank these players.
- The players in the "Lost" group are also ranked in the same manner, then the rank of each of these players increases by 2^{n-1}.
For example, the figure below shows how a full tournament of level 3 progresses when eight players are lined up in the order 3,4,8,6,2,1,7,5. The list of the players sorted by the final ranking will be 1,3,5,6,2,4,7,8.
Takahashi has a sheet of paper with the list of the players sorted by the final ranking in the tournament, but some of it blurred and became unreadable. You are given the information on the sheet as a sequence A of length N. When A_i is 1 or greater, it means that the i-th ranked player had the ID A_i. If A_i is 0, it means that the ID of the i-th ranked player is lost.
Determine whether there exists a valid order in the first phase of the tournament which is consistent with the sheet. If it exists, provide one such order.
Constraints
- 1 \leq N \leq 18
- 0 \leq A_i \leq 2^N
- No integer, except 0, occurs more than once in A_i.
Input
Input is given from Standard Input in the following format:
N
A_1 A_2 ... A_{2^N}
Output
If there exists a valid order in the first phase of the tournament, print YES first, then in the subsequent line, print the IDs of the players sorted by the final ranking, with spaces in between.
If there is no such order, print NO instead.
Sample Input 1
3 0 3 0 6 0 0 0 8
Sample Output 1
YES 3 4 8 6 2 1 7 5
This is the same order as the one in the statement.
Sample Input 2
1 2 1
Sample Output 2
NO