問題一覧 > 通常問題

No.1355 AND OR GAME

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 33
作問者 : blackyukiblackyuki / テスター : KoDKoD maguromaguro tenoristtenorist PCTprobabilityPCTprobability
7 ProblemId : 5759 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-03-05 20:13:41

問題文

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もしくは右上の雲マークをクリックしてアカウントを作成してください。