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:
import numpy as np
n=int(input())
a=np.array(list(map(int,input().split())))
s=np.bitwise_xor.reduce(a)
if s==0:
  print(0)
  exit()
for i in range(a[0]):
  a[1]+=1
  a[0]+=-1
  s=np.bitwise_xor.reduce(a)
  if s ==0:
    print(i+1)
    exit()
print(-1)
#b=np.bitwise_xor(a,s)
#print(" ".join((str(x) for x in b)))

Submission status: Wrong Answer

Solution code:
import sys


def solve(n, aaa):
    x = 0
    for a in aaa[2:]:
        x ^= a
    a0, a1 = aaa[:2]
    s = a0 + a1

    if s & 1 != x & 1:
        return -1

    p, q = 0, 0

    b = 1 << 40
    while b:
        bx = x & b
        if bx == 0:
            # print('bx', s)
            # print(f'{b:040b}')
            # print(f'{p:040b}')
            # print(f'{q:040b}')
            # print(f'{a0:040b}')
            # print(f'{a1:040b}')
            # print()
            if s >= 2 * b:
                if p + b <= a0:
                    p |= b
                    q |= b
                    s -= 2 * b
                else:
                    return -1
        else:
            if s < b:
                return -1
            if p + b <= a0 and q + b > a1:
                p |= b
            else:
                q |= b
            s -= b

        # print(f'{b:040b}')
        # print(f'{p:040b}')
        # print(f'{q:040b}')
        # print(f'{a0:040b}')
        # print(f'{a1:040b}')
        # print()

        b >>= 1

    if p == 0:
        return -1
    return a0 - p


n, *aaa = map(int, sys.stdin.buffer.read().split())
print(solve(n, aaa))

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 <= 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:
      print(a[0] - a0)
    else:
      print(-1)

Submission status: Wrong Answer

