No.1355 AND OR GAME
タグ : / 解いたユーザー数 34
作問者 :
blackyuki
/ テスター :
KoD
maguro
tenorist
PCTprobability
問題文
tenorist 君は非負整数 $X$ と $1$ 以上 $3$ 以下の整数 $N$ 個からなる数列 $P = P_1 , P_2 , \cdots , P_N$ を持っています。
またこれとは別に $N$ 個の非負整数 $A_1 , A_2 , \cdots , A_N$ が与えられます。 tenorist 君は各 $i= 1 , 2 , \cdots , N$ に対してこの順番に以下の処理を行います。
- $P_i = 1$ ならば、 $X$ を $X$ と $A_i$ のビットごとの論理積に置き換える
- $P_i = 2$ ならば、 $X$ を $X$ と $A_i$ のビットごとの論理和に置き換える
- $P_i = 3$ ならば、 $X$ を $A_i$ に置き換える
$N$ 回の処理が終わった後の $X$ の値が $Y$ に等しくなるような $P$ は存在しますか？存在するならば一例を示してください。
writer : blackyuki、tenorist
入力
$N\ X\ Y$ $A_1\ A_2\ \ldots \ A_N$
- 入力はすべて整数である。
- $1 \leq N \leq 2 \times 10^5$
- $0 \leq A_i \leq 10^{18}$
- $0 \leq X, Y \leq 10^{18}$
出力
条件を満たす $P$ が存在しない場合は -1 と一行に出力してください。
$-1$
存在する場合は条件を満たす $P$ を空白区切りで一行に出力してください。条件を満たす $P$ が複数存在する場合、どれを出力しても構いません。
$P_1\ P_2\ \ldots\ P_N$最後に改行を忘れないでください。
サンプル
サンプル1
入力
3 3 0 2 1 4
出力
1 3 1
この入力では、 $X$ の初期値は $3$、$Y$ の値は $0$ です。
$P = \{1,3,1\}$ のとき、あなたはまず $X$ を $3$ と $2$ のビットごとの論理積である $2$ に置き換えます。
次に $X$ を $1$ に置き換えます。
最後に $X$ を $1$ と $4$ のビットごとの論理積である $0$ に置き換えます。
よって $X$ の最終的な値は $0$ となりました。めでたし、めでたし。
ほかにも解は複数考えられます。どれを出力しても構いません。
サンプル2
入力
1 2 0 0
出力
3
サンプル3
入力
10 982257690615318021 816132242399997719 792469312208399382 160900413107596294 775228082263688784 172262391806149387 172451449299925557 217147622500309492 33508584223087170 827064136254818074 257775131712831174 599326141495553303
出力
1 2 1 3 1 2 1 3 1 2
サンプル4
入力
1 0 1 0
出力
-1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。