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: Accepted

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

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

S = A[0] + A[1]
A1 = A[0]

D, M = divmod(S - X, 2)
ans = -1
if M % 2 == 0 and D & X == 0 and D <= A1:
    Y = 0
    for p in range(P, -1, -1):
        if (X >> p) & 1 == 1:
            new_Y = Y ^ (1 << p)
            if D ^ new_Y <= A1:
                Y = new_Y

    ans = A1 - (D ^ Y)
    if ans == A1:
        ans = -1

print(ans)

Submission status: Accepted

Solution code:
import random
N = int(input())
A = list(map(int, input().split()))
 
S = A[0]+A[1]
X = 0
for a in A[2:]:
  X ^= a
 
D = (S-X)>>1
if S!=X+(D<<1) or D>A[0] or (X&D)!=0:
  print(-1)
  exit(0)
a = D
b = 2**64
while b>0:
  if (X&b)!=0 and (a|b)<=A[0]:
    a |= b
  b >>= 1
if a==0:
  print(-1)
  exit(0)
print(A[0]-a)

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

Solution code:
INF=10**18
def calc(a,b,xor):
  if (a,b,xor) in memo:
    return memo[(a,b,xor)]
  if (a&1)^(b&1)!=(xor&1):
    return INF
  if xor==0:
    if a<b:
      return INF
    else:
      return (a-b)//2
  x=2*calc(a//2,b//2,xor//2)
  y=2*calc((a-1)//2,(b+1)//2,xor//2)+1
  memo[(a,b,xor)]=min(x,y)
  return memo[(a,b,xor)]

n=int(input())
arr=list(map(int,input().split()))
a,b=arr[0],arr[1]
xor=0
for i in range(2,n):
  xor^=arr[i]
memo={}
ans=calc(a,b,xor)
if ans>=a:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
import sys

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

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

S = a[0] + a[1]
D = (S-T)//2
if S<T or (S-T)%2 or D&T:
    print(-1)
    sys.exit()

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def dp(a,b,s):
        if mem[(a,b,s)] is not None:
            return mem[(a,b,s)]
        x = a&1
        y = b&1
        z = s&1
        if x^y != z:
            return float("inf")
        res = 2*dp(a>>1,b>>1,s>>1)
        if a > 1:
            nr = 2*dp((a-1)>>1,(b+1)>>1,s>>1)+1
            if nr < res:
                res = nr
        mem[(a,b,s)] = res
        return res
    n = I()
    a = LI()
    s = 0
    for i in a[2:]:
        s ^= i
    b = a[1]
    a = a[0]
    mem = defaultdict(lambda : None)
    mem[(0,0,0)] = 0
    ans = dp(a,b,s)
    if ans == float("inf"):
        ans = -1
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

if 0<Y<=X[0]:
    print(X[0]-Y)
else:
    print(-1)

Submission status: Accepted

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

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

M = T.bit_length()+1
if D > X[0]:
    print(-1)
    sys.exit()

Y = D
for i in range(M, -1, -1):
    if T & (1<<i) and (1<<i)|Y <= X[0]:
        Y |= 1<<i

if Y == 0:
    print(-1)
else:
    print(X[0]-Y)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
a = A[0]
b = A[1]
x = 0
for i in A[2:]:
    x ^= i
 
d = {}
def F(a,b,xor):
    if (a,b,xor) in d:
        return d[(a,b,xor)]
    if a&1 ^ b&1 != xor&1:
        return float("INF")
    if xor == 0:
        if a<b:
            return float("INF")
        else:
            return (a-b)//2
    c1 = 2*F(a//2,b//2,xor//2)
    c2 = 2*F((a-1)//2,(b+1)//2,xor//2) + 1
    f = min(c1,c2)
    d[(a,b,xor)] = f
    return f
 
ans = F(a,b,x)
if ans >= a:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n=II()
    aa=LI()
    x=0
    for a in aa[2:]:x^=a
    t=aa[0]+aa[1]-x
    if t<0 or t&1:
        print(-1)
        exit()
    t>>=1
    #print(t)
    a0=a1=0
    for i in range(40,-1,-1):
        dt=t>>i&1
        dx=x>>i&1
        if (dt,dx)==(1,1):
            print(-1)
            exit()
        if (dt,dx)==(1,0):
            a0|=1<<i
            a1|=1<<i

    for i in range(40,-1,-1):
        dt=t>>i&1
        dx=x>>i&1
        if (dt,dx)==(0,1):
            if (a0|1<<i)<=aa[0]:a0|=1<<i
            else:a1|=1<<i

    #print(a0,a1)
    if a0>0 and a0<=aa[0]:print(aa[0]-a0)
    else:print(-1)

main()

Submission status: Accepted

Solution code:
import pprint
N=int(input())
A=list(map(int,input().split()))
bitlen=42
flag=1
exor=0
andsum=0
ex=[0]*bitlen
an=[0]*bitlen
num=0
for i in range(2,N):
    exor=exor^A[i]
andsum=(A[0]+A[1])-exor

if (andsum%2!=0)or(andsum<0):
    flag=0
else:
    andsum=andsum//2
    for i in range(bitlen):
        if (exor>>i)&1:
            ex[i]=1
        if (andsum>>i)&1:
            an[i]=1
    num=andsum
    for i in range(bitlen):
        if (an[i]==1)and(ex[i]==1):
            flag=0
            break
    if num>A[0]:
        flag=0
    for i in range(bitlen-1,-1,-1):
        if ex[i]==1:
            if num+pow(2,i)<=A[0]:
                num=num+pow(2,i)
    #print(num)
    if num==0:
        flag=0
if flag==0:
    print(-1)
else:
    print(A[0]-num)

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, A):
    xor = 0
    for i in range(2, N):
        xor ^= A[i]
    p = A[0] + A[1]
    if (p - xor) & 1:
        return -1
    a = (p - xor) >> 1

    # dp[i][j]=A[0]と同じ桁数の整数で下からi桁目までで条件を満たす値の最大値
    # j=0:i桁目より下の数値がA[0]以下 j=1:A[0]より大きい
    bl = max(A[0], xor).bit_length()
    dp = [[-1] * 2 for _ in range(bl + 1)]
    # 初期状態
    dp[0][0] = 0

    az = A[0]
    for i in range(bl):
        ni = i + 1
        azb = az & 1
        xorb = xor & 1
        ab = a & 1
        for j in range(2):
            if dp[i][j] < 0: continue
            for nazb in range(2):
                if nazb > azb:
                    nj = 1
                elif nazb < azb:
                    nj = 0
                else:
                    nj = j
                for nbzb in range(2):
                    if nazb ^ nbzb == xorb and nazb & nbzb == ab:
                        break
                else:
                    continue
                dp[ni][nj] = max(dp[ni][nj], dp[i][j] | (nazb << i))
        az >>= 1
        xor >>= 1
        a >>= 1

    ans = dp[bl][0]
    if ans <= 0:
        return - 1
    return A[0] - ans

if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(input())
    *A, = map(int, input().split())
    print(main(N, A))

Submission status: Accepted

Solution code:
def digit(x):
    ret = 0
    while x > 0:
        x //= 2
        ret += 1
    return ret

def main():
    N = int(input())
    A = list(map(int, input().split()))
    g = 0
    for i in range(2, N):
        g ^= A[i]
    a0 = A[0]
    a1 = A[1]
    ans = 0
    half = 2**20
    if a0 < half:
        for i in range(a0):
            t0 = a0 - i
            t1 = a1 + i
            if t0 ^ t1 == g:
                print(i)
                return
        print(-1)
        return

    # check upper part (2**20 <= x)
    ug = g >> 20
    b0 = a0 >> 20
    b1 = a1 >> 20
    upper_ans_0 = -1 # a0: no borrow, a1: no carry
    for i in range(b0):
        t0 = b0 - i
        t1 = b1 + i
        if t0 ^ t1 == ug:
            upper_ans_0 = i
            break

    upper_ans_1 = -1 # a0: no borrow, a1: carry
    for i in range(b0):
        t0 = b0 - i
        t1 = b1 + 1 + i
        if t0 ^ t1 == ug:
            upper_ans_1 = i
            break

    upper_ans_2 = -1 # a0: borrow, a1: no carry
    for i in range(b0-1):
        t0 = b0 - 1 - i
        t1 = b1 + i
        if t0 ^ t1 == ug:
            upper_ans_2 = i
            break

    upper_ans_3 = -1 # a0: borrow, a1: carry
    for i in range(b0-1):
        t0 = b0 - 1 - i
        t1 = b1 + 1 + i
        if t0 ^ t1 == ug:
            upper_ans_3 = i
            break

    # print(upper_ans_0, upper_ans_1, upper_ans_2, upper_ans_3)
    # check lower part (0 ... 2**20)
    lower_answers = []
    for i in range(half):
        t0 = (a0 - i) % half
        t1 = (a1 + i) % half
        if t0 ^ t1 == (g % half):
            lower_answers.append(i)
    if len(lower_answers) == 0:
        print(-1)
        return
    # print(len(lower_answers))
    # print(lower_answers)
    answers = []
    for l in lower_answers:
        if (a0 % half) >= l:
            # a0: no borrow
            if (a1 % half) + l < half:
                # no carry
                if upper_ans_0 != -1:
                    answers.append((upper_ans_0 << 20) + l)
            else:
                # carry
                if upper_ans_1 != -1:
                    answers.append((upper_ans_1 << 20) + l)
        else:
            # a0: borrow
            if (a1 % half) + l < half:
                # no carry
                if upper_ans_2 != -1:
                    answers.append((upper_ans_2 << 20) + l)
            else:
                # carry
                if upper_ans_3 != -1:
                    answers.append((upper_ans_3 << 20) + l)
    if len(answers) == 0:
        print(-1)
        return
    answers.sort()
    print(answers[0])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n=int(input())
    A=list(map(int,input().split()))
    x=A[0]^A[1]
    for i in A:
        x^=i
    s=A[0]+A[1]
    dp=[[[-1]*2 for _ in range(2)] for _ in range(43)]
    dp[0][0][0]=0
    v=1
    a=A[0]
    for i in range(42):
        cx,ca,cs=x&1,a&1,s&1
        for j in range(2):
            for k in range(2):
                if dp[i][j][k]==-1:
                    continue
                for na in range(2):
                    for nb in range(2):
                        if na^nb!=cx:
                            continue
                        ni,nj,nk,ns=i+1,0,k,na+nb+j
                        if ns%2!=cs:
                            continue
                        if ns>=2:
                            nj=1
                        if ca<na:
                            nk=1
                        elif ca==na:
                            nk=k
                        else:
                            nk=0
                        dp[ni][nj][nk]=max(dp[ni][nj][nk],dp[i][j][k]|(v*na))
        x>>=1
        s>>=1
        a>>=1
        v<<=1
    a=dp[42][0][0]
    if a==0 or a==-1:
        ans=-1
    else:
        ans=A[0]-a
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
a = A[0]
b = A[1]
x = 0
for i in A[2:]:
    x ^= i

d = {}
def F(a,b,xor):
    if (a,b,xor) in d:
        return d[(a,b,xor)]
    if a&1 ^ b&1 != xor&1:
        return float("INF")
    if xor == 0:
        if a<b:
            return float("INF")
        else:
            return (a-b)//2
    c1 = 2*F(a//2,b//2,xor//2)
    c2 = 2*F((a-1)//2,(b+1)//2,xor//2) + 1
    f = min(c1,c2)
    d[(a,b,xor)] = f
    return f

ans = F(a,b,x)
if ans >= a:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

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

a,b = A[:2]

def answer(ta,tb,tr):
    for i in range(ta):
        if (ta-i)^(tb+i) == tr:
            ans = i
            break
    else:
        ans = -1
    return ans

def solve(a,b,r):
    orga = a

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

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

print(solve(a,b,r))

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, A):
    xor = 0
    for i in range(2, N):
        xor ^= A[i]
    p = A[0] + A[1]
    if (p - xor) & 1:
        return -1
    a = (p - xor) >> 1

    # dp[i][j]=A[0]と同じ桁数の整数で下からi桁目までで条件を満たす値の最大値
    # j=0: i桁目まで見てN未満が確定, j=1: 未確定
    bl = max(A[0], xor).bit_length()
    dp = [[-1] * 2 for _ in range(bl + 1)]
    # 初期状態
    dp[0][0] = 0

    az = A[0]
    for i in range(bl):
        ni = i + 1
        azb = az & 1
        xorb = xor & 1
        ab = a & 1
        for j in range(2):
            if dp[i][j] < 0: continue
            for nazb in range(2):
                if nazb > azb:
                    nj = 1
                elif nazb < azb:
                    nj = 0
                else:
                    nj = j
                for nbzb in range(2):
                    if nazb ^ nbzb == xorb and nazb & nbzb == ab:
                        break
                else:
                    continue
                dp[ni][nj] = max(dp[ni][nj], dp[i][j] | (nazb << i))
        az >>= 1
        xor >>= 1
        a >>= 1

    ans = dp[bl][0]
    if ans <= 0:
        return - 1
    return A[0] - ans

if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(input())
    *A, = map(int, input().split())
    print(main(N, A))

Submission status: Accepted

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

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

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

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

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
xsm = 0
sm = a[0] + a[1]

for i in range(2, N): xsm ^= a[i]
t = sm - xsm
table = [0] * 41
for i in range(40, -1, -1):
  if t >= 1 << (i + 1):
    t -= 1 << (i + 1)
    table[i] = 1
if t:
  print(-1)
  exit(0)


t = a[0]
res = 0
for i in range(40, -1, -1):
  if t >= 1 << i:
    if table[i]:
      t -= 1 << i
      res += 1 << i
for i in range(40, -1, -1):
  if t >= 1 << i:
    if xsm & (1 << i):
      t -= 1 << i
      res += 1 << i
if res == 0 or (res ^ (sm - res) != xsm): print(-1)
else: print(a[0] - res)

Submission status: Accepted

Solution code:
def f_unfair_nim():
    from functools import reduce
    from operator import xor
    N = int(input())
    A = [int(i) for i in input().split()]

    s = sum(A[:2])
    x = reduce(xor, A[2:], 0)
    if (s - x) % 2 != 0 or (((s - x) // 2) & x) != 0:
        return -1

    a = (s - x) // 2
    for i in range(60, -1, -1):
        if (x & (1 << i)) != 0 and (a ^ (1 << i) <= A[0]):
            a ^= 1 << i
    return A[0] - a if A[0] >= a > 0 else -1

print(f_unfair_nim())

Submission status: Accepted

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



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


n = I()
a = LI()

y = 0
flg = 0

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

x = a[0] + a[1] - y
if x < 0 or x % 2:
    flg = 1

x //= 2
a1 = x

if a1 > a[0]:
    flg = 1

for i in reversed(range((a[0] + a[1]).bit_length())):
    if y & (1 << i):
        if x & (1 << i):
            flg = 1
        if a1 + 2 ** i <= a[0]:
            a1 += 2 ** i

if a1 == 0:
    flg = 1

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

Submission status: Accepted

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



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


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

t = 0
flg = 0

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

x = a[0] + a[1] - t
if x < 0 or x % 2:
    flg = 1

x //= 2
a1 = x

if a1 > a[0]:
    flg = 1

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

if a1 == 0:
    flg = 1

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

Submission status: Accepted

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



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


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

t = 0
flg = 0

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

b1 = a[0] + a[1] - t
if b1 < 0 or b1 % 2:
    flg = 1

b1 //= 2
a1 = b1

if a1 > a[0]:
    flg = 1

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

if a1 == 0:
    flg = 1

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

Submission status: Accepted

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



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


n = int(input())
a = list(map(int, input().split()))
c = a[0] + a[1]

t = 0
flg = 0

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

b1 = c - t
if b1 < 0 or b1 % 2:
    flg = 1

b1 //= 2
a1 = b1

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

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

if a1 == 0:
    flg = 1

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