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:
def compute(S, X): 
  A = (S - X)//2
  a = 0
  b = 0
  ambiguous=[0]*64
  for i in range(64): 
    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)  
      b = ((1 << i) | b)  
    elif (Xi > 0 and Ai == 0): 
      ambiguous[i]=1
    else:
      print(-1) 
      return
  firsti=-1
  for i in range(63,-1,-1):
    temp = (a1[1] & (1 << i)) 
    Ai = (a & (1 << i)) 
    if Ai>temp:
      firsti=i
      break
  for i in range(63,-1,-1):
    temp = (a1[1] & (1 << i)) 
    if ambiguous[i]==1:
      if i>firsti:
        if temp>0:
          a = ((1 << i) | a) 
        else:
          a = ((0 << i) | a)
      if i<=firsti:
        a = ((0 << i) | a)
  if a>=a1[1]:
    print(a-a1[1])
    return
  flag=0
  for i in range(64):
    temp = (a1[1] & (1 << i)) 
    Ai = (a & (1 << i)) 
    if ambiguous[i]==1 and Ai==0:
      a = ((1 << i) | a)
      for j in range(i-1,-1,-1):
        if ambiguous[j]==1:
          a = ((0 << i) | a)
      break
    if i==63:
      print(-1)
      flag=1
  if flag==1:
    return
  if a<a1[1] or S==a:
    print(-1)
  else:
    print(a-a1[1])
  
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
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

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

for i in range(min(10**8,a[0])):
  if (a[0]-i)^(a[1]+i) == c:
    print(i)
    exit()
print(-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(x) for x in input().split()]

sm = 0
for i in range(2, n):
    sm ^= a[i]

if a[0] ^ a[1] ^ sm == 0:
    print(0)
    exit()

# TLE解
for i in range(min(a[0]-1, 10*6+5)):
    a[0] -= 1
    a[1] += 1
    if a[0] ^ a[1] ^ sm == 0:
        print(i+1)
        exit()