Solution code:
import sys
N=int(input())
A=list(map(int,input().split()))
if N==2:
  if A[0]>A[1] and sum(A)%2==0:
    print((sum(A)//2)-A[1])
    sys.exit()
  else:
    print(-1)
    sys.exit()
if N>2:
  s=A[2]
  for i in range(3,N):
    s=s^A[i]
  t=bin(s)
  if s>A[0]+A[1]:
    print(-1)
    sys.exit()
  n=A[0]+A[1]-s
  o=bin(n)
  m=int(o,0)
  if m%2==1:
    print(-1)
    sys.exit()
  m=m//2
  if (s+m)^m!=s:
    print(-1)
    sys.exit()
  print(m-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]:
        b0 = [(a[0] - e // 2) // 2**i % 2 for i in range(m)]
        b1 = [(a[1] - e // 2) // 2**i % 2 for i in range(m)]
        for i in range(m - 1, -1, -1):
            if 2**i > a[0]:
                continue
            if b0[i] == 0 and b1[i] == 1:
                b0[i] = 1
        print(a[0] - sum(b0[i] * 2**i for i in range(m)))
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

start = a[0]
a,b = a[0],a[1]
if((a^b)==c):
    print(0)
    exit()

dif = a+b-c
if(dif%2==1):
    print(-1)
    exit()

dif = dif//2
for i in range(40):
    if((c >> i)&1)&((dif >> i)&1):
        print(-1)
        exit()

if(dif > c):
    print(-1)
    exit()

goal = dif

for i in range(40,-1,-1):
    if(c >> i)&1:
        if(goal + 2**i <= start):
            goal += 2**i

print(start-goal)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n = int(readline())
lst2 = list(map(int,readline().split()))

res = 0
for i in lst2:
    res = res^i
print(res)
lst1 = []
for i in range(len(bin(res))):
    lst1.append((res>>i)&1)
if sum(lst1) == 0:
    print(0)
elif sum(lst1) == 1:
    if lst1[0] == 1:
        print(-1)
        exit()
    else:
        for i in range(len(lst1)):
            if lst1[i] == 1:
                if lst2[0] >= 1<<i:
                    print(i)
                    exit()
print(-1)

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()
a = format(a,"b")
b = format(b,"b")
num = format(num,"b")
l = max(len(a),len(b),len(num))
a = int(a,2)
b = int(b,2)
num = int(num,2)
a = format(a,"b").zfill(l)
b = format(b,"b").zfill(l)
num = format(num,"b").zfill(l)


ans = 0

for i in range(len(a)):
    if b[-(i+1)] == "0" and num[-(i+1)] == "1":
        if a[-(i+1)] != "1":
            print(-1)
            exit()
        else:
            ans += 2 ** (i+1)-1
            a = int(a,2)
            a -= 2 ** i
            a = format(a,"b").zfill(l)
    elif b[-(i+1)] == "1" and num[-(i+1)] == "0":
        ans += 2 ** i
        b = int(b,2)
        b += 2 ** i
        b = format(b,"b").zfill(l)
        a = int(a,2)
        a -= 2 ** i
        if a < 0:
            print(-1)
            exit()
        a = format(a,"b").zfill(l)
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
x=0
for i in range(2,N):
    x=x^A[i]
A=A[0]+A[1]
for k in range(0,A+1):
    if k^(A-k)==x:
        print(x)
        exit()

Submission status: Wrong Answer

Solution code:
n=int(input())
a,b,*c=map(int,input().split())
aaa=a
bbb=b
x=0
for i in c:x^=i
t=[0]*41
xt=[0]*41
c=a+b
for i in range(41):
  if c&(1<<i):t[i]=1
  if x&(1<<i):xt[i]=1
for i in range(40,0,-1):
  if t[i]>=4:exit(print(-1))
  if xt[i]==0:
    tt=t[i]%2
    t[i]-=tt
    t[i-1]+=tt*2
  else:
    if t[i]==0:
      exit(print(-1))
    tt=(t[i]+1)%2
    t[i]-=tt
    t[i-1]+=tt*2
ans=0
for i in range(40,0,-1):
  z=1<<i
  if t[i]==0:
    if a&z:
      ans+=a-z+1
      b+=a-z+1
      a-=a-z+1
  if t[i]==1:
    if (a&z)==(b&z)==0:
      v=z-b
      ans+=v
      b+=v
      a-=v
    elif (a&z)==(b&z)==z:
      ans+=a-z+1
      b+=a-z+1
      a-=a-z+1
  if t[i]==2:
    if (b&z)==0:
      v=z-b
      ans+=v
      b+=v
      a-=v
  if a&z:a-=z
  if b&z:b-=z
if aaa==ans:exit(print(-1))
if (aaa-ans)^(bbb+ans)!=x:exit(print(-1))
print(ans)

Submission status: Wrong Answer

Solution code:
#                          JAI SHREE RAM

import math; from collections import *
import sys; from functools import reduce

def get_ints(): return map(int, input().strip().split())
def get_list(): return list(get_ints())
def getlistofstring(): return list(input().strip().split())
def printxsp(*args): return print(*args, end="")
def printsp(*args): return print(*args, end=" ")

UGLYMOD = int(1e9)+7; SEXYMOD = 998244353; MAXN = int(1e5)

# sys.setrecursionlimit(10**6)
# sys.stdin=open("input.txt","r");sys.stdout=open("output.txt","w")

# for _testcases_ in range(int(input())):
def compute(A, X, a, b):
    x = ['0'] * 32
    y = ['0'] * 32
    A = bin(A)[2:].zfill(32)
    X = bin(X)[2:].zfill(32)
    # print(A, X, sep = '\n')
    for i in range(32):
        if A[i] == '1':
            x[i] = y[i] = '1'
            a -= (2**(32-i-1))
            b -= (2**(32-i-1))
        elif A[i] == '0' and X[i] == '1':
            if a >= b:
                x[i] = '1'
                y[i] = '0'
                a -= (2**(31-i))
            else:
                x[i] = '0'
                y[i] = '1'
                b -= (2**(31-i))
    ans1 = ans2 = ''
    
    for i in x:
        ans1 += i
    for i in y:
        ans2 += i
    # print(ans1, ans2)
    return [ans1, ans2]



n = int(input())
li = get_list()

S = li[0] + li[1]
try:
    X = reduce(lambda x, y: x ^ y, li[2:])
except:
    X = 0

A = (S - X) / 2
if A != math.floor(A):
    print('-1')
else:
    # print(A, X)
    x, y = compute(int(A), X, li[0], li[1])
    if x == -1:
        print(x)
    else:
        x = int(x, 2)
        y = int(y, 2)
        # print(x, y)
        x, y = min(x, y), max(x, y)
        if x > li[0]:
            print(-1)
        else:
            print(li[0] - x)

'''
>>> COMMENT THE STDIN!! CHANGE ONLINE JUDGE !!
THE LOGIC AND APPROACH IS MINE @luctivud ( UDIT GUPTA )
Link may be copy-pasted here if it's taken from other source.
DO NOT PLAGIARISE.
>>> COMMENT THE STDIN!! CHANGE ONLINE JUDGE !!
'''

Submission status: Wrong Answer

Solution code:
import random

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)

def solve(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<X2:
    return d
  else:
    return -1

ans = solve(X, Y)
for i in range(50000):
  if ans<=2:
    break
  r = random.randint(1, ans-1)
  a = solve(X-r, Y+r)
  if a!=-1 and r+a<ans:
    ans = r+a
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
n=int(input())
a=np.array(list(map(int,input().split())))
s=np.bitwise_xor.reduce(a)
if s==0:
  print(0)
  exit()
for i in range(a[0]):
  a[1]+=1
  a[0]+=-1
  s=np.bitwise_xor.reduce(a)
  if s ==0:
    print(i)
    exit()
print(-1)
#b=np.bitwise_xor(a,s)
#print(" ".join((str(x) for x in b)))

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*7)):
    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())
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()
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])+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
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    N = int(input())
    A = list(map(int,input().split()))
    X = 0
    for i in range(2,N):
        X ^= A[i]
    if A[0]^A[1] == X:
        print(0)
        return
    a = A[0]
    b = A[1]
    C = a + b
    ans = -1
    for i in range(40000000):
        if (a - i)^(b + i) == X:
            ans = i
            break
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
xsm = 0
for i in range(2, N): xsm ^= a[i]
for x in range(min(a[0], 10 ** 6 + 1)):
  if (a[0] - x) ^ (a[1] + x) ^ xsm == 0:
    print(x)
    exit(0)
print(-1)

Submission status: Wrong Answer

Solution code:
import sys
n = int(input())
a = list(map(int, input().split()))
c = a[0] + a[1]

t = 0

for ai in a[2:]:
    t = t ^ ai

bit_len = c.bit_length()+1

if c < t:
    print(-1)
    sys.exit()

if (c-t) % 2:
    print(-1)
    sys.exit()

b1 = (c - t) // 2


a1 = b1
a2 = b1


if a1 > a[0]:
    print(-1)
    sys.exit()
    

for i in reversed(range(bit_len)):
    if t & (1 << i):
        if a1 + 2 ** i <= a[0]:
            a1 += 2 ** i

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

Submission status: Wrong Answer

Solution code:
#!python3

LI = lambda: list(map(int, input().split()))

# input
N = int(input())
A = LI()


def main():
    s = 0
    for a in A[2:]:
        s ^= a
    for i in range(A[0] + 1):
        a = A[0] - i
        b = A[1] + i
        if s ^ a ^ b == 0:
            print(i)
            return
    print(-1)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
N=int(input())
A=list(map(int,input().split()))
if N==2:
  if A[0]>A[1] and sum(A)%2==0:
    print((sum(A)//2)-A[1])
    sys.exit()
  else:
    print(-1)
    sys.exit()
if N>2:
  s=A[2]
  for i in range(3,N):
    s=s^A[i]
  t=bin(s)
  if s>A[0]+A[1]:
    print(-1)
    sys.exit()
  n=A[0]+A[1]-s
  o=bin(n)
  m=int(o,0)
  if m%2==1:
    print(-1)
    sys.exit()
  m=m//2
  if (s+m)^m!=s:
    print(-1)
    sys.exit()
  print(1)

Submission status: Wrong Answer

Solution code:
n=int(input())
a,b,*c=map(int,input().split())
aaa=a
bbb=b
x=0
for i in c:x^=i
t=[0]*41
xt=[0]*41
c=a+b
for i in range(41):
  if c&(1<<i):t[i]=1
  if x&(1<<i):xt[i]=1
for i in range(40,0,-1):
  if t[i]>=4:exit(print(-1))
  if xt[i]==0:
    tt=t[i]%2
    t[i]-=tt
    t[i-1]+=tt*2
  else:
    if t[i]==0:
      exit(print(-1))
    tt=(t[i]+1)%2
    t[i]-=tt
    t[i-1]+=tt*2
ans=0
for i in range(40,0,-1):
  z=1<<i
  if t[i]==0:
    if a&z:
      ans+=a-z+1
      b+=a-z+1
      a-=a-z+1
    if b&z:
      exit(print(-1))
  if t[i]==1:
    if (a&z)==(b&z)==0:
      v=z-b
      ans+=v
      b+=v
      a-=v
      if a<0:exit(print(-1))
    elif (a&z)==(b&z)==z:
      ans+=a-z+1
      b+=a-z+1
      a-=a-z+1
  if t[i]==2:
    if (b&z)==0:
      v=z-b
      ans+=v
      b+=v
      a-=v
    if not((a&z)==(b&z)==z):exit(print(-1))
  if a&z:a-=z
  if b&z:b-=z
if aaa==ans:exit(print(-1))
if (aaa-ans)^(bbb+ans)!=x:exit(print(-1))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
n = int(input())
a = list(map(int, input().split()))
c = a[0] + a[1]

t = 0

for ai in a[2:]:
    t = t ^ ai

bit_len = c.bit_length()+1

if c < t:
    print(-1)
    sys.exit()

if (c-t) % 2:
    print(-1)
    sys.exit()

b1 = (c - t) // 2


a1 = b1
a2 = b1


if a1 > a[0]:
    sys.exit()
    print(-1)

for i in reversed(range(bit_len)):
    if t & (1 << i):
        if a1 + 2 ** i <= a[0]:
            a1 += 2 ** i

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

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()
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]),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())
A = list(map(int, input().split()))
if A[0] == 1:
  print("-1")
  quit()

