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:
from functools import reduce

N=int(input())
*A,=map(int,input().split())

if N == 2:
  if A[0]<A[1] or (A[0]+A[1])&1:
    print(-1)
  else:
    print(A[0]-(A[0]+A[1])//2)
  exit()

g = reduce(lambda a,b:a^b,A[2:])
a,b = A[:2]
ans = 0
for i in range(max(A[0].bit_length(),A[1].bit_length(),g.bit_length())-1,-1,-1):
  if ((a>>i)&1) + ((b>>i)&1) + ((g>>i)&1) % 2 == 0:continue
  if (((a>>i)&1) + ((b>>i)&1) + ((g>>i)&1)) % 2 == 1:
    if (a>>i)&1==0:
      print(-1)
      exit()
    var = sum([1<<j for j in range(i,-1,-1) if (a>>j)&1]) - ((1<<i)-1)
    ans += var
    a -= var
    b += var
    
print(ans)

Submission status: Wrong Answer

Solution code:

def main(n,a):
    s=a[0]+a[1]
    z=0
    for ai in a[2:]:
        z^=ai
    # i+j=s,i<=a[0],i^j=z となるi,jを探す
    # i+j=i^j+2*(i & j)
    # s = z + 2*(i & j)
    # i & j = (s-z)/2 = d
    # z = 2*(i & j) - s = i ^ j
    # d = (s-z) / 2
    # z = x^y , x&y=0
    # d^x,d^yは条件を満たす。d^x+d^y=d^x^d^y + 2*((d^x)&(d^y))= z + 2*d = s
    # (d^x)^(d^y)=x^y=z
    # (d^x)&(d^y)=d (z & d = 0 のときのみ)
    if s-z<0 or (s-z)%2==1:return -1
    d=(s-z)//2
    if d&z!=0:return -1
    if not d<=a[0]:return -1
    part=[]
    i=0
    while z//pow(2,i):
        if (z//pow(2,i))%2==1:part.append(pow(2,i))
        i+=1
    ans=float('inf')
    k=len(part)
    x=0
    while part:
        tmp=part.pop()
        if d^(x+tmp)<=a[0]:
            x+=tmp
    return a[0]-(d^x)


n=int(input())
a=list(map(int,input().split()))
print(main(n,a))

Submission status: Wrong Answer

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    xorR = 0
    for i in range(2, N):
        xorR ^= A[i]
    rbit = [0] * 40
    K = xorR
    for i in range(40):
        rbit[i] = K % 2
        K //= 2
    
    D = A[0] + A[1] - xorR
    if D < 0 or D % 2 == 1:
        print(-1)
        return 0
    else:
        D //= 2
        if D > A[0]:
            print(-1)
            return 0
        K = D
        dbit = [0] * 40
        for i in range(40):
            dbit[i] = K % 2
            K //= 2
        A0 = D
        for i in range(40):
            if rbit[39 - i] == dbit[39 - i] == 1:
                print(-1)
                break
            else:
                if rbit[39 - i] == 1:
                    if A0 + pow(2, 39 - i) <= A[0]:
                        A0 += pow(2, 39 - i)
        if A0  > 0: print(A[0] - A0)
        else: print(-1)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    xorR = 0
    for i in range(2, N):
        xorR ^= A[i]
    rbit = [0] * 40
    K = xorR
    for i in range(40):
        rbit[i] = K % 2
        K //= 2
    
    D = A[0] + A[1] - xorR
    if D < 0 or D % 2 == 1:
        print(-1)
        return 0
    else:
        D //= 2
        if D > A[0]:
            print(-1)
            return 0
        K = D
        dbit = [0] * 40
        for i in range(40):
            dbit[i] = K % 2
            K //= 2
        A0 = 0 
        for i in range(40):
            if rbit[39 - i] == dbit[39 - i] == 1:
                print(-1)
                break
            else:
                if rbit[39 - i] == 1:
                    if (A0 + pow(2, 39 - i)) ^ D <= A[0]:
                        A0 += pow(2, 39 - i)
                elif rbit[39 - i] == 0 and dbit[39 - i] == 1:
                    if (A0 + pow(2, 39 - i)) ^ D <= A[0]:
                        A0 += pow(2, 39 - i)
                    else: 
                        print(-1)
                        break
        if A0 > 0: print(A[0] - A0)
        else: print(-1)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    xorR = 0
    for i in range(2, N):
        xorR ^= A[i]
    rbit = [0] * 40
    K = xorR
    for i in range(40):
        rbit[i] = K % 2
        K //= 2
    
    D = A[0] + A[1] - xorR
    if D < 0 or D % 2 == 1:
        print(-1)
        return 0
    else:
        D //= 2
        K = D
        dbit = [0] * 40
        for i in range(40):
            dbit[i] = K % 2
            K //= 2
        A0 = 0 
        for i in range(40):
            if rbit[39 - i] == dbit[39 - i] == 1:
                print(-1)
                break
            else:
                if rbit[39 - i] == 1:
                    if (A0 + pow(2, 39 - i)) ^ D <= A[0]:
                        A0 += pow(2, 39 - i)
                elif rbit[39 - i] == 0 and dbit[39 - i] == 1:
                    if (A0 + pow(2, 39 - i)) ^ D <= A[0]:
                        A0 += pow(2, 39 - i)
                    else: 
                        print(-1)
                        break
        if A0 > 0: print(A[0] - A0)
        else: print(-1)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    xorR = 0
    for i in range(2, N):
        xorR ^= A[i]
    rbit = [0] * 40
    K = xorR
    for i in range(40):
        rbit[i] = K % 2
        K //= 2
    
    D = A[0] + A[1] - xorR
    if D < 0 or D % 2 == 1:
        print(-1)
        return 0
    else:
        D //= 2
        K = D
        dbit = [0] * 40
        for i in range(40):
            dbit[i] = K % 2
            K //= 2
        A0, A1 = 0, 0
        for i in range(40):
            if rbit[39 - i] == dbit[39 - i] == 1:
                print(-1)
                break
            else:
                if rbit[39 - i] == 1:
                    if (A0 + pow(2, 39 - i)) ^ D <= A[0]:
                        A0 += pow(2, 39 - i)
                    else:
                        A1 += pow(2, 39 - i)
        if A0 > 0: print(A[0] - A0)
        else: print(-1)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
S = A[0]+A[1]
X = 0
A0 = A[0]

for i in range(2, N):
    X ^= A[i]

L = 45
dp = [[[-1]*2 for _ in range(2)] for _ in range(L+1)]
dp[0][0][1] = 0

for i in range(L):
    for j in range(2):
        for k in range(2):
            if dp[i][j][k]==-1:
                continue
            
            for a in range(2):
                for b in range(2):
                    nj, s = divmod(a+b+j, 2)
                    x = a^b
                    
                    if s!=S&1:
                        continue
                    
                    if x!=X&1:
                        continue
                    
                    if a<A0&1:
                        nk = 0
                    elif a>A0&1:
                        nk = 1
                    else:
                        nk = k
                    
                    dp[i+1][nj][nk] = max(dp[i+1][nj][nk], dp[i][j][k]+(a<<i))
    
    S >>= 1
    X >>= 1
    A0 >>= 1

if dp[L][0][0]<=0:
    print(-1)
else:
    print(A[0]-dp[L][0][0])

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int, input().split()))
x=0
for i in a[2:]:x^=i
m=(a[0]+a[1]-x)//2
if a[0]+a[1]!=x+m*2or m>a[0]or(m&x)!=0:exit(print(-1))
l=1<<max(x.bit_length(),m.bit_length())
while l>0:
 if (x&l)!=0and(m|l)<=a[0]:m|=l
 l>>=1