print(-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
alst = list(map(int, input().split()))
if n == 2:
    if sum(alst) % 2 != 0:
        print(-1)
    elif alst[0] < alst[1]:
        print(-1)
    else:
        print((alst[0] - alst[1]) // 2)
    exit()

if alst.count(1) == n:
    if n % 2 == 0:
        print(0)
    else:
        print(-1)
    exit()
    
if alst.count(1) == n - 1:
    print(-1)
    exit()

xor = 0
for num in alst[2:]:
    xor ^= num
total = alst[0] + alst[1]
if xor > total:
    print(-1)
    exit()

diff = total - xor
if diff % 2 == 1:
    print(-1)
    exit()

if alst[0] == 1:
    if xor == alst[0] ^ alst[1]:
        print(0)
    else:
        print(-1)
    exit()
    
diff //= 2
total_bin = format(total, "b")
diff_bin = format(diff,"b")
xor_bin = format(xor,"b")
i = len(total_bin)
ans = 0
for j in range(i, 0, -1):
    if j <= len(diff_bin):
        if diff_bin[-j] == "1":
            ans += 2 ** (j - 1)
            continue
for j in range(i, 0, -1):
    if j <= len(diff_bin):
        if diff_bin[-j] == "1":
            continue
    if j <= len(xor_bin):
        if xor_bin[-j] == "0":
            continue    
    if ans + 2 ** (j - 1) < alst[0]:
        ans += 2 ** (j - 1)
if ans == 0 or ans >= alst[0]:
    print(-1)
else:
    print(alst[0] - ans)

Submission status: Wrong Answer

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

s = 0
for i in range(2, n):
    s ^= a[i]

ans = -1
for i in range(min(10**8, a[0])):
    if (a[0]-i)^(a[1]+i)==s:
        ans = i
        break

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
l = [int(x) for x in input().split()]
hai = 0
b =[0] * N
for j in range(min(l[0]-1,10000)):
    hai = 0
    for k in range(N):
        b[k] = l[k]
    b[0] -= j
    b[1] += j
    for i in range(N):
        hai = hai^b[i]
    if hai == 0:
        print(j)
        exit()
print(-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
alst = list(map(int, input().split()))
if n == 2:
    if sum(alst) % 2 != 0:
        print(-1)
    elif alst[0] < alst[1]:
        print(-1)
    else:
        print((alst[0] - alst[1]) // 2)
    exit()

if alst.count(1) == n:
    if n % 2 == 0:
        print(0)
    else:
        print(-1)
    exit()
    
if alst.count(1) == n - 1:
    if n % 2 == 1:
        print(0)
    else:
        print(-1)
    exit()

xor = 0
for num in alst[2:]:
    xor ^= num
total = alst[0] + alst[1]
if xor > total:
    print(-1)
    exit()

diff = total - xor
if diff % 2 == 1:
    print(-1)
    exit()

if alst[0] == 1:
    if xor == alst[0] ^ alst[1]:
        print(0)
    else:
        print(-1)
    exit()
    
diff //= 2
total_bin = format(total, "b")
diff_bin = format(diff,"b")
xor_bin = format(xor,"b")
i = len(total_bin)
ans = 0
for j in range(i, 0, -1):
    if j <= len(diff_bin):
        if diff_bin[-j] == "1":
            ans += 2 ** (j - 1)
            continue
for j in range(i, 0, -1):
    if j <= len(diff_bin):
        if diff_bin[-j] == "1":
            continue
    if j <= len(xor_bin):
        if xor_bin[-j] == "0":
            continue    
    if ans + 2 ** (j - 1) < alst[0]:
        ans += 2 ** (j - 1)
if ans == 0 or ans >= alst[0]:
    print(-1)
else:
    print(alst[0] - ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
l = [int(x) for x in input().split()]
hai = 0
b =[0] * N
for j in range(min(l[0]-1,1000)):
    hai = 0
    for k in range(N):
        b[k] = l[k]
    b[0] -= j
    b[1] += j
    for i in range(N):
        hai = hai^b[i]
    if hai == 0:
        print(j)
        exit()
print(-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

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

for i in range(min(10**7,a[0])):
  if (a[0]-i)^(a[1]+i) == c:
    print(i)
    exit()
print(-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
alst = list(map(int, input().split()))
if n == 2:
    if sum(alst) % 2 != 0:
        print(-1)
    elif alst[0] < alst[1]:
        print(-1)
    else:
        print((alst[0] - alst[1]) // 2)
    exit()

if alst.count(1) == n:
    if n % 2 == 0:
        print(0)
    else:
        print(-1)
    exit()

xor = 0
for num in alst[2:]:
    xor ^= num
total = alst[0] + alst[1]
if xor > total:
    print(-1)
    exit()

diff = total - xor
if diff % 2 == 1:
    print(-1)
    exit()

if alst[0] == 1:
    if xor == alst[0] ^ alst[1]:
        print(0)
    else:
        print(-1)
    exit()
    
diff //= 2
total_bin = format(total, "b")
diff_bin = format(diff,"b")
xor_bin = format(xor,"b")
i = len(total_bin)
ans = 0
for j in range(i, 0, -1):
    if j <= len(diff_bin):
        if diff_bin[-j] == "1":
            ans += 2 ** (j - 1)
            continue
for j in range(i, 0, -1):
    if j <= len(diff_bin):
        if diff_bin[-j] == "1":
            continue
    if j <= len(xor_bin):
        if xor_bin[-j] == "0":
            continue    
    if ans + 2 ** (j - 1) < alst[0]:
        ans += 2 ** (j - 1)
if ans == 0 or ans >= alst[0]:
    print(-1)
else:
    print(alst[0] - ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
alst = list(map(int, input().split()))
if n == 2:
    if sum(alst) % 2 != 0:
        print(-1)
    elif alst[0] < alst[1]:
        print(-1)
    else:
        print((alst[0] - alst[1]) // 2)
    exit()

if alst.count(1) == n:
    if n % 2 == 0:
        print(0)
    else:
        print(-1)
    exit()

xor = 0
for num in alst[2:]:
    xor ^= num
total = alst[0] + alst[1]
if xor > total:
    print(-1)
    exit()

diff = total - xor
if diff % 2 == 1:
    print(-1)
    exit()
    
diff //= 2
total_bin = format(total, "b")
diff_bin = format(diff,"b")
xor_bin = format(xor,"b")
i = len(total_bin)
ans = 0
for j in range(i, 0, -1):
    if j <= len(diff_bin):
        if diff_bin[-j] == "1":
            ans += 2 ** (j - 1)
            continue
for j in range(i, 0, -1):
    if j <= len(diff_bin):
        if diff_bin[-j] == "1":
            continue
    if j <= len(xor_bin):
        if xor_bin[-j] == "0":
            continue    
    if ans + 2 ** (j - 1) < alst[0]:
        ans += 2 ** (j - 1)
if ans == 0 or ans >= alst[0]:
    print(-1)
else:
    print(alst[0] - ans)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

xor = lambda x,y:x^y

if N == 2:
    a, b = A[0], A[1]
    if (a+b)%2 == 0 and a > b:
        print(a-(a+b)//2)
    else:
        print(-1)
    exit()

X = reduce(xor, A[2:])
if X == 0:
    print(0)
    exit()
# print(X)
if X%2 != (A[0]+A[1])%2:
    print(-1)
    exit()

a = A[0]
b = A[1]
for i in range(0, min(a, 5*10**6)):
    x = a-i
    y = b+i
    if x^y == X:
        print(i)
        break
else:
    print(-1)

Submission status: Wrong Answer

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

X = A[0]
Y = A[1]
Z = 0
for a in A[2:]:
  Z ^= a

if ((X^Y)&1)!=(Z&1):
  print(-1)
  exit(0)

d = 0
for i in range(1, 100):
  if (((X-d)^(Y+d))>>i&1)!=(Z>>i&1):
    if ((X-(d+(1<<(i-1))))^(Y+(d+(1<<(i-1)))))==((X-(d-1+(1<<(i-1))))^(Y+(d-1+(1<<(i-1))))):
      d += (1<<(i-1))-1
    else:
      d += 1<<(i-1)
if d<X:
  print(d)
else:
  print(-1)

Submission status: Wrong Answer

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

xor = 0
for i in range(2,n):
    xor = xor^a[i]

for i in range(1,min(10**6+1,a[0])):
    if (a[0]-i)^(a[1]+i)^xor==0:
        print(i)
        exit()
print(-1)

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    if n == 2:
        if a[0] < a[1] or sum(a) % 2:
            print(-1)
        else:
            print((a[0] - a[1]) // 2)
        return
    m = max(a).bit_length()
    b = [0] * m
    for ai in a:
        c = ai
        for k in range(m):
            b[k] += c % 2
            c //= 2
    e = 0
    for i, bi in enumerate(b):
        if bi % 2:
            e += 2**i
    if e % 2:
        print(-1)
        return
    if e // 2 < a[0]:
        print(e // 2)
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

if n == 2:
  if a[0] >= a[1] and (a[0] - a[1]) % 2 == 0:
    print((a[0] - a[1]) // 2)
  else:
    print(-1)
else:
  num = 0
  for i in range(2, n):
    num ^= a[i]
  
  _and = (a[0] + a[1] - num)
  if  _and % 2 != 0 or a[0] < _and // 2:
    print(-1)
  else:
    _and //= 2
    
    max_2 = 1
    while max_2 * 2 <= num:
      max_2 *= 2
    
    a0 = _and
    while max_2 >= 1:
      if num & max_2 != 0 and a0 + max_2 < a[0]:
        a0 += max_2
      max_2 //= 2
    
    if a0 != 0 and a0 != a[0]:
      print(a[0] - a0)
    else:
      print(-1)

Submission status: Wrong Answer

Solution code:
def compute(S, X): 
  A = (S - X)//2
  a = 0
  b = 0
  ambiguous=[0]*64
  for i in range(64): 
    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)  
      b = ((1 << i) | b)  
    elif (Xi > 0 and Ai == 0): 
      ambiguous[i]=1
    else:
      print(-1) 
      return
  firsti=-1
  for i in range(63,-1,-1):
    temp = (a1[1] & (1 << i)) 
    Ai = (a & (1 << i)) 
    if Ai>temp:
      firsti=i
      break
  for i in range(63,-1,-1):
    temp = (a1[1] & (1 << i)) 
    if ambiguous[i]==1:
      if i>firsti:
        if temp>0:
          a = ((1 << i) | a) 
        else:
          a = ((0 << i) | a)
      if i<=firsti:
        a = ((0 << i) | a)
  if a>=a1[1]:
    print(a-a1[1])
    return
  flag=0
  for i in range(64):
    temp = (a1[1] & (1 << i)) 
    Ai = (a & (1 << i)) 
    if ambiguous[i]==1 and Ai==0:
      a = ((1 << i) | a)
      break
    if i==63:
      print(-1)
      flag=1
  if flag==1:
    return
  if a<a1[1] or S==a:
    print(-1)
  else:
    print(a-a1[1])
  
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:
n = int(input())
alst = list(map(int, input().split()))
if n == 2:
    if sum(alst) % 2 != 0:
        print(-1)
    elif alst[0] < alst[1]:
        print(-1)
    else:
        print((alst[0] - alst[1]) // 2)
    exit()

xor = 0
for num in alst[2:]:
    xor ^= num
total = alst[0] + alst[1]
if xor > total:
    print(-1)
    exit()

diff = total - xor
if diff % 2 == 1:
    print(-1)
    exit()
    
diff //= 2
total_bin = format(total, "b")
diff_bin = format(diff,"b")
xor_bin = format(xor,"b")
i = len(total_bin)
ans = 0
for j in range(i, 0, -1):
    if j <= len(diff_bin):
        if diff_bin[-j] == "1":
            ans += 2 ** (j - 1)
            continue
for j in range(i, 0, -1):
    if j <= len(diff_bin):
        if diff_bin[-j] == "1":
            continue
    if j <= len(xor_bin):
        if xor_bin[-j] == "0":
            continue    
    if ans + 2 ** (j - 1) < alst[0]:
        ans += 2 ** (j - 1)
if ans == 0 or ans >= alst[0]:
    print(-1)
else:
    print(alst[0] - ans)

Submission status: Wrong Answer

Solution code:
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
    r = 0
    for i in reversed(range(1,40)):
        if (a ^ b ^ x) & (1 << i) == 0:
            continue
        for j in range(0, i):
            if r & (1 << j):
                continue
            aa = a - (1 << j)
            bb = b + (1 << j)
            a = aa
            b = bb
            r |= (1 << j)
            if (aa ^ bb ^ x) & (1 << i) == 0:
                break
        else:
            return -1
    if r >= A[0]:
        return -1
    return r

print(main())

Submission status: Wrong Answer

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

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

    if N == 2:
        if A[0] == A[1]:
            print(0)
        elif A[0] < A[1]:
            print(-1)
        else:
            if (A[0] - A[1]) %2 == 0:
                print((A[0] -  A[1])//2)
            else:
                print(-1)
        exit()

    g1 = A[0]
    g2 = A[1]
    g3 = 0
    for i in range(2, N):
        g3 ^= A[i]
    n1 = g1.bit_length()
    n2 = g2.bit_length()
    n3 = g3.bit_length()
    NN = max(n1, n2, n3)
    ans = 0
    cnt = 0
    while True:
        cnt += 1
        if cnt == 100:
            print(-1)
            exit()
        for i in range(NN):
            if (g1 >> i & 1) ^ (g2 >> i & 1) != (g3 >> i & 1):
                r1 = g1 % (1 << i) + 1
                r2 = (1<<i) - g2 % (1 << i)
                if r1 < r2:
                    g1 -= r1
                    g2 += r1
                    ans += r1
                    break
                elif r1 > r2:
                    g1 -= r2
                    g2 += r2
                    ans += r2
                    break
                else:
                    print(-1)
                    exit()
            if g1 ^ g2 == g3:
                if ans != A[0]:
                    print(ans)
                else:
                    print(-1)
                exit()


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
alst = list(map(int, input().split()))
if n == 2:
    if sum(alst) % 2 != 0:
        print(-1)
    elif alst[0] < alst[1]:
        print(-1)
    else:
        print((alst[0] - alst[1]) // 2)
    exit()

xor = 0
for num in alst[2:]:
    xor ^= num
total = alst[0] + alst[1]
if xor > total:
    print(-1)
    exit()

diff = total - xor
if diff % 2 == 1:
    print(-1)
    exit()
    
diff //= 2
total_bin = format(total, "b")
diff_bin = format(diff,"b")
xor_bin = format(xor,"b")
i = len(total_bin)
ans = 0
for j in range(i, 0, -1):
    if j <= len(diff_bin):
        if diff_bin[-j] == "1":
            ans += 2 ** (j - 1)
            continue
for j in range(i, 0, -1):
    if j <= len(diff_bin):
        if diff_bin[-j] == "1":
            continue
    if j <= len(xor_bin):
        if xor_bin[-j] == "0":
            continue    
    if ans + 2 ** (j - 1) <= alst[0]:
        ans += 2 ** (j - 1)
if ans == 0 or ans >= alst[0]:
    print(-1)
else:
    print(alst[0] - ans)

Submission status: Wrong Answer

Solution code:
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
    r = 0
    for i in reversed(range(1,40)):
        if (a ^ b ^ x) & (1 << i) == 0:
            continue
        for j in range(0, i):
            if r & (1 << j):
                continue
            aa = a - (1 << j)
            bb = b + (1 << j)
            a = aa
            b = bb
            r |= (1 << j)
            if (aa ^ bb ^ x) & (1 << i) == 0:
                break
        else:
            return -1
    return r

print(main())

Submission status: Wrong Answer

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

if n == 2:
  if a[0] >= a[1] and (a[0] - a[1]) % 2 == 0:
    print((a[0] - a[1]) // 2)
  else:
    print(-1)
else:
  num = 0
  for i in range(2, n):
    num ^= a[i]
  
  _and = (a[0] + a[1] - num)
  if a[0] < _and or _and % 2 != 0:
    print(-1)
  else:
    _and //= 2
    
    max_2 = 1
    while max_2 * 2 <= num:
      max_2 *= 2
    
    a0 = _and
    while max_2 >= 1:
      if num & max_2 != 0 and a0 + max_2 <= a[0]:
        a0 += max_2
      max_2 //= 2
    
    if a0 != 0 and a0 != a[0]:
      print(a[0] - a0)
    else:
      print(-1)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
C=A[:]
X=0
for i in range(2,N):
  X^=A[i]
if (A[0]^A[1]^X)==0:
  print(0)
  exit()
B=A[0]
Y=1<<50
P=0
Z=0
for i in range(50):
  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)
C[0]-=P
C[1]+=P
X=0
for i in range(N):
  X^=C[i]
if X==0 and C[0]>0 and P>=0:
  print(P)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
alst = list(map(int, input().split()))
if n == 2:
    if sum(alst) % 2 != 0:
        print(-1)
    elif alst[0] < alst[1]:
        print(-1)
    else:
        print((alst[0] - alst[1]) // 2)
    exit()

xor = 0
for num in alst[2:]:
    xor ^= num
total = alst[0] + alst[1]
if xor > total:
    print(-1)
    exit()
    
if xor == total:
    print(0)
    exit()

diff = total - xor
if diff % 2 == 1:
    print(-1)
    exit()
    
diff //= 2
total_bin = format(total, "b")
diff_bin = format(diff,"b")
xor_bin = format(xor,"b")
i = len(total_bin)
ans = 0
for j in range(i, 0, -1):
    if j <= len(diff_bin):
        if diff_bin[-j] == "1":
            ans += 2 ** (j - 1)
            continue
for j in range(i, 0, -1):
    if j <= len(diff_bin):
        if diff_bin[-j] == "1":
            continue
    if j <= len(xor_bin):
        if xor_bin[-j] == "0":
            continue    
    if ans + 2 ** (j - 1) <= alst[0]:
        ans += 2 ** (j - 1)
if ans == 0 or ans > alst[0]:
    print(-1)
else:
    print(alst[0] - ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
C=A[:]
X=0
for i in range(2,N):
  X^=A[i]
if (A[0]^A[1]^X)==0:
  print(0)
  exit()
B=A[0]
Y=1<<50
P=0
Z=0
for i in range(50):
  Y>>=1
  print(Y)
  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)
C[0]-=P
C[1]+=P
X=0
for i in range(N):
  X^=C[i]
if X==0 and C[0]>0 and P>=0:
  print(P)
else:
  print(-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

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

for i in range(a[0]):
  if (a[0]-i)^(a[1]+i) == c:
    print(i)
    break

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
C=A[:]
X=0
for i in range(2,N):
  X^=A[i]
if (A[0]^A[1]^X)==0:
  print(0)
  exit()
B=A[0]
Y=1<<50
P=0
Z=0
for i in range(50):
  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)
C[0]-=P
C[1]+=P
X=0
for i in range(N):
  X^=C[i]
if X==0 and C[0]>0:
  print(P)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
C=A[:]
X=0
for i in range(2,N):
  X^=A[i]
if X==0:
  print(0)
  exit()
B=A[0]
Y=1<<50
P=0
Z=0
for i in range(50):
  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)
C[0]-=P
C[1]+=P
X=0
for i in range(N):
  X^=C[i]
if X==0 and C[0]>0:
  print(P)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
alst = list(map(int, input().split()))
if n == 2:
    if sum(alst) % 2 != 0:
        print(-1)
    elif alst[0] == alst[1] == 2:
        print(-1)
    elif alst[0] < alst[1]:
        print(-1)
    else:
        print((alst[0] - alst[1]) // 2)
    exit()

xor = 0
for num in alst[2:]:
    xor ^= num
total = alst[0] + alst[1]
if xor > total:
    print(-1)
    exit()

diff = total - xor
if diff % 2 == 1:
    print(-1)
    exit()
    
diff //= 2
total_bin = format(total, "b")
diff_bin = format(diff,"b")
xor_bin = format(xor,"b")
i = len(total_bin)
ans = 0
for j in range(i, 0, -1):
    if j <= len(diff_bin):
        if diff_bin[-j] == "1":
            ans += 2 ** (j - 1)
            continue
for j in range(i, 0, -1):
    if j <= len(diff_bin):
        if diff_bin[-j] == "1":
            continue
    if j <= len(xor_bin):
        if xor_bin[-j] == "0":
            continue    
    if ans + 2 ** (j - 1) <= alst[0]:
        ans += 2 ** (j - 1)
if ans == 0 or ans > alst[0]:
    print(-1)
else:
    print(alst[0] - ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
lis = list(map(int,input().split()))
num = 0
for i in range(2,n):
    num ^= lis[i]
if lis[0] + lis[1] < num:
    print(-1)
    exit()
a = lis[0]
b = lis[1]
nu = a + b-num
if nu % 2 != 0:
    print(-1)
    exit()
print(format(a,"b"),format(b,"b"),nu,format(num,"b"))

Submission status: Wrong Answer

Solution code:
import sys
def input():return sys.stdin.readline()[:-1]
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
n=N()
l=L()
sx=0
for i in l[2:]:
    sx^=i
if sx>l[0]+l[1]:
    print(-1)
    quit()
if (l[0]+l[1]-sx)%2==1:
    print(-1)
    quit()
if sx^l[0]^l[1]==0:
    print(0)
    quit()
x=(l[0]+l[1]-sx)//2
y=x
if x>l[0]:
    print(-1)
    quit()
for i in range(45,-1,-1):
    if sx>>i&1:
        if l[0]>=(x+(1<<i)):
            x+=(1<<i)
if x==0:
    print(-1)
    quit()
print(l[0]-x)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
C=A[:]
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)
C[0]-=P
C[1]+=P
X=0
for i in range(N):
  X^=C[i]
if X==0 and C[0]>0:
  print(P)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
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
    r = 0
    for i in reversed(range(1,40)):
        if (a ^ b ^ x) & (1 << i) == 0:
            continue
        for j in reversed(range(0, i)):
            aa = a - (1 << j)
            bb = b + (1 << j)
            if (aa ^ bb ^ x) & (1 << i) == 0:
                a = aa
                b = bb
                r |= (1 << j)
                break
        else:
            return -1
    if r >= A[0]:
        return -1
    for i in range(max(0, r - 1000), r):
        if (A[0] - i) ^ (A[1] + i) ^ x == 0:
            return i
    return r

print(main())

Submission status: Wrong Answer

Solution code:
n = int(input())
alst = list(map(int, input().split()))
if n == 2:
    if sum(alst) % 2 != 0:
        print(alst[0] - 1)
    elif alst[0] < alst[1]:
        print(-1)
    else:
        print((alst[0] - alst[1]) // 2)
    exit()

xor = 0
for num in alst[2:]:
    xor ^= num
total = alst[0] + alst[1]
if xor > total:
    print(-1)
    exit()

diff = total - xor
if diff % 2 == 1:
    print(-1)
    exit()
    
diff //= 2
total_bin = format(total, "b")
diff_bin = format(diff,"b")
xor_bin = format(xor,"b")
i = len(total_bin)
ans = 0
for j in range(i, 0, -1):
    if j <= len(diff_bin):
        if diff_bin[-j] == "1":
            ans += 2 ** (j - 1)
            continue
for j in range(i, 0, -1):
    if j <= len(diff_bin):
        if diff_bin[-j] == "1":
            continue
    if j <= len(xor_bin):
        if xor_bin[-j] == "0":
            continue    
    if ans + 2 ** (j - 1) <= alst[0]:
        ans += 2 ** (j - 1)
if ans == 0 or ans > alst[0]:
    print(-1)
else:
    print(alst[0] - ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
xorValue = 0
sumValue = A[0] + A[1]
for i in range(2,N):
    xorValue ^= A[i]
if sumValue % 2 != xorValue % 2:
    print(-1)
else:
    Base = (sumValue - xorValue) // 2
    if Base > A[0]:
        print(-1)
    else:
        strXOR = bin(xorValue)[2:]
        minStoneMovement = A[0] - Base
        strBase = bin(Base)[2:]
        lenStrXOR = len(strXOR)
        cannotMove = False
        for i in range(-1,-1 * min(len(strXOR),len(strBase)) - 1,-1):
            if strBase[i] == '1' and strXOR[i] == '1':
                cannotMove = True
                break
        if not cannotMove:
            for i in range(lenStrXOR):
                if strXOR[i] == '1' and minStoneMovement >= 2 ** (lenStrXOR - 1 - i):
                    minStoneMovement -= 2 ** (lenStrXOR - 1 - i)
        if minStoneMovement == A[0] or cannotMove:
            print(-1)
        else:
            print(minStoneMovement)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
if set(A)==set([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 = int(input())
A = list(map(int, input().split()))

X = A[0]
Y = A[1]
Z = 0
for a in A[2:]:
  Z ^= a

def check(X2, Y2):
  if ((X2^Y2)&1)!=(Z&1):
    return -1

  d = 0
  for i in range(1, 100):
    if (((X2-d)^(Y2+d))>>i&1)!=(Z>>i&1):
      d |= 1<<(i-1)
  if d<X:
    return d
  else:
    return -1

if check(X, Y)==-1:
  print(-1)
  exit(0)

ans = 0
b = 1
while b<2**64:
  c0 = check(X-ans, Y+ans)
  c1 = check(X-(ans+b), Y+(ans+b))
  if c1!=-1 and c1<=c0 and ans+b<X:
    ans += b
  b *= 2
print(ans)

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=int(input())
A=list(map(int,input().split()))
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)