if N == 2:
  if A[0] < A[1]:
    print("-1")
    quit()
  elif (A[0] + A[1]) % 2 == 1:
    print("-1")
    quit()
  else:
    half = (A[0] + A[1]) // 2
    print(int(A[0] - half))
    quit()

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

if now == 0:
  print("-1")
else:
  a = A[0] ^ A[1]
  b = a ^ now
  if a ^ b == 0:
    print(0)
    quit()
  c = int((A[0] + A[1]) // 2) + 1
  d = A[0] + A[1] - c
  #print(A[0] + A[1])
  #print(c + d, c, d)
  if c > d:
    c, d = d, c
  mm = abs(d - A[0])
  #print(mm)
  while mm >= 0:
    e = (A[0] + mm) ^ (A[1] - mm)
    if e ^ b == 0:
      print(mm)
      quit()
    mm -= 1
  print(-1)

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]

x = "{:b}".format(X)
y = "{:b}".format(a^b)
l = max(len(x), len(y))
x = x.zfill(l)
y = y.zfill(l)

ans = 0
for i in range(l):
    if x[i]!=y[i]:
        ans += l-i-1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
n = int(input())
a = list(map(int, input().split()))
c = a[0] + a[1]

t = 0

for ai in a[2:]:
    t = t ^ ai

