問題一覧 > 通常問題

No.1355 AND OR GAME

レベル : / AI推定難易度 : 1800 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : （解説公開後に AC するまで非表示） / 解いたユーザー数 34
作問者 : blackyuki / テスター : KoD maguro tenorist PCTprobability
お気に入りにしたユーザー ProblemId : 5759 / 自分の提出
問題文最終更新日: 2021-03-05 20:13:41
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
灘中入試コンテストday2 (順位表) の他の問題:

Problem Statement

tenorist has a non-negative integer $X$ and a sequence $P = P_1 , P_2 , \cdots , P_N$ consisting of $N$ integers, each between $1$ and $3$, inclusive.

Separately from these, $N$ non-negative integers $A_1 , A_2 , \cdots , A_N$ are given. For each $i= 1 , 2 , \cdots , N$, in this order, tenorist performs the following operation.

  • If $P_i = 1$, replace $X$ with the bitwise AND of $X$ and $A_i$.
  • If $P_i = 2$, replace $X$ with the bitwise OR of $X$ and $A_i$.
  • If $P_i = 3$, replace $X$ with $A_i$.

Does there exist a $P$ such that the value of $X$ after the $N$ operations equals $Y$? If one exists, show one example.

writer : blackyuki, tenorist

Input

$N\ X\ Y$
$A_1\ A_2\ \ldots \ A_N$

  • All inputs are integers.
  • $1 \leq N \leq 2 \times 10^5$
  • $0 \leq A_i \leq 10^{18}$
  • $0 \leq X, Y \leq 10^{18}$

Output

If no $P$ satisfying the condition exists, print -1 on a single line. 

$-1$

If one exists, print a $P$ satisfying the condition on a single line, separated by spaces. If there are multiple such $P$, you may print any of them. 

$P_1\ P_2\ \ldots\ P_N$
Do not forget the newline at the end.

Sample

Sample 1
Input
3 3 0
2 1 4
Output
1 3 1

In this input, the initial value of $X$ is $3$ and the value of $Y$ is $0$.

When $P = \{1,3,1\}$, you first replace $X$ with $2$, the bitwise AND of $3$ and $2$.

Next, you replace $X$ with $1$.

Finally, you replace $X$ with $0$, the bitwise AND of $1$ and $4$.

Thus, the final value of $X$ is $0$. All's well that ends well.

Several other solutions are possible. You may print any of them.

Sample 2
Input
1 2 0
0
Output
3

Sample 3
Input
10 982257690615318021 816132242399997719
792469312208399382 160900413107596294 775228082263688784 172262391806149387 172451449299925557 217147622500309492 33508584223087170 827064136254818074 257775131712831174 599326141495553303
Output
1 2 1 3 1 2 1 3 1 2

Sample 4
Input
1 0 1
0
Output
-1

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