/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
非負整数からなる長さ N の数列 a=\{a_0,\ldots,a_{N-1}\} と b=\{b_0,\ldots,b_{N-1}\} が与えられます。
すぬけ君は 0 \leq k < N を満たす整数 k と、0 以上の整数 x を決めて、新しく長さ N の数列 a'=\{a_0',\ldots,a_{N-1}'\} を次のようにして作ります。
- a_i'= a_{i+k \mod N}\ XOR \ x
a' が b と等しくなるような (k,x) の組を全て求めてください。
\text{ XOR } とは
整数 A, B のビットごとの排他的論理和 a \text{ XOR } b は、以下のように定義されます。
- A \text{ XOR } B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
制約
- 1 \leq N \leq 2 \times 10^5
- 0 \leq a_i,b_i < 2^{30}
- 入力中のすべての値は整数である。
入力
入力は以下の形式で標準入力から与えられる。
N
a_0 a_1 ... a_{N-1}
b_0 b_1 ... b_{N-1}
出力
a' と b が等しくなるような (k,x) の組を、1 行に 1 組ずつ、k の昇順 (k が等しいものは x の昇順) にすべて出力せよ。
このような組が存在しない場合の出力は空でよい。
入力例 1
3 0 2 1 1 2 3
出力例 1
1 3
(k,x)=(1,3) のとき、
-
a_0'=(a_1\ XOR \ 3)=1
-
a_1'=(a_2\ XOR \ 3)=2
-
a_2'=(a_0\ XOR \ 3)=3
となり、a' は b と等しくなります。
入力例 2
5 0 0 0 0 0 2 2 2 2 2
出力例 2
0 2 1 2 2 2 3 2 4 2
入力例 3
6 0 1 3 7 6 4 1 5 4 6 2 3
出力例 3
2 2 5 5
入力例 4
2 1 2 0 0
出力例 4
条件を満たすような組が存在しないこともあります。
Score : 600 points
Problem Statement
Given are two sequences a=\{a_0,\ldots,a_{N-1}\} and b=\{b_0,\ldots,b_{N-1}\} of N non-negative integers each.
Snuke will choose an integer k such that 0 \leq k < N and an integer x not less than 0, to make a new sequence of length N, a'=\{a_0',\ldots,a_{N-1}'\}, as follows:
- a_i'= a_{i+k \mod N}\ XOR \ x
Find all pairs (k,x) such that a' will be equal to b.
What is \text{ XOR }?
The XOR of integers A and B, A \text{ XOR } B, is defined as follows:
- When A \text{ XOR } B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if either A or B, but not both, has 1 in the 2^k's place, and 0 otherwise.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 0 \leq a_i,b_i < 2^{30}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
a_0 a_1 ... a_{N-1}
b_0 b_1 ... b_{N-1}
Output
Print all pairs (k, x) such that a' and b will be equal, using one line for each pair, in ascending order of k (ascending order of x for pairs with the same k).
If there are no such pairs, the output should be empty.
Sample Input 1
3 0 2 1 1 2 3
Sample Output 1
1 3
If (k,x)=(1,3),
-
a_0'=(a_1\ XOR \ 3)=1
-
a_1'=(a_2\ XOR \ 3)=2
-
a_2'=(a_0\ XOR \ 3)=3
and we have a' = b.
Sample Input 2
5 0 0 0 0 0 2 2 2 2 2
Sample Output 2
0 2 1 2 2 2 3 2 4 2
Sample Input 3
6 0 1 3 7 6 4 1 5 4 6 2 3
Sample Output 3
2 2 5 5
Sample Input 4
2 1 2 0 0
Sample Output 4
No pairs may satisfy the condition.