bit_len = c.bit_length()+1

if c < t:
    print(-1)
    sys.exit()

if (c-t) % 2:
    print(-1)
    sys.exit()

b1 = (c - t) // 2


a1 = b1
a2 = b1


if a1 > a[0]:
    sys.exit()

for i in reversed(range(bit_len)):
    if t & (1 << i):
        if a1 + 2 ** i <= a[0]:
            a1 += 2 ** i

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    ref=0
    for i in range(2,N):
        ref^=A[i]
    
    a0=A[0]
    a1=A[1]
    ans=0
    #print(bin(a0),bin(a1),bin(ref))
    def dfs(a0,a1,ref):
        q=[(0,a0,a1,ref,0)]
        visited=set()
        while len(q):
            tot,a0,a1,ref,j=heappop(q)#ここをpopleftにすると幅優先探索BFSになる
            
            if a0 in visited:
                continue
            if a0^a1==ref:
                return tot
            visited.add(a0)


            if ((a0>>j)&1)^((a1>>j)&1)!=ref&1:
                a0-=1<<j
                a1+=1<<j
                if a0>=0:
                    heappush(q,(tot+(1<<j),a0,a1,ref,j+1))
            else:
                heappush(q,(tot,a0,a1,ref,j+1))
                a0-=1<<j
                a1+=1<<j

                if a0>=0:
                    heappush(q,(tot+(1<<j),a0,a1,ref,j+1))
        return -1
    print(dfs(a0,a1,ref))
    # for j in range(0,41):
    #     a0j=(a0>>j)&1
    #     a1j=(a1>>j)&1
        
    #     refj=(ref>>j)&1
    #     #print(a0j,a1j,refj)
    #     if a0j^a1j==refj:
    #         nref=(ref>>(j+1))&1

    #         na0=((a0>>(j+1))&1)
    #         na1=((a1>>(j+1))&1)
            
    #         if ((a0>>(j+1))&1)^((a1>>(j+1))&1)!=nref:
    #             #print("a",na0,na1,nref)
    #             shif=1<<j
    #             if a0>0 and (((a0-shif))^(((a1+shif))==ref:
    #                 ans+=shif
    #                 a0-=shif
    #                 a1+=shif


    #         continue
    #     else:
    #         shif=1<<j

    #         ans+=shif
    #         a0-=shif
    #         a1+=shif
    #         #print(shif,a0,a1)
    #         if a0<0:
    #             print(-1)
    #             return









