Problem:


Score : 600 points

Problem Statement

There are N piles of stones. The i-th pile has A_i stones.

Aoki and Takahashi are about to use them to play the following game:

Starting with Aoki, the two players alternately do the following operation:

Operation: Choose one pile of stones, and remove one or more stones from it.

When a player is unable to do the operation, he loses, and the other player wins.

When the two players play optimally, there are two possibilities in this game: the player who moves first always wins, or the player who moves second always wins, only depending on the initial number of stones in each pile.

In such a situation, Takahashi, the second player to act, is trying to guarantee his win by moving at least zero and at most (A_1 - 1) stones from the 1-st pile to the 2-nd pile before the game begins.

If this is possible, print the minimum number of stones to move to guarantee his victory; otherwise, print -1 instead.

Constraints

2 \leq N \leq 300

1 \leq A_i \leq 10^{12}

Input

Input is given from Standard Input in the following format:

N
A_1 \ldots A_N

Output

Print the minimum number of stones to move to guarantee Takahashi's win; otherwise, print -1 instead.

Sample Input 1

2
5 3

Sample Output 1

1

Without moving stones, if Aoki first removes 2 stones from the 1-st pile, Takahashi cannot win in any way.

If Takahashi moves 1 stone from the 1-st pile to the 2-nd before the game begins so that both piles have 4 stones, Takahashi can always win by properly choosing his actions.

Sample Input 2

2
3 5

Sample Output 2

-1

It is not allowed to move stones from the 2-nd pile to the 1-st.

Sample Input 3

3
1 1 2

Sample Output 3

-1

It is not allowed to move all stones from the 1-st pile.

Sample Input 4

8
10 9 8 7 6 5 4 3

Sample Output 4

3

Sample Input 5

3
4294967297 8589934593 12884901890

Sample Output 5

1

Watch out for overflows.



Sample input:
2
5 3


Sample output:
1

Submission status: Wrong Answer

Solution code:
n = int(input())
l = list(map(int,input().split()))

x = 0
s = l[0]+l[1]
for i in l[2:]:
    x ^= i
