Codeforces Round 817 (Div. 4)

 

Dashboard - Codeforces Round 817 (Div. 4) - Codeforces

 

G

홀수번째 index의 원소들을 모두 xor한 값을 a, 짝수번째 index의 원소들을 모두 xor한 값을 b라고 하자. 
(모든 원소를 xor한 결과가 0) iff (a=b).

따라서 모든 원소를 xor한 결과가 0이 되게 답이 되는 배열 A를 구성하자.

case1

index of array A	1	2	...	N-2	N-1	N
val	0	1	...	N-3	MSB^acc	MSB

MSB = (1<<30)
acc = A[1] ^ A[2] ^ ... ^ A[N-2]

위와 같이 배열을 구성하면 모든 원소를 xor한 결과가 0이다. 이제 모든 원소가 다른지만 확인하면 된다.
A[1...N-2]의 msb는 MSB(:= (1<<30)와 다르므로 A[N-1]와 A[N]가 다른지만 확인하면 된다.
(acc = 0) iff (A[N-1] = A[N]).

따라서 acc != 0 인 경우에 위와 같이 답을 구성하면 된다. acc = 0인 경우에는 아래와 같이 답을 구성하면 된다.

case 2

index of array A	1	2	...	N-2	N-1	N
val	1	2	...	N-2	MSB^acc	MSB

MSB = (1<<30)
acc = A[1] ^ A[2] ^ ... ^ A[N-2]