No.1209 XOR Into You
タグ : / 解いたユーザー数 105
作問者 :
Rho
/ テスター :
simasima_71
Problem Statement
There is a sequence $A=\{A_1, A_2, ... A_N\}$ of length $N$. Yu can perform the following operation any number of times.
- Choose an integer $i$ $(1 \leq i \leq N-2)$. Replace $A_{i+1}$ with $A_{i}⊕A_{i+1}⊕A_{i+2}$, where $⊕$ denotes bitwise exclusive OR.
Determine whether the goal can be achieved through operations, and if it can, find the minimum number of operations required.
Input
$N$ $A_1\ A_2\ ...\ A_N$ $B_1\ B_2\ ...\ B_N$
All inputs are integers.
$3 \leq N \leq 10^5$
$0 \leq A_i, B_i < 2^{30} (1 \leq i \leq N)$
Output
If the goal described in the problem statement cannot be achieved through operations, print -1 on a single line.
Otherwise, print the minimum number of operations on a single line.
Print a newline at the end.
Sample
Sample 1
Input
3 1 2 3 1 0 3
Output
1
By performing the operation $1$ time, the sequence $A$ can be made equal to $B$.
Sample 2
Input
3 1 2 3 1 4 3
Output
-1
The sequence $A$ cannot be made equal to $B$.
Sample 3
Input
8 1 7 3 2 0 5 0 8 1 7 3 2 0 5 0 8
Output
0
$A$ and $B$ may already be equal from the beginning.
Sample 4
Input
8 0 1 2 3 4 5 6 7 0 3 0 1 0 1 0 7
Output
7
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。