Informatica Online Judge

  2개의 순열 [2192 / 0890]

Time Limit(Test case) : 3000(ms)
Number of users who solved : 8   Total Tried : 15


The Champion of this Problem (C++) : ajou709 - 297ms / 547byte
My Best Submission (C++) : N/A

[AtCoder]

Background

길이가 $N$인 $2$개의 순열 $a$와 $b$가 주어진다.

각 순열의 값은 $a_{1}, a_{2}, ... , a_{N}$, $b_{1}, b_{2}, ... , b_{N}$ 으로 나타낸다.

$1≤i, j≤N$이 되도록 자연수 $i, j$를 고르는 방법은 $N^2$가지가 있으므로 이 $N^2$가지의 $i, j$에 대해서 $a_i + b_j$를 모두 구한다.

이 모두 구한 값을 $s_{1}, s_{2}, ... , s_{N^2}$ 라 할 때 $s_{1}$ xor $s_{2}$ xor ... xor $s_{N^2}$의 값을 구하시오.

Input

입력 형식은 다음과 같다.

$N$
$a_{1}$ $a_{2}$ ... $a_{N}$
$b_{1}$ $b_{2}$ ... $b_{N}$

[입력값의 정의역]

$1≤N≤200,000$
$0≤a_i, b_i ≤ 2^{28}-1$

[Sub-Task Info]
#1 : N≤10,000 (50%)
#2 : 추가제한요소 없음 (50%)

Output

각 원소의 합들에 대한 xor값을 출력한다.

IO Example

입력1
2
1 2
3 4

출력1
2

* 설명 : s = [ 4(1+3), 5(1+4), 5(2+3), 6(2+4) ] 가 되므로 4 xor 5 xor 5 xor 6 = 2 이므로 2를 출력한다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]