if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import random

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)

def solve(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<X2:
    return d
  else:
    return -1

ans = solve(X, Y)
for i in range(10000):
  if ans<=2:
    break
  r = random.randint(1, ans-1)
  a = solve(X-r, Y+r)
  if a!=-1 and r+a<ans:
    ans = r+a
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
A = list(map(int,input().split()))
ALL = 0
for a in A:
    ALL ^= a

ALL ^= A[0] ^ A[1]

K = A[0] + A[1]
L = []

for i in range(40, -1, -1):
    if (1 << i) & ALL:
        L.append(1)
        K -= (1 << i)
    else:
        if K >= 2 * (1 << i):
            L.append(2)
            K -= 1 << (i + 1)
        else:
            L.append(0)

if K != 0:
    print(-1)
    sys.exit()

ans = 0
for i in range(41):
    if L[i] == 2:
        ans += 1 << (40 - i)

if ans >= A[0]:
    print(-1)
    sys.exit()

for i in range(41):
    if L[i] == 1:
        if ans + (1 << (40 - i)) < A[0]:
            ans += 1 << (40 - i)

if ans == 0:
    print(-1)
    sys.exit()

print(A[0] - ans)

Submission status: Wrong Answer

Solution code:
import sys


def solve(n, aaa):
    if n == 2:
        h, m = divmod(sum(aaa), 2)
        if m == 1 or h >= aaa[0]:
            return -1
        return aaa[0] - h

    x = 0
    for a in aaa[2:]:
        x ^= a
    a0, a1 = aaa[:2]
    s = a0 + a1

    if s & 1 != x & 1:
        return -1

    p, q = 0, 0

    b = 1 << 40
    while b:
        bx = x & b
        if bx == 0:
            # print('bx', s)
            # print(f'{b:040b}')
            # print(f'{p:040b}')
            # print(f'{q:040b}')
            # print(f'{a0:040b}')
            # print(f'{a1:040b}')
            # print()
            if s >= 2 * b:
                if p + b <= a0:
                    p |= b
                    q |= b
                    s -= 2 * b
                else:
                    return -1
        else:
            if s < b:
                return -1
            if p + b <= a0 and q + b > a1:
                p |= b
            else:
                q |= b
            s -= b

        # print(f'{b:040b}')
        # print(f'{p:040b}')
        # print(f'{q:040b}')
        # print(f'{a0:040b}')
        # print(f'{a1:040b}')
        # print()

        b >>= 1

    if p == 0:
        return -1
    return a0 - p


n, *aaa = map(int, sys.stdin.buffer.read().split())
print(solve(n, aaa))

Submission status: Wrong Answer

Solution code:
n=int(input())
a,b,*c=map(int,input().split())
aaa=a
bbb=b
x=0
for i in c:x^=i
t=[0]*41
xt=[0]*41
c=a+b
for i in range(41):
  if c&(1<<i):t[i]=1
  if x&(1<<i):xt[i]=1
for i in range(40,0,-1):
  if t[i]>=4:exit(print(-1))
  if xt[i]==0:
    tt=t[i]%2
    t[i]-=tt
    t[i-1]+=tt*2
  else:
    if t[i]==0:
      exit(print(-1))
    tt=(t[i]+1)%2
    t[i]-=tt
    t[i-1]+=tt*2
ans=0
for i in range(40,0,-1):
  z=1<<i
  if t[i]==0:
    if a&z:
      ans+=a-z+1
      b+=a-z+1
      a-=a-z+1
    if b&z:
      exit(print(-1))
  if t[i]==1:
    if (a&z)==(b&z)==0:
      if (a&(z//2)):
        b+=z//2
        ans+=z//2
        a-=z//2
      else:
        exit(print(-1))
    elif (a&z)==(b&z)==z:
      ans+=a-z+1
      b+=a-z+1
      a-=a-z+1
  if t[i]==2:
    if (b&z)==0:
      v=z-b
      ans+=v
      b+=v
      a-=v
    if not((a&z)==(b&z)==z):exit(print(-1))
  if a&z:a-=z
  if b&z:b-=z
if aaa==ans:exit(print(-1))
if (aaa-ans)^(bbb+ans)!=x:exit(print(-1))
print(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

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

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    N = int(input())
    A = list(map(int,input().split()))
    X = 0
    for i in range(2,N):
        X ^= A[i]
    if A[0]^A[1] == X:
        print(0)
        return
    a = A[0]
    b = A[1]
    C = a + b
    ans = -1
    for i in range(a):
        if i*i > a:
            break
        if (a - i)^(b + i) == X:
            ans = i
            break
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys


def solve(n, aaa):
    if n == 2:
        h, m = divmod(sum(aaa), 2)
        if m == 1 or h > aaa[0]:
            return -1
        return aaa[0] - h

    x = 0
    for a in aaa[2:]:
        x ^= a
    a0, a1 = aaa[:2]
    s = a0 + a1

    if s & 1 != x & 1:
        return -1

    p, q = 0, 0

    b = 1 << 40
    while b:
        bx = x & b
        if bx == 0:
            # print('bx', s)
            # print(f'{b:040b}')
            # print(f'{p:040b}')
            # print(f'{q:040b}')
            # print(f'{a0:040b}')
            # print(f'{a1:040b}')
            # print()
            if s >= 2 * b:
                if p + b <= a0:
                    p |= b
                    q |= b
                    s -= 2 * b
                else:
                    return -1
        else:
            if s < b:
                return -1
            if p + b <= a0 and q + b > a1:
                p |= b
            else:
                q |= b
            s -= b

        # print(f'{b:040b}')
        # print(f'{p:040b}')
        # print(f'{q:040b}')
        # print(f'{a0:040b}')
        # print(f'{a1:040b}')
        # print()

        b >>= 1

    if p == 0:
        return -1
    return a0 - p


n, *aaa = map(int, sys.stdin.buffer.read().split())
print(solve(n, aaa))

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 << j) | 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**9,a[0])):
  if (a[0]-i)^(a[1]+i) == c:
    print(i)
    exit()
print(-1)