print(a[0]-m if a!=0else-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
a, b, *L = map(int, input().split())
x = 0
for l in L:
  x ^= l
s = a+b
if s-x < 0 or (s-x)%2:
  print(-1)
  exit()
d = (s-x)//2
if d&x:
  print(-1)
  exit()
if d > a:
  print(-1)
  exit()
for i in range(50, -1, -1):
  if (x>>i)&1 and d|(1<<i) <= a:
    d |= 1<<i
ans = a - d
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n = int(input())
    a = list(map(int, input().split()))

    x = 0
    for i in range(2, n):
        x ^= a[i]
    d = a[0]+a[1]-x
    if d%2 == 1 or d < 0:
        print(-1)
        return
    d >>= 1
    if d&x != 0 or d > a[0]:
        print(-1)
        return
    k = x.bit_length()
    tmp = d
    # d^tmp はd&x=0からd|tmpと一緒
    for i in range(k, -1, -1):
        if (x >> i) & 1:
            if tmp+1<<i <= a[0]:
                tmp += 1<<i
    if 0 < tmp <= a[0]:
        print(a[0]-tmp)
    else:
        print(-1)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n = int(input())
    a = list(map(int, input().split()))

    x = 0
    for i in range(2, n):
        x ^= a[i]
    d = a[0]+a[1]-x
    if d%2 == 1 or d < 0:
        print(-1)
        return
    d >>= 1
    if d&x != 0 or d > a[0]:
        print(-1)
        return
    k = x.bit_length()
    tmp = 0
    for i in range(k-1, -1, -1):
        if (x >> i) & 1:
            if d ^ (tmp+(1<<i)) <= a[0]:
                tmp += 1<<i
    ans =a[0]-d^tmp
    if 0 <= ans < a[0]:
        print(ans)
    else:
        print(-1)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n = int(input())
    a = list(map(int, input().split()))

    x = 0
    for i in range(2, n):
        x ^= a[i]
    s = a[0]+a[1]
    if (s-x)%2 != 0 or (d:=(s-x)//2)&x != 0 or d < 0 or d > a[0]:
        print(-1)
        return
    k = x.bit_length()
    tmp = 0
    for i in range(k-1, -1, -1):
        if (x >> i) & 1:
            if d ^ (tmp+(1<<i)) <= a[0]:
                tmp += 1<<i
    ans =a[0]-d^tmp
    if ans == a[0]:
        print(-1)
    else:
        print(ans)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n = int(input())
    a = list(map(int, input().split()))

    x = 0
    for i in range(2, n):
        x ^= a[i]
    s = a[0]+a[1]
    if (s-x)%2 != 0 or (d:=(s-x)//2)&x != 0 or d > a[0]:
        print(-1)
        return
    k = x.bit_length()
    tmp = 0
    for i in range(k-1, -1, -1):
        if (x>>i)&1:
            if d^(tmp+1<<i) <= a[0]:
                tmp += 1<<i
    ans =a[0]-d^tmp
    if ans == a[0]:
        print(-1)
    else:
        print(ans)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n = int(input())
    a = list(map(int, input().split()))

    x = 0
    for i in range(2, n):
        x ^= a[i]
    s = a[0]+a[1]
    if (s-x)%2 != 0 or (d:=(s-x)//2)&x != 0 or d > a[0]:
        print(-1)
        return
    k = x.bit_length()
    tmp = 0
    for i in range(k, -1, -1):
        if (x>>i)&1:
            if d^(tmp+1<<i) <= a[0]:
                tmp += 1<<i
    ans =a[0]-d^tmp
    if ans == a[0]:
        print(-1)
    else:
        print(ans)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))

XOR = 0
for el in A[2:]:
    XOR ^= el

if (A[0] + A[1] - XOR) % 2 != 0:
    print(-1)
    exit(0)

AND = (A[0] + A[1] - XOR) // 2
if XOR & AND != 0:
    print(-1)
    exit(0)

ok = False
u = 0
v = 0

bits = list()
for bit in range(60, -1, -1):
    if XOR >> bit & 1 == 0 and AND >> bit & 1 == 1:
        u |= 1 << bit
        v |= 1 << bit
    elif XOR >> bit & 1 == 1 and AND >> bit & 1 == 0:
        bits.append(bit)

for bit in bits:
    if (u | (1 << bit)) <= A[0]:
        u |= 1 << bit

if u > A[0]:
    print(-1)
    exit(0)
print(A[0] - u)

Submission status: Wrong Answer

Solution code:
# AFTER EDITORIAL


def solve(ls):
    import math

    x, y, *ls = ls
    z = x + y
    s = 0
    for a in ls:
        s ^= a

    #
    # Max a <= x  s.t.
    #   0 = NimSum(a, (x + y) - a, ls)
    # <=>
    # Max a <= x s.t.
    #   ∃b.
    #     a + b = x + y  (NOTE: a + b = a ^ b + 2 (a & b))
    #     a ^ b = NimSum(ls)
    # <=>
    # Max a <= x s.t.
    #   ∃b.
    #     a & b = (x + y - NimSum(ls)) / 2
    #     a ^ b = NimSum(ls)
    #

    #
    # Thus it amounts to solve
    #   a ^ b = s
    #   a & b = (z - S) / 2 = t
    #
    # which is bit-wise independent as
    #   a  b  ^  &
    #   0  0  0  0
    #   0  1  1  0
    #   1  0  1  0
    #   1  1  0  1
    #

    if (z - s) < 0 or (z - s) % 2 == 1:
        return -1

    t = (z - s) // 2
    s_t = s & t

    if s_t > 0 or t > x:
        return -1

    a = t
    b = t
    first_set = math.floor(math.log2(s + 1))
    for i in range(first_set + 1)[::-1]:
        k = 1 << i
        if s & k:
            if (a | k) <= x:  # Greedy is optimal
                a = a | k
            else:
                b = b | k
    return x - a


def main(istr, ostr):
    n = int(istr.readline().strip())
    ls = list(map(int, istr.readline().strip().split()))
    result = solve(ls)
    print(result, file=ostr)


if __name__ == "__main__":
    import sys

    main(sys.stdin, sys.stdout)

Submission status: Wrong Answer

Solution code:
n=int(input())
A=list(map(int,input().split()))
#print(format(A[0],"45b"))
#print(format(A[1],"45b"))
X=0
for i in range(n-2):
  X=X^A[i+2]
#print(X)
XX=A[0]+A[1]
#print(XX)
#print(XX-X)
if (XX-X)%2==1:
  print(-1)
  exit()
Y=(XX-X)//2 #固定bit
if A[0]<Y:
  print(-1)
  exit()
S=format(Y,"45b")
T=format(XX,"45b")
#print(S)
y=Y
#print(y)
for i in range(42):
  if T[-42+i]=="1" and S[-42+i]!="1":
    if A[0]<2**(41-i)+y:
      continue
    else:
      y=y+2**(41-i)
#    print(y)
#print(y*10000)
if y==0:
  print(-1)
else:
  print(A[0]-y)

Submission status: Wrong Answer

Solution code:
n=int(input())
A=list(map(int,input().split()))
#print(format(A[0],"45b"))
#print(format(A[1],"45b"))
X=0
for i in range(n-2):
  X=X^A[i+2]
#print(X)
XX=A[0]+A[1]
#print(XX)
#print(XX-X)
if (XX-X)%2==1:
  print(-1)
  exit()
Y=(XX-X)//2 #固定bit
if A[0]<Y:
  print(-1)
  exit()
S=format(Y,"45b")
T=format(XX,"45b")
#print(S)
y=Y
#print(y)
for i in range(42):
  if T[-42+i]=="1":
    if A[0]<2**(41-i)+y:
      continue
    else:
      y=y+2**(41-i)
#    print(y)
#print(y*10000)
if y==0:
  print(-1)
else:
  print(A[0]-y)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from functools import lru_cache
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
A=tuple(map(int,input().split()))
X=0
for x in A[2:]:
    X^=x
S=A[0]+A[1]
if (S-X)%2:
    print(-1)
    exit()
D=(S-X)//2
ans=0
tmp=0
ttmp=0
f=False
for i in range(50):
    if (D>>i)&1==(X>>i)&1==1:
        print(-1)
        exit()
    elif (D>>i)&1==1 and (X>>i)&1==0: # (1,1)
        if (A[0]>>i)&1==0:
            ans-=1<<i
            f=True
    elif (D>>i)&1==0 and (X>>i)&1==1: # (1,0), (0,1)
        if (A[0]>>i)&1==1 and f:
            tmp=1<<i
            ans+=ttmp
            ttmp=0
            f=False
        elif (A[0]>>i)&1==0:
            ttmp-=1<<i
    else: # (0,0)
        if (A[0]>>i)&1==1:
            ans+=1<<i
            if f:
                ans+=ttmp
                ttmp=0
            f=False
if f:
    print(-1)
else:
    if ans+tmp>=A[0]:
        print(-1)
    else:
        print(ans+tmp)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
X = 0
for i in range(2,N):
    X ^= A[i]
ans = 0
for i in range(A[0]):
    A[0] -= i
    A[1] += i
    xor = 0
    xor ^= X^A[0]^A[1]
    if xor == 0:
        ans = i
        break
    A[0] += i
    A[1] -= i
if ans == 0:
    print('-1')
else:
    print(ans)

Submission status: Wrong Answer

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

A = l[0]
B = l[1]
X = 0
for i in l[2:]:
	X ^= i

S = A + B
D = (S - X) // 2
if ((S - X) / 2) % 1!= 0:
	ans = A + 1

else:
	if D < 0 or (D & X) & X != 0 or D > A:
		ans = A + 1
	else:
		ans = D
		l = bin(X)[2:]
		len_l = len(l)

		i = 0

		while True and i < len_l:
			y =int(l[i]+'0'*(len_l-1-i), 2)
			if ans^y <= A:
				ans ^= y
			i += 1

print(A - ans)

Submission status: Wrong Answer

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

A = l[0]
B = l[1]
X = 0
for i in l[2:]:
	X ^= i

S = A + B
D = (S - X) // 2
if ((S - X) / 2) % 1!= 0:
	ans = A + 1

if D < 0 or (D & X) & X != 0 or D > A:
	ans = A + 1
else:
	ans = D
	l = bin(X)[2:]
	len_l = len(l)

	i = 0

	while True and i < len_l:
		y =int(l[i]+'0'*(len_l-1-i), 2)
		if ans^y <= A:
			ans ^= y
		i += 1

print(A - ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
ans = 0
for i in range(A[0]):
    A[0] -= i
    A[1] += i
    xor = 0
    for j in A:
        xor ^= j
    if xor == 0:
        ans = i
        break
    A[0] += i
    A[1] -= i
if ans == 0:
    print('-1')
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N = int(readline())
    A = list(map(int, readline().split()))

    grundy = 0

    for a in A[2:]:
        grundy ^= a

    A0 = A[0]
    A1 = A[1]
    ans = -1

    for i in range(A0+1):
        a = A0 - i
        b = A1 + i
        if a^b^grundy==0:
            ans = i
            break

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))

XOR=0
for a in A[2:]:
    XOR^=a

S=A[0]+A[1]

DP=[[[1<<60]*2 for i in range(2)] for j in range(60)]
DP[0][0][0]=0

for i in range(59):
    CX=0
    if XOR & (1<<i)!=0:
        CX=1

    CS=0
    if S & (1<<i)!=0:
        CS=1

    CA=0
    if A[1] & (1<<i)!=0:
        CA=1
    
    for j in range(2):
        for k in range(2):
            if DP[i][j][k]==1<<60:
                continue

            for na,nb in [(0,0),(0,1),(1,0),(1,1)]:
                if na^nb != CX:
                    continue
                if (na+nb+j)%2 != CS:
                    continue
                
                if na+nb+j>=2:
                    nj=1
                else:
                    nj=0

                if CA<nb:
                    nk=1
                elif CA==nb:
                    nk=k
                else:
                    nk=0

                DP[i+1][nj][nk]=min(DP[i+1][nj][nk],DP[i][j][k]|((1<<i)*nb))
                #print(i,j,k,nj,nk,DP[i][j][k]|((1<<i)*nb))

ANS=DP[59][0][1]-A[1]

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

Submission status: Wrong Answer

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

al = 0
for i in range(2,n):
    al ^= a[i]
ans = 0
s = a[0]+a[1]
if s-al<0 or (s-al)%2:
    ans = -1
else:
    d = (s-al)//2
    now = d
    for i in range(65,-1,-1):
        if (1 << i)&al and (1 << i)+now<=a[0]:
            now += 1 << i
    if now==0 or now>a[0]:
        ans = -1
    else:
        ans = a[0]-now

print(ans)

Submission status: Wrong Answer

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

al = 0
for i in range(2,n):
    al ^= a[i]
ans = 0
s = a[0]+a[1]
if s-al<0 or (s-al)%2:
    ans = -1
else:
    d = (s-al)//2
    now = d
    for i in range(65,-1,-1):
        if (1 << i)&al and (1 << i)+now<=a[0]:
            now += 1 << i
    ans = a[0]-now if now > 0 else -1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
for i in range(A[0]):
    xor = 0
    A[0] -= i
    A[1] += i
    for j in A:
        xor ^= j
    if xor == 0:
        print(i)
        exit()
print(-1)

Submission status: Wrong Answer

Solution code:

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    readline = sys.stdin.buffer.readline
    sys.setrecursionlimit(10 ** 7)

    from copy import deepcopy

    def binary_count(a, x):
        # max_A[i] <= 10 ** (n // 3) -> x = 10 * n (n % 3 == 0)
        res = [0] * x
        check = 2 ** x
        for i in range(x):
            check //= 2
            for j, aa in enumerate(a):
                if aa >= check:
                    a[j] -= check
                    res[i] += 1
        return res

    n = int(readline())
    a = list(map(int, readline().split()))
    memo = binary_count(a[2:], 40)
    a = a[:2]
    for ans in range(min(10 ** 6, a[0])):
        for v, m in zip(binary_count(deepcopy(a), 40), memo):
            if (v + m) % 2 == 1:
                break
        else:
            print(ans)
            break
        a[0] -= 1
        a[1] += 1
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    readline = sys.stdin.buffer.readline
    sys.setrecursionlimit(10 ** 7)

    def binary_count(a, x, flag):
        # max_A[i] <= 10 ** (n // 3) -> x = 10 * n (n % 3 == 0)
        res = [0] * x
        check = 2 ** x
        if flag:
            for i in range(x):
                check //= 2
                for j, aa in enumerate(a):
                    if aa >= check:
                        a[j] -= check
                        res[i] += 1
        else:
            for i in range(x):
                check //= 2
                if a >= check:
                    a -= check
                    res[i] = 1
        return res

    n = int(readline())
    a = list(map(int, readline().split()))
    memo = binary_count(a[2:], 40, True)
    for ans in range(min(10 ** 6, a[0])):
        for bf, af, m in zip(binary_count(a[0] - ans, 40, False), binary_count(a[1] + ans, 40, False), memo):
            if (bf + af + m) % 2 == 1:
                break
        else:
            print(ans)
            break
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from functools import lru_cache

def main():
    N = int(input())
    A = list(map(int, input().split()))
    x = 0
    for a in A[2:]:
        x ^= a
    a, b = A[0], A[1]
    if (a ^ b ^ x) & 1 != 0:
        return -1

    @lru_cache(None)
    def helper(a, b, x):
        if a == 0 or b == 0:
            return 0 if a ^ b == x else None
        if (a ^ b) & 1 != x & 1:
            return None
        t1 = helper(a // 2, b // 2, x // 2)
        t2 = helper((a - 1) // 2, (b + 1) // 2, x // 2)
        if t1 is None and t2 is None:
            return None
        if t1 is None:
            return t2 * 2 + 1
        if t2 is None:
            return t1 * 2
        t1 = t1 * 2
        t2 = t2 * 2 + 1
        return min(t1, t2)
    r = helper(a, b, x)
    if r is None or r >= a:
        return -1
    return r

print(main())

Submission status: Wrong Answer

Solution code:
from functools import lru_cache

def main():
    N = int(input())
    A = list(map(int, input().split()))
    x = 0
    for a in A[2:]:
        x ^= a
    a, b = A[0], A[1]
    if (a ^ b ^ x) & 1 != 0:
        return -1

    @lru_cache(None)
    def helper(a, b, x):
        if a == 0 or b == 0:
            return 0 if a ^ b == x else None
        if (a ^ b) & 1 != x & 1:
            return None
        t1 = helper(a // 2, b // 2, x // 2)
        t2 = helper((a - 1) // 2, (b + 1) // 2, x // 2)
        if t1 is None and t2 is None:
            return None
        if t1 is None:
            return t2 * 2 + 1
        if t2 is None:
            return t1 * 2
        t1 = t1 * 2
        t2 = t2 * 2 + 1
        return min(t1, t2)
    r = helper(a, b, x)
    if r is None or r == a:
        return -1
    return r

print(main())

Submission status: Wrong Answer

Solution code:
N = map(int, input().split())
As = list(map(int, input().split()))

added = As[0] + As[1]
xored = 0
for A in As[2:]:
    xored ^= A

anded = added - xored
if anded % 2 == 1:
    print(-1)
    exit()
else:
    anded >>= 1

left_stones_l_A0 = '' # <= A[0] for sure.
left_stones_e_A0 = '' #not sure if this is <= A[0].
for i, (a, x) in enumerate(zip(format(anded, '045b'), format(xored, '045b'))):
    if x == '0':
        if a == '0':
            left_stones_l_A0 += '0'
            left_stones_e_A0 += '0'
        else:
            left_stones_l_A0 += '1'
            left_stones_e_A0 += '1'
    else:
        if a == '0':
            if int(left_stones_l_A0 + '1' + '1' * (44 - i), base = 2) <= As[0]:
                left_stones_l_A0 += '1'
            else:
                left_stones_l_A0 += '0'
            if int(left_stones_e_A0 + '1' + '1' * (44 - i), base = 2) <= As[0]:
                left_stones_e_A0 += '1'
                left_stones_l_A0 = left_stones_e_A0
            elif int(left_stones_e_A0 + '1' + '0' * (44 - i), base = 2) <= As[0]:
                left_stones_e_A0 += '1'
            elif int(left_stones_e_A0 + '0' + '0' * (44 - i), base = 2) <= As[0]:
                left_stones_e_A0 += '0'
            else:
                left_stones_e_A0 = left_stones_l_A0
        else:
            print(-1)
            exit()

if int(left_stones_e_A0, base = 2) <= As[0]:
    ans = As[0] - int(left_stones_e_A0, base = 2)
else:
    ans = As[0] - int(left_stones_l_A0, base = 2)

if 0 <= ans < As[0]:
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
N = map(int, input().split())
As = list(map(int, input().split()))

added = As[0] + As[1]
xored = 0
for A in As[2:]:
    xored ^= A

anded = added - xored
if anded % 2 == 1:
    print(-1)
    exit()
else:
    anded >>= 1

left_stones_l_A0 = '' # <= A[0] for sure.
left_stones_e_A0 = '' #not sure if this is <= A[0].
for i, (a, x) in enumerate(zip(format(anded, '045b'), format(xored, '045b'))):
    if x == '0':
        if a == '0':
            left_stones_l_A0 += '0'
            left_stones_e_A0 += '0'
        else:
            left_stones_l_A0 += '1'
            left_stones_e_A0 += '1'
    else:
        if a == '0':
            if int(left_stones_l_A0 + '1' + '1' * (44 - i), base = 2) <= As[0]:
                left_stones_l_A0 += '1'
            else:
                left_stones_l_A0 += '0'
            if int(left_stones_e_A0 + '1' + '0' * (44 - i), base = 2) <= As[0]:
                left_stones_e_A0 += '1'
            elif int(left_stones_e_A0 + '0' + '0' * (44 - i), base = 2) <= As[0]:
                left_stones_e_A0 += '0'
            else:
                left_stones_e_A0 = left_stones_l_A0
        else:
            print(-1)
            exit()

if int(left_stones_e_A0, base = 2) <= As[0]:
    ans = As[0] - int(left_stones_e_A0, base = 2)
else:
    ans = As[0] - int(left_stones_l_A0, base = 2)

if 0 <= ans < As[0]:
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
mem = defaultdict(lambda : None)
mem[(0,0,0)] = 0
def dp(a,b,s):
  if mem[(a,b,s)] is not None:
    return mem[(a,b,s)]
  x = a&1
  y = b&1
  xor = s&1
  res = float("inf")
  if x^y != xor:
    mem[(a,b,s)] = res
    return res
  else:
    res = 2*dp(a>>1,b>>1,s>>1)
    if a > 1:
      pants = 2*dp((a-1)>>1,(b+1)>>1,s>>1)+1
      if pants > res:
        res = pants
  mem[(a,b,s)] = res
  return res

n = int(input())
a = list(map(int, input().split()))
s = 0
for i in a[2:]:
  s ^= i
b = a[1]
a = a[0]
ans = dp(a,b,s)
if ans == float("inf"):
  ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
A=[int(i) for i in input().split()]

A1=A[0]
A2=A[1]

c=0
for ele in A[2:]:
    c^=ele

d=A1+A2-c
if d%2==1:
    print(-1)
else:
    d=d//2
    #print(bin(c),bin(d))
    flgs=[]
    
    for i in range(41):
        fand= d & (1<<i)
        fxor= c & (1<<i)
        
        if fand & fxor:
            print(-1)
            break
        elif fand:
            flgs.append(1)
        elif fxor:
            flgs.append(2)
        else:
            flgs.append(0)
    else:
        flgs=flgs[::-1]
        #print(flgs)
        ans=0
        for i in range(len(flgs)):
            if flgs[i]==1:
                ans+=2**(41-i-1)
        
        for i in range(len(flgs)):
            if flgs[i]==2:
                if ans + 2**(41-i-1) <= A1:
                    ans+=2**(41-i-1)
        
        #print(ans)
        
        if ans==0:
            print(-1)
        else:
            print(A1-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

    s = A[0] + A[1]
    if s - x < 0 or (s - x) % 2:
        print(-1)
        return

    a = (s-x)//2
    if a & x:
        print(-1)
        return

    b = 1 << (A[0].bit_length() - 1)
    while b > 0:
        if b & x and a + b <= A[0]:
            a += b
        b >>= 1
    if a > 0:
        print(A[0] - a)
    else:
        print(-1)


if __name__ == '__main__':
    main()

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
if a > l[0]:
    print(-1)
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)