if x > s or (s-x)%2 or ((s-x)//2)&x:
    print(-1)
    exit()
a = (s-x)//2
for i in range(50,-1,-1):
    if 1<<i & x:
        if a+ (1<<i) <= l[0]:
            a += 1<<i
if a == 0:
    print(-1)
else:
    print(l[0]-a)

Submission status: Wrong Answer

Solution code:
n = int(input())
l = list(map(int,input().split()))

x = 0
s = l[0]+l[1]
for i in l[2:]:
    x ^= i
if (s-x)%2 or ((s-x)//2)&x:
    print(-1)
    exit()
a = (s-x)//2
for i in range(50,-1,-1):
    if 1<<i & x:
        if a+ (1<<i) <= l[0]:
            a += 1<<i
if a == 0:
    print(-1)
else:
    print(l[0]-a)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
s = a[0]+a[1]
x = 0
for i in range(2,n):
    x ^= a[i]
aa = (s-x)>>1
if aa>a[0]:
    print(-1)
else:
    y = 0
    for i in range(61):
        bit = 1<<i
        if (bit&x) == 0:
            continue
        if (y+bit)^aa <= a[0]:
            y += bit
    ans = a[0]-(y^aa)
    if ans==a[0]:
        print(-1)
    else:
        print(ans)

Submission status: Wrong Answer

Solution code:
def compute(S, X): 
  A = (S - X)//2
  a = 0
  ambiguous=[0]*64
  for i in range(63,-1,-1): 
    Xi = (X & (1 << i)) 
    Ai = (A & (1 << i)) 
    if (Xi == 0 and Ai == 0): 
      pass
    elif (Xi == 0 and Ai > 0): 
      a = ((1 << i) | a)
    elif (Xi > 0 and Ai == 0): 
      ambiguous[i]=1
    else:
      print(-1) 
      return
  for i in range(63,-1,-1):
    if ambiguous[i]==1:
      R=((1 << i) | a) 
      if R<=a1[0]:
        a=R
      else:
        a = ((0 << i) | a)
  if a>a1[0]:
    print(-1)
  else:
    if a==0 and a1[0]!=0:
      print(-1)
    else:
      print(a1[0]-a)
    
  
import sys
n=int(input())
a1=list(map(int,input().split()))
nimsum=0
for i in range(2,n):
  nimsum=a1[i]^nimsum
compute(a1[0]+a1[1],nimsum)

Submission status: Wrong Answer

Solution code:
def compute(S, X): 
  A = (S - X)//2
  a = 0
  ambiguous=[0]*64
  for i in range(63,-1,-1): 
    Xi = (X & (1 << i)) 
    Ai = (A & (1 << i)) 
    if (Xi == 0 and Ai == 0): 
      pass
    elif (Xi == 0 and Ai > 0): 
      a = ((1 << i) | a)
    elif (Xi > 0 and Ai == 0): 
      ambiguous[i]=1
    else:
      print(-1) 
      return
  for i in range(63,-1,-1):
    if ambiguous[i]==1:
      R=((1 << i) | a) 
      if R<=a1[0]:
        a=R
      else:
        a = ((0 << i) | a)
  if a>a1[0]:
    print(-1)
  else:
    print(a1[0]-a)
  
import sys
n=int(input())
a1=list(map(int,input().split()))
nimsum=0
for i in range(2,n):
  nimsum=a1[i]^nimsum
compute(a1[0]+a1[1],nimsum)

Submission status: Wrong Answer

Solution code:
import sys
N, = map(int, input().split())
X = list(map(int, input().split()))
S = X[0]+X[1]
T = 0
for i in range(2, N):
    T ^= X[i]
if S<T or (S-T)%2:
    print(-1)
    sys.exit()

D = (S-T)//2
if D&T:
    print(-1)
    sys.exit()

Y = D
for i in range(T.bit_length()+1, -1, -1):
    if T&(1<<i)|Y <= X[0]:
        Y |= 1<<i
if 0<Y<=X[0]:
    print(X[0]-Y)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from sys import exit
n = int(input())
a = list(map(int, input().split()))
X = 0
for i in range(2, n):
	X ^= a[i]
A = (a[0] + a[1] - X) // 2
if (a[0] + a[1] - X) != A * 2 or A > a[0] or A < 0 or X & A: 
	print(-1)
	exit()
res = 0
flg = False
for i in range(42, -1, -1):
	if flg:
		if (A >> i) & 1 or (X >> i) & 1:
			res += (1<<i)
	else:
		if (a[0] >> i) & 1 == 0:
			if (A >> i) & 1 == 1:
				for j in range(i+1, 43):
					if (a[0] >> j) & 1 == 1 and (A >> j) & 1 == 0:
						res -= (1 << j)
						for k in range(j-1, i-1, -1):
							res |= (1 << k)
						break
				flg = True
		else:
			if (A >> i) & 1 or (X >> i) & 1:
				res += (1 << i)
			else:
				flg = True
if res == 0:
	print(-1)
	exit()
print(a[0]-res)

Submission status: Wrong Answer

Solution code:
from sys import exit
n = int(input())
a = list(map(int, input().split()))
X = 0
for i in range(2, n):
	X ^= a[i]
A = (a[0] + a[1] - X) // 2
if (a[0] + a[1] - X) != A * 2:
	print(-1)
	exit()
if A > a[0]:
	print(-1)
	exit()
if X & A:
	print(-1)
	exit()
res = 0
flg = False
for i in range(42, -1, -1):
	if flg:
		if (A >> i) & 1 or (X >> i) & 1:
			res += (1<<i)
	else:
		if (a[0] >> i) & 1 == 0:
			if (A >> i) & 1 == 1:
				for j in range(i+1, 43):
					if (a[0] >> j) & 1 == 1 and (A >> j) & 1 == 0:
						res -= (1 << j)
						for k in range(j-1, i-1, -1):
							res |= (1 << k)
						break
				flg = True
		else:
			if (A >> i) & 1 or (X >> i) & 1:
				res += (1 << i)
			else:
				flg = True
if res == 0:
	print(-1)
	exit()
print(a[0]-res)

Submission status: Wrong Answer

Solution code:
from sys import exit
n = int(input())
a = list(map(int, input().split()))
X = 0
for i in range(2, n):
	X ^= a[i]
A = (a[0] + a[1] - X) // 2
if A > a[0]:
	print(-1)
	exit()
if X & A:
	print(-1)
	exit()
res = 0
flg = False
for i in range(42, -1, -1):
	if flg:
		if (A >> i) & 1 or (X >> i) & 1:
			res += (1<<i)
	else:
		if (a[0] >> i) & 1 == 0:
			if (A >> i) & 1 == 1:
				for j in range(i+1, 43):
					if (a[0] >> j) & 1 == 1 and (A >> j) & 1 == 0 and (X >> j) & 1 == 1:
						res -= (1 << j)
						for k in range(j-1, i-1, -1):
							res |= (1 << k)
						break
				flg = True
		else:
			if (A >> i) & 1 or (X >> i) & 1:
				res += (1 << i)
			else:
				flg = True
if res == 0:
	print(-1)
	exit()
print(a[0]-res)

Submission status: Wrong Answer

Solution code:
from sys import exit
n = int(input())
a = list(map(int, input().split()))
X = 0
for i in range(2, n):
	X ^= a[i]
A = (a[0] + a[1] - X) // 2
if A > a[0]:
	print(-1)
	exit()
if X & A:
	print(-1)
	exit()
res = 0
flg = False
for i in range(42, -1, -1):
	if flg:
		if (A >> i) & 1 or (X >> i) & 1:
			res += (1<<i)
	else:
		if (a[0] >> i) & 1 == 0:
			if (A >> i) & 1 == 1:
				for j in range(i+1, 43):
					if (a[0] >> j) & 1 == 1 and (A >> j) & 1 == 0:
						res -= (1 << j)
						for k in range(j-1, i-1, -1):
							res |= (1 << k)
						break
				flg = True
		else:
			if (A >> i) & 1 or (X >> i) & 1:
				res += (1 << i)
			else:
				flg = True
if res == 0:
	print(-1)
	exit()
print(a[0]-res)

Submission status: Wrong Answer

Solution code:
from sys import exit
n = int(input())
a = list(map(int, input().split()))
X = 0
for i in range(2, n):
	X ^= a[i]
A = (a[0] + a[1] - X) // 2
if A > a[0]:
	print(-1)
	exit()
if X & A:
	print(-1)
	exit()
res = 0
flg = False
a[0] -= 1
for i in range(42, -1, -1):
	if flg:
		if (A >> i) & 1 or (X >> i) & 1:
			res += (1<<i)
	else:
		if (a[0] >> i) & 1 == 0:
			if (A >> i) & 1 == 1:
				for j in range(i+1, 43):
					if (a[0] >> j) & 1 == 1 and (A >> j) & 1 == 0:
						res -= (1 << j)
						for k in range(j-1, i-1, -1):
							res |= (1 << k)
						break
				flg = True
		else:
			if (A >> i) & 1 or (X >> i) & 1:
				res += (1 << i)
			else:
				flg = True
if res == 0:
	print(-1)
	exit()
print(a[0]-res+1)

Submission status: Wrong Answer

Solution code:
from sys import exit
n = int(input())
a = list(map(int, input().split()))
X = 0
for i in range(2, n):
	X ^= a[i]
A = (a[0] + a[1] - X) // 2
if A > a[0]:
	print(-1)
	exit()
if X & A:
	print(-1)
	exit()
res = 0
flg = False
a[0] -= 1
for i in range(42, -1, -1):
	if flg:
		if (A >> i) & 1 or (X >> i) & 1:
			res += (1<<i)
	else:
		if (a[0] >> i) & 1 == 0:
			if (A >> i) & 1 == 1:
				res -= (1 << (i+1))
				res += (1 << i)
				flg = True
		else:
			if (A >> i) & 1 or (X >> i) & 1:
				res += (1 << i)
			else:
				flg = True
if res == 0:
	print(-1)
	exit()
print(a[0]-res+1)

Submission status: Wrong Answer

Solution code:
import sys
N, = map(int, input().split())
X = list(map(int, input().split()))
S = X[0]+X[1]
T = 0
for i in range(2, N):
    T ^= X[i]
if S<T or (S-T)%2:
    print(-1)
    sys.exit()
D = (S-T)//2
if D&T:
    print(-1)
    sys.exit()
M = T.bit_length()+1
if D > X[0]:
    print(-1)
    sys.exit()
Y = 0
for i in range(M, -1, -1):
    if T & (1<<i) and ((1<<i)|Y)^D <= X[0]:
        Y = (1<<i)|Y
if Y == 0:
    print(-1)
else:
    print(X[0]-(Y^D))

Submission status: Wrong Answer

Solution code:
from sys import exit
n = int(input())
a = list(map(int, input().split()))
X = 0
for i in range(2, n):
	X ^= a[i]
A = (a[0] + a[1] - X) // 2
if A > a[0]:
	print(-1)
	exit()
if X & A:
	print(-1)
	exit()
res = 0
flg = False
a[0] -= 1
for i in range(40, -1, -1):
	if flg:
		if (A >> i) & 1 or (X >> i) & 1:
			res += (1<<i)
	else:
		if (a[0] >> i) & 1 == 0:
			if (A >> i) & 1 == 1:
				res -= (1 << (i+1))
				res += (1 << i)
				flg = True
		else:
			if (A >> i) & 1 or (X >> i) & 1:
				res += (1 << i)
			else:
				flg = True
if res == 0:
	print(-1)
	exit()
print(a[0]-res+1)

Submission status: Wrong Answer

Solution code:
from sys import exit
n = int(input())
a = list(map(int, input().split()))
X = 0
for i in range(2, n):
	X ^= a[i]
A = (a[0] + a[1] - X) // 2
if A > a[0]:
	print(-1)
	exit()
if X & A:
	print(-1)
	exit()
res = 0
flg = False
a[0] -= 1
for i in range(40, -1, -1):
	if flg:
		if (A >> i) & 1 or (X >> i) & 1:
			res += (1<<i)
	else:
		if (a[0] >> i) & 1 == 0:
			if (A >> i) & 1 == 1:
				res -= (1 << (i+1))
				res += (1 << i)
				flg = True
		elif (A >> i) & 1 or (X >> i) & 1:
			res += (1 << i)
if res == 0:
	print(-1)
	exit()
print(a[0]-res+1)

Submission status: Wrong Answer

Solution code:
print(-1)

Submission status: Wrong Answer

Solution code:
from sys import exit
n = int(input())
a = list(map(int, input().split()))
X = 0
for i in range(2, n):
	X ^= a[i]
A = (a[0] + a[1] - X) // 2
if A > a[0]:
	print(-1)
	exit()
if X & A:
	print(-1)
	exit()
res = 0
flg = False
a[0] -= 1
for i in range(40, -1, -1):
	if flg:
		res += (1<<i)
	else:
		if (a[0] >> i) & 1 == 0:
			if (A >> i) & 1 == 1:
				res -= (1 << (i+1))
				if res < 0:
					print(-1)
					exit()
				res += (1 << i)
				flg = True
		else:
			res += (1 << i)
if res == 0:
	print(-1)
	exit()
print(a[0]-res+1)

Submission status: Wrong Answer

Solution code:
import sys
N, = map(int, input().split())
X = list(map(int, input().split()))
S = X[0]+X[1]
T = 0
for i in range(2, N):
    T ^= X[i]
if S<T or (S-T)%2:
    print(-1)
    sys.exit()
D = (S-T)//2
if D&T:
    print(-1)
    sys.exit()
M = S.bit_length()+1
if D > X[0]:
    print(-1)
    sys.exit()
a = 0
for i in range(M, -1, -1):
    if (T >> i)&1 and ((1<<i)|a)^D <= X[0]:
        a = (1<<i)|a
if a == 0:
    print(-1)
else:
    print(X[0]-a)

Submission status: Wrong Answer

Solution code:
from sys import exit
n = int(input())
a = list(map(int, input().split()))
X = 0
for i in range(2, n):
	X ^= a[i]
A = (a[0] + a[1] - X) // 2
if X & A:
	print(-1)
	exit()
res = 0
flg = False
a[0] -= 1
for i in range(40, -1, -1):
	if flg:
		res += (1<<i)
	else:
		if (a[0] >> i) & 1 == 0:
			if (A >> i) & 1 == 1:
				res -= (1 << (i+1))
				res += (1 << i)
				flg = True
		else:
			res += (1 << i)
if res == 0:
	print(-1)
	exit()
print(a[0]-res+1)

Submission status: Wrong Answer

Solution code:
from sys import exit
n = int(input())
a = list(map(int, input().split()))
X = 0
for i in range(2, n):
	X ^= a[i]
A = (a[0] + a[1] - X) // 2
if A > a[0]:
	print(-1)
	exit()
if X & A:
	print(-1)
	exit()
res = 0
flg = False
a[0] -= 1
for i in range(40, -1, -1):
	if flg:
		res += (1<<i)
	else:
		if (a[0] >> i) & 1 == 0:
			if (A >> i) & 1 == 1:
				res -= (1 << (i+1))
				res += (1 << i)
				flg = True
		else:
			res += (1 << i)
if res == 0:
	print(-1)
	exit()
print(a[0]-res+1)

Submission status: Wrong Answer

Solution code:
import sys
N, = map(int, input().split())
X = list(map(int, input().split()))
S = X[0]+X[1]
T = 0
for i in range(2, N):
    T ^= X[i]
if S<T or (S-T)%2:
    print(-1)
    sys.exit()
D = (S-T)//2
if D&T:
    print(-1)
    sys.exit()
M = S.bit_length()+1
a = 0
if D > X[0]:
    print(-1)
    sys.exit()
for i in range(M, -1, -1):
    if (T >> i)&1 and ((1<<i)|a)^D <= X[0]:
        a = (1<<i)|a
if a^D == 0:
    print(-1)
else:
    print(X[0]-a^D)

Submission status: Wrong Answer

Solution code:
import sys
N, = map(int, input().split())
X = list(map(int, input().split()))
S = X[0]+X[1]
T = 0
for i in range(2, N):
    T ^= X[i]
if S<T or (S-T)%2:
    print(-1)
    sys.exit()
D = (S-T)//2
if D&T:
    print(-1)
    sys.exit()
M = 60
a = 0
if D > X[0]:
    print(-1)
    sys.exit()
for i in range(M, -1, -1):
    if (T >> i)&1 and ((1<<i)|a)^D <= X[0]:
        a = (1<<i)|a
if a^D == 0:
    print(-1)
else:
    print(X[0]-a^D)

Submission status: Wrong Answer

Solution code:
import sys
N, = map(int, input().split())
X = list(map(int, input().split()))
S = X[0]+X[1]
T = 0
for i in range(2, N):
    T ^= X[i]
if S<T or (S-T)%2:
    print(-1)
    sys.exit()
D = (S-T)//2
if D&T:
    print(-1)
    sys.exit()
M = 60
a = 0
for i in range(M, -1, -1):
    if (T >> i)&1 and ((1<<i)|a)^D <= X[0]:
        a = (1<<i)|a
if X[0]-a^D >= X[0]:
    print(-1)
else:
    print(X[0]-a^D)

Submission status: Wrong Answer

Solution code:
import sys
N, = map(int, input().split())
X = list(map(int, input().split()))
S = X[0]+X[1]
T = 0
for i in range(2, N):
    T ^= X[i]
if S<T or (S-T)%2:
    print(-1)
    sys.exit()
D = (S-T)//2
if D&T:
    print(-1)
    sys.exit()
M = 60
a = 0
for i in range(M, -1, -1):
    if (T >> i)&1 and ((1<<i)|a)^D <= X[0]:
        a = (1<<i)|a
print(X[0]-a^D)

Submission status: Wrong Answer

Solution code:
import sys
N, = map(int, input().split())
X = list(map(int, input().split()))
S = X[0]+X[1]
T = 0
for i in range(2, N):
    T ^= X[i]
if S<T or (S-T)%2:
    print(-1)
    sys.exit()
D = (S-T)//2
if D&T:
    print(-1)
    sys.exit()
M = 20
a = 0
for i in range(M, -1, -1):
    if (T >> i)&1 and ((1<<i)|a)^D <= X[0]:
        a = (1<<i)|a
print(X[0]-a^D)

Submission status: Wrong Answer

Solution code:
import sys
N, = map(int, input().split())
X = list(map(int, input().split()))
S = X[0]+X[1]
T = 0
for i in range(2, N):
    T ^= X[i]
if S<T or (S-T)%2:
    print(-1)
    sys.exit()
D = (S-T)//2
M = 20
a = 0
for i in range(M, -1, -1):
    if (T >> i)&1 and ((1<<i)|a)^D <= X[0]:
        a = (1<<i)|a
print(X[0]-a^D)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
if N==2 and A==[0,0]:
  print(0)
  exit()
X=0
for i in range(2,N):
  X^=A[i]
B=A[0]
Y=1<<42
P=0
Z=0
for i in range(42):
  Y>>=1
  if Y&(X^A[0]^A[1])==0:
    X=X&(~Y)
    A[0],A[1]=A[0]&(~Y),A[1]&(~Y)
    continue
  Z=min(((~Y)&A[0])+1,(Y-((~Y)&A[1])))
  A[0]-=Z
  A[1]+=Z
  A[0],A[1]=A[0]&(~Y),A[1]&(~Y)
  P+=Z
  X=X&(~Y)
if A[0]^A[1]^X==0 and P<B and P>=0:
  print(P)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
N, = map(int, input().split())
X = list(map(int, input().split()))
t = 0
for x in X:
    t = t^x
inf = float('inf')
d = dict()
def it(x, y, z):
    if (x, y, z) in d:
        return d[(x, y, z)]
    xm, ym, zm = x%2, y%2, z%2
    if xm ^ ym != zm:
        d[(x, y, z)] = inf
        return inf
    if x^y == z:
        d[(x, y, z)] = 0
        return 0
    Rz = 2*it(x>>1, y>>1, z>>1)
    Ro = inf
    if x:
        Ro = 2*it((x-1)>>1, (y+1)>>1, z>>1)+1
    Rz = min(Rz, Ro)
    d[(x, y, z)] = Rz
    return Rz

r = it(X[0], X[1], t^X[0]^X[1])
if 0 < r < X[0]:
    print(r)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
N, = map(int, input().split())
X = list(map(int, input().split()))
t = 0
for x in X:
    t = t^x
inf = float('inf')
d = dict()
def it(x, y, z):
    if (x, y, z) in d:
        return d[(x, y, z)]
    xm, ym, zm = x%2, y%2, z%2
    if xm ^ ym != zm:
        d[(x, y, z)] = inf
        return inf
    if x^y == z:
        d[(x, y, z)] = 0
        return 0
    Rz = 2*it(x>>1, y>>1, z>>1)
    Ro = inf
    if x:
        Ro = 2*it((x-1)>>1, (y+1)>>1, z>>1)+1
    Rz = min(Rz, Ro)
    d[(x, y, z)] = Rz
    return Rz

r = it(X[0], X[1], t^X[0]^X[1])
if 0 < r < 10**18:
    print(r)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    a = [int(i) for i in ipt().split()]
    x = 0
    for i in a[2::]:
        x ^= i
    s = a[0]+a[1]
    d = (s-x)//2
    if d < 0 or d&x or d > a[0]:
        print(-1)
        exit()
    a1 = d
    xi = 1
    kx = x
    while kx > 0:
        xi *= 2
        kx >>= 1
    xi //= 2
    while xi > 0:
        if x&xi:
            if a1+xi <= a[0]:
                a1 += xi
            x -= xi
        xi //= 2
    if a1 == a[0]:
        print(-1)
        exit()
    else:
        print(a[0]-a1)

    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    a = [int(i) for i in ipt().split()]
    x = 0
    for i in a[2::]:
        x ^= i
    s = a[0]+a[1]
    d = (s-x)//2
    if d < 0 or d&x or d > a[0]:
        print(-1)
        exit()
    a1 = d
    xi = 1
    kx = x
    while kx > 0:
        xi *= 2
        kx >>= 1
    xi //= 2
    while xi > 0:
        if x&xi:
            if a1+xi <= a[0]:
                a1 += xi
            x -= xi
        xi //= 2
    if a1 == 0:
        print(-1)
        exit()
    else:
        print(a[0]-a1)

    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
a = list(map(int,readline().split()))
s = a[0]+a[1]
if n == 2:
  if a[0] < a[1] or s%2 == 1:
    print(-1)
  else:
    print(a[0]-s//2)
  exit()
  
c = 0
for i in a[2:]:
  c ^= i

sc = (s-c)//2
if s < c or (s-c)%2 == 1 or c&sc:
  print(-1,0)
  exit()

bb = a[0].bit_length()
x = ''
chk = 0
for i in range(bb-1,-1,-1):
  if not (c>>i&1)|(sc>>i&1):
    x += '0'
  elif not c>>i&1 and sc>>i&1:
    x += '1'
    chk += 2**i
  else:
    x += '?'
  
for i in range(bb):
  if x[i] == '?':
    if a[0] >= chk+2**(bb-1-i):
      chk += 2**(bb-1-i)

ans = a[0]-chk
print(ans if a[0] > ans > 0 else -1)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
a = list(map(int,readline().split()))
s = a[0]+a[1]
if n == 2:
  if a[0] < a[1] or s%2 == 1:
    print(-1)
  else:
    print(a[0]-s//2)
  exit()
  
c = 0
for i in a[2:]:
  c ^= i

sc = (s-c)//2
if s < c or (s-c)%2 == 1 or c&sc:
  print(-1)
  exit()

bb = a[0].bit_length()
x = ''
chk = 0
for i in range(bb-1,-1,-1):
  if not (c>>i&1)|(sc>>i&1):
    x += '0'
  elif not c>>i&1 and sc>>i&1:
    x += '1'
    chk += 2**i
  else:
    x += '?'
  
for i in range(bb):
  if x[i] == '?':
    if a[0] >= chk+2**(bb-1-i):
      chk += 2**(bb-1-i)

ans = a[0]-chk
print(ans if ans > 0 else -1)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
a = list(map(int,readline().split()))
s = a[0]+a[1]
if n == 2:
  if a[0] < a[1] or s%2 == 1:
    print(-1)
  else:
    print(a[0]-s//2)
  exit()
  
c = 0
for i in a[2:]:
  c ^= i

sc = (s-c)//2
if s < c or (s-c)%2 == 1 or c&sc != 0:
  print(-1)
  exit()

bb = a[0].bit_length()
x = ''
chk = 0
for i in range(bb-1,-1,-1):
  if (c>>i&1)|(sc>>i&1) == 0:
    x += '0'
  elif c>>i&1 == 0 and sc>>i&1 == 1:
    x += '1'
    chk += 2**i
  else:
    x += '?'
  
for i in range(bb):
  if x[i] == '?':
    if a[0] >= chk+2**(bb-1-i):
      chk += 2**(bb-1-i)
      
if chk <= 0:
  print(-1)
else:
  print(a[0]-chk)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
a = list(map(int,readline().split()))
s = a[0]+a[1]
if n == 2:
  if a[0] < a[1] or s%2 == 1:
    print(-1)
  else:
    print(a[0]-s//2)
  exit()
  
c = 0
for i in a[2:]:
  c ^= i

sc = (s-c)//2
if s < c or (s-c)%2 == 1 or c&sc != 0:
  print(-1)
  exit()

bb = a[0].bit_length()
x = ''
chk = 0
for i in range(bb-1,-1,-1):
  if (c>>i&1)|(sc>>i&1) == 0:
    x += '0'
  elif c>>i&1 == 0 and sc>>i&1 == 1:
    x += '1'
    chk += 2**i
  else:
    x += '?'
  
for i in range(bb):
  if x[i] == '?':
    if a[0] >= chk+2**(bb-1-i):
      chk += 2**(bb-1-i)
      
if chk < 0:
  print(-1)
else:
  print(a[0]-chk)

Submission status: Wrong Answer

Solution code:
#解説方針
import math
N = int(input())
A = list(map(int, input().split()))

all_xor = 0
for i in range(N):
  all_xor = all_xor ^ A[i]

fore = A[0] ^ A[1]#S
back = fore ^ all_xor #X
#a + b = (a xor b) + 2 * (a and b)
#a xor b = back, a + b = A[0] + A[1]

a_and_b = (A[0] + A[1] - back) / 2
#print(a_and_b, back)
#a_and_bは非負整数である必要がある
if (a_and_b % 1 != 0) or (a_and_b < 0):
  print(-1)
  quit()
a_and_b = int(a_and_b)

#print(a_and_b, back, a_and_b & back)
#a_and_bとbackには共通のbitがない
if (a_and_b & back) != 0:
  print(-1)
  quit()

ans = a_and_b
#print(math.log2(32))
if back == 0:
  if (ans < 0) or (ans == A[0]):
    print(-1)
  else:
    print(A[0] - ans)
  quit()
else:
  if ans > A[0]:
    print(-1)
    quit()
  nn = int(math.log2(back)) + 1
  #print(nn)
  #print(2 >> 1)
  #print(2 << 1)
  for i in range(nn + 1):
    #print(back, nn - i)
    if ((back >> (nn - i)) & 1):
      #print(ans, 2 << (nn - i))
      k = ans + (1 << (nn - i))
      #print("k", k, i)
      if k <= A[0]:
        ans = k 
  if (ans == 0) or (A[0] - ans < 0):
    print(-1)
  else:
    print(A[0] - ans)

Submission status: Wrong Answer

Solution code:
#解説方針
import math
N = int(input())
A = list(map(int, input().split()))

all_xor = 0
for i in range(N):
  all_xor = all_xor ^ A[i]

fore = A[0] ^ A[1]#S
back = fore ^ all_xor #X
#a + b = (a xor b) + 2 * (a and b)
#a xor b = back, a + b = A[0] + A[1]

a_and_b = (A[0] + A[1] - back) / 2
#print(a_and_b, back)
#a_and_bは非負整数である必要がある
if (a_and_b % 1 != 0) or (a_and_b < 0):
  print(-1)
  quit()
a_and_b = int(a_and_b)

#print(a_and_b, back, a_and_b & back)
#a_and_bとbackには共通のbitがない
if (a_and_b & back) != 0:
  print(-1)
  quit()

ans = a_and_b
#print(math.log2(32))
if back == 0:
  if (ans < 0) or (ans == A[0]):
    print(-1)
  else:
    print(A[0] - ans)
  quit()
else:
  if ans > A[0]:
    print(-1)
    quit()
  nn = int(math.log2(back)) + 1
  #print(nn)
  #print(2 >> 1)
  #print(2 << 1)
  for i in range(nn + 1):
    #print(back, nn - i)
    if ((back >> (nn - i)) & 1):
      #print(ans, 2 << (nn - i))
      k = ans + (1 << (nn - i))
      #print("k", k, i)
      if k <= A[0]:
        ans = k 
  if ans == 0:
    print(-1)
  else:
    print(A[0] - ans)

Submission status: Wrong Answer

Solution code:
#解説方針
import math
N = int(input())
A = list(map(int, input().split()))

all_xor = 0
for i in range(N):
  all_xor = all_xor ^ A[i]

fore = A[0] ^ A[1]#S
back = fore ^ all_xor #X
#a + b = (a xor b) + 2 * (a and b)
#a xor b = back, a + b = A[0] + A[1]

a_and_b = (A[0] + A[1] - back) / 2
#print(a_and_b, back)
#a_and_bは非負整数である必要がある
if (a_and_b % 1 != 0) or (a_and_b < 0):
  print(-1)
  quit()
a_and_b = int(a_and_b)

#print(a_and_b, back, a_and_b & back)
#a_and_bとbackには共通のbitがない
if (a_and_b & back) != 0:
  print(-1)
  quit()

ans = a_and_b
#print(math.log2(32))
if back == 0:
  if (ans < 0) or (ans == A[0]):
    print(-1)
  else:
    print(A[0] - ans)
  quit()
else:
  if ans > A[0]:
    print(-1)
    quit()
  nn = int(math.log2(back)) + 1
  #print(nn)
  #print(2 >> 1)
  #print(2 << 1)
  for i in range(nn + 1):
    #print(back, nn - i)
    if ((back >> (nn - i)) & 1):
      #print(ans, 2 << (nn - i))
      k = ans + (1 << (nn - i))
      #print("k", k, i)
      if k <= A[0]:
        ans = k
  #print(ans)  
  if ans == A[0]:
    print(-1)
  else:
    print(A[0] - ans)

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    A = LI()

    x = 0
    for i in A[2:]:
        x ^= i

    z = A[0] ^ A[1]
    if z & 1 != x & 1:
        print(-1)
        return

    a0 = A[0]
    a1 = A[1]

    b = 2
    mask = 1
    while b <= (A[0]+A[1]):
        if z & b != x & b:
            d0 = (a0 & mask) + 1
            d1 = b - (a1 & mask)
            a0 -= min(d0,d1)
            a1 += min(d0,d1)
            z = a0 ^ a1
            if z & b != x & b:
                a0 += min(d0,d1)
                a1 -= min(d0,d1)
                a0 -= max(d0,d1)
                a1 += max(d0,d1)
                z = a0 ^ a1
                if z & b != x & b:
                    print(-1)
                    return
        b <<= 1
        mask <<= 1
        mask += 1

    if a0 > 0:
        print(A[0] - a0)
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    A = LI()

    x = 0
    for i in A[2:]:
        x ^= i

    z = A[0] ^ A[1]
    if z & 1 != x & 1:
        print(-1)
        return

    a0 = A[0]
    a1 = A[1]

    b = 2
    mask = 1
    while b <= (A[0]+A[1]):
        if z & b != x & b:
            d0 = (a0 & mask) + 1
            d1 = b - (a1 & mask)
            a0 -= min(d0,d1)
            a1 += min(d0,d1)
            z = a0 ^ a1
            if z & b != x & b:
                print(-1)
                return
        b <<= 1
        mask <<= 1
        mask += 1

    if a0 > 0:
        print(A[0] - a0)
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from functools import reduce
from collections import defaultdict
N = int(input())
A = list(map(int,input().split()))

r = reduce(lambda x,y : x^y , A[2:],0)

a,b = A[:2]

orga = a

ans = 0
l = max(map(lambda x : len(bin(x)), [a,b,r]))-2
cand = {(a,b,r):0}
for i in range(l):
    temp = defaultdict(lambda : 10**10)
    for (a,b,r),s in cand.items():
        x,y,z = a%2,b%2,r%2
        if not x^y == z:
            continue
        else:
            if s < temp[(a//2,b//2,r//2)]:
                temp[(a//2,b//2,r//2)] = s
            a -= 1
            b += 1
            if a < 0:
                continue
            s += (1<<i)
            if s < temp[(a//2,b//2,r//2)]:
                temp[(a//2,b//2,r//2)] = s
    cand = temp

if not (0,0,0) in cand:
    print(-1)
else:
    ans = cand[(0,0,0)]
    if ans == orga:
        print(-1)
    else:
        print(ans)

Submission status: Wrong Answer

Solution code:
from functools import reduce
N = int(input())
A = list(map(int,input().split()))

r = reduce(lambda x,y : x^y , A[2:],0)

a,b = A[:2]

ans = 0
l = max(map(lambda x : len(bin(x)), [a,b,r]))-2
cand = [[a,b,r,0]]
for i in range(l):
    temp = []
    for a,b,r,s in cand:
        x,y,z = a%2,b%2,r%2
        if not x^y == z:
            continue
        else:
            temp.append([a//2,b//2,r//2,s])
            a -= 1
            b += 1
            if a <= 0:
                continue
            temp.append([a//2,b//2,r//2,s+(1<<i)])
    cand = temp
ans = 10**10
for x,y,z,s in cand:
    if x == 0 and y == 0 and z == 0:
        ans = min(ans,s)
if ans == 10**10:
    ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd, sqrt
from operator import mul
from functools import reduce
from operator import mul
from pprint import pprint



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
A = LI()
y = 0
flg  = 0
for i in range(2, n):
    y ^= A[i]

x = A[0] + A[1] - y
if x < 0 or x % 2:
    flg = 0
x //= 2
a1 = x
if a1 >= A[0]:
    print(-1)
    exit()


for i in reversed(range((A[0] + A[1]).bit_length())):
    if y & (1 << i):
        if x & (1 << i):
            print(-1)
            sys.exit()
        if a1 + 2 ** i <= A[0]:
            a1 += 2 ** i

if a1 == 0:
    flg = 1
print(A[0] - a1 if flg == 0 else -1)