No.1209 XOR Into You
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 83
作問者 :
Rho
/ テスター :
simasima_71
タグ : / 解いたユーザー数 83
作問者 :
Rho
/ テスター :
simasima_71
問題文最終更新日: 2020-08-28 18:42:40
問題文
長さ $N$ の数列 $A=\{A_1, A_2, ... A_N\}$ があります。ユウは以下の操作を何回でも行うことができます。
- 整数 $i$ $(1 \leq i \leq N-2)$ を選ぶ。$A_{i+1}$ を$A_{i}⊕A_{i+1}⊕A_{i+2}$ で置き換える。ただしここで$⊕$はbitごとの排他的論理和を表す。
操作によって目標を達成できるかどうか判定し、達成できるならばそのときの最小の操作回数を求めてください。
入力
$N$ $A_1\ A_2\ ...\ A_N$ $B_1\ B_2\ ...\ B_N$
入力は全て整数である
$3 \leq N \leq 10^5$
$0 \leq A_i, B_i < 2^{30} (1 \leq i \leq N)$
出力
操作によって問題文の目標を達成できない場合、-1を一行に出力してください。
できる場合、最小の操作回数を一行に出力してください。
最後に改行してください。
サンプル
サンプル1
入力
3 1 2 3 1 0 3
出力
1
操作を $1$ 回行うことで、数列 $A$ を $B$ と一致させることができます。
サンプル2
入力
3 1 2 3 1 4 3
出力
-1
数列 $A$ を $B$ と一致させることはできません。
サンプル3
入力
8 1 7 3 2 0 5 0 8 1 7 3 2 0 5 0 8
出力
0
最初から $A$ と $B$ が一致している場合もあります。
サンプル4
入力
8 0 1 2 3 4 5 6 7 0 3 0 1 0 1 0 7
出力
7
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。