問題一覧 > 通常問題

No.1209 XOR Into You

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 48
作問者 : RhoRho / テスター : simasima_71simasima_71
11 ProblemId : 4462 / 出題時の順位表
問題文最終更新日: 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ごとの排他的論理和を表す。
ユウの目標は、操作によって数列 $A$ を数列 $B=\{B_1, B_2, ... B_N\}$ と一致させることです。
操作によって目標を達成できるかどうか判定し、達成できるならばそのときの最小の操作回数を求めてください。

入力

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