問題一覧 > 通常問題

No.1652 XOR Inequalities

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 7
作問者 : 👑 chocoruskchocorusk / テスター : ei1333333ei1333333
4 ProblemId : 6697 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-08-21 00:38:43

問題文

ラスク君は長さ $2^N$ の数列 $A=(A_0, A_1, \ldots, A_{2^N-1})$ を持っています。$A$ の各要素は $-1$ または $0$ 以上 $2^{30}$ 未満の整数です。ラスク君は $A$ に含まれるすべての $-1$ をそれぞれ $0$ 以上 $2^{30}$ 未満の整数に書き換えて、次の条件を満たすようにしたいです。

  • すべての $i$, $j$ ($0\leq i, j < 2^N$) に対し $A_{i\oplus j}\geq A_i\oplus A_j$ が成り立つ。
これが可能かどうか判定し、可能ならば条件を満たす書き換え方を $1$ つ求めてください。

ただし、非負整数 $x$, $y$ に対し、$x\oplus y$ は $x$ と $y$ のビットごとの排他的論理和を表します。

入力

$N$
$A_0\ A_1\ \ldots \ A_{2^N-1}$

  • $1\leq N\leq 7$
  • $-1\leq A_i < 2^{30}$
  • 入力はすべて整数である。

出力

条件を満たすような書き換えが不可能ならば、No と出力してください。可能ならば、$1$ 行目に Yes と出力し、$2$ 行目に、条件を満たすように書き換えを行った後の $A$ の要素を空白区切りで出力してください。条件を満たす書き換え方が複数考えられる場合、どれを出力しても構いません。

サンプル

サンプル1
入力
2
2 -1 -1 6
出力
Yes
2 7 3 6

例えば $A_1=7$, $A_2=3$ とすると、すべての $i$, $j$ ($0\leq i, j< 4$) に対し $A_{i\oplus j}\geq A_i\oplus A_j$ を満たします。

サンプル2
入力
3
-1 4 -1 5 9 2 6 5
出力
No

$A_0$ と $A_2$ をどのように書き換えても $A_5< A_1\oplus A_4$ なので条件を満たしません。

サンプル3
入力
3
3 -1 -1 7 -1 -1 -1 10
出力
Yes
3 22 18 7 15 26 30 10

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。