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: Time Limit Exceeded

Solution code:
import functools
from typing import List
from numba import njit


@njit
def solve(n: int, A: List[int]):
    a = A[0]
    b = A[1]
    c = 0
    for x in A[2:]:
        c ^= x
    for ans in range(A[0]):
        if (a - ans) ^ (b + ans) ^ c == 0:
            return ans

    return -1


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

print(solve(n, A))

Submission status: Time Limit Exceeded

Solution code:
import functools

n = int(input())
A = [int(x) for x in input().split()]
a, b, *C = A
c = functools.reduce(lambda x, y: x ^ y, C, 0)
for ans in range(A[0]):
    if (a - ans) ^ (b + ans) ^ c == 0:
        print(ans)
        break
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
a1=[]
for i in range(n):
    a1.append(int(format(a[i], 'b')))
k=sum(a1[2:])

for i in range(a[0]):
    s=int(format(a[0]-i, 'b'))+int(format(a[1]+i, 'b'))
    s1=s+k
    s1=str(s1)
    s11=s1.count('1') 
    s13=s1.count('3')
    s15=s1.count('5')
    s17=s1.count('7')
    s19=s1.count('9')
    if s11==0 and s13==0 and s15==0 and s17==0 and s19==0:
        print(i)
        exit()

print(-1)

Submission status: Time Limit Exceeded

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**9, a[0])):
    if (a[0]-i)^(a[1]+i)==s:
        ans = i
        break

print(ans)

Submission status: Time Limit Exceeded

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

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

ans = -1
for i in range(A[0]):
    if (A[0] - i) ^ (A[1] + i) == A3:
        ans = i
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
ans=0
for i in range(2,N):
    ans=ans^A[i]
S=A[0]+A[1]
flag=True
for i in range(A[0]):
    if (A[0]-i)^(A[1]+i)==ans:
        print(i)
        flag=False
        break
if flag:
    print(-1)

Submission status: Time Limit Exceeded

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
    while True:
        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: Time Limit Exceeded

Solution code:
c=0
for i in range(1000000000000):
  c+=1
print(c)

Submission status: Time Limit Exceeded

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

x = 0

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

for i in range(A[0]):
  temp = x
  ans = temp^(A[0]-i)^(A[1]+i)
  if ans == 0:
    print(i)
    exit()

print(-1)

Submission status: Time Limit Exceeded

Solution code:
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

ans = 10 ** 18
# print(t)

for num in range(2 ** bit_len):
    a1 = 0
    a2 = 0
    for i in range(bit_len):
        # flag = 1
        if num & (1 << i):
            # ti = 1
            if t & (1 << i):
                a1 += 2 ** i
        else:
            if t & (1 << i):
                a2 += 2 ** i
            else:
                a1 += 2 ** i
                a2 += 2 ** i
    if a1 and a[1] <= a2 and a1 + a2 == c:
        ans = min(ans, abs(a1-a[0]))

if ans == 10 ** 18:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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
  T = True
  i = 0
  while T:
    now2 = (A[0] - i) ^ (A[1] + i)
    #print(now2, A[0] - i, A[1] + i, b)
    if not (now2 ^ b):
      print(i)
      quit()
    
    i += 1
    if (A[0] - i) < 0:
      T = False
      print("-1")

Submission status: Time Limit Exceeded

Solution code:
import sys
n=int(input())
A=[int(i) for i in input().split()]
def f(A):
    s=0
    for a in A:
        s^=a
    return s
if n>=3:
    K=f(A[2:])
else:
    K=0
    
for i in range(A[0]):
    res = (A[0] - i) ^ (A[1] + i) ^ K
    #print(res)
    if res == 0:
        print(i)
        sys.exit()
else:
    print(-1)

Submission status: Time Limit Exceeded

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]

for i in range(A[0]):
    if ALL ^ (A[0] - i) ^ (A[1] + i) == 0:
        print(i)
        sys.exit()

print(-1)

Submission status: Time Limit Exceeded

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

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

a0 = A[0]
a1 = A[1]
for i in range(A[0]):
    if tmp ^ (a0 - i) ^ (a1 + i) == 0:
        print (i)
        exit()

print (-1)

Submission status: Time Limit Exceeded

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

sm = 0
for x in a:
    sm ^= x

if sm == 0:
    print(0)
    exit()

for i in range(a[0]-1):
    a[0] -= 1
    a[1] += 1
    sm = 0
    for x in a:
        sm ^= x
    if sm == 0:
        print(i+1)
        exit()

print(-1)

Submission status: Accepted

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

N = int(readline())
A = list(map(int, readline().split()))
S = A[0] + A[1]
X = 0
for i in range(2, N):
    X ^= A[i]

K = S-X
if K&1:
    print(-1)
else:
    K >>= 1
    if K&X or K > A[0]:
        print(-1)
    else:
        Y = 0
        for i in range(60, -1, -1):
            if X & (1<<i) and (Y+(1<<i))^K <= A[0]:
                Y += 1<<i
        Y = Y^K
        if not Y:
            print(-1)
        else:
            print(A[0]-Y)

Submission status: Accepted

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


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

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

"""
全部の山のxorを0にしたい
変化する山は2つだけ，1とどこか．
1番目の山からi番目の山に移動するものとする．
この2つの山を使って，うまく目標T（2~Nのうちi番目だけのぞいた全てのxor）を作れるか

2つの山をごちゃ混ぜにして，aとbの二つに分けるものとする
和  :S=A[0] + A[i]
xor :T

Tのbitが立っている場合，aとbの同じ位置では片方しかbitが立っていない
それ以外の場所ではaとbのbitが同じ．

j桁目のbitをxjとする，
bitの立ち方が違うとろの和は当然Tなので
bitの立ち方が同じ桁の総和を考えると
これが S-T　になるので2で割ればどのbitが立つべきかわかる 

例)
5,3,4でi=2なら
5,3をごちゃ混ぜにして，S=8でT=4を作りたい


a= x3  1  x1  x0
b= x3  0  x1  x0

2*(x3+x1+x0) = 8-4
x3 + x1 + x0 =2 
なのでx1だけ立てれば良い

---

1番目の山からしか動かせないので，このa,bが必ずしも作れるとは限らない，
a,bのうち小さい方がA[0]以下なら良い．
片方をできるだけ小さくしたいので，Tで立っているbitはどちらかに固める

"""
def main():
    mod=10**9+7
    inf = 10**13
    
    N=I()
    A=LI()
    allx=0
    for i in range(N):
        allx=allx^A[i]
        
    #　最初から後手必勝
    if allx==0:
        print(0)
        exit()
        
    #　動かせない
    if A[0]==1:
        print(-1)
        exit()
        
    ####
        
    M=45 #桁数のmaxちょい
        
    def calc(S,T):
        # SとTが与えられた状態で取れる最大のa
        # 達成可能ならそれで良いわけではない，aを最小としての計算が楽だが，実際には最小手数を求めたいので
        # aを可能な限り大きくしていきたい．(S-T)//2 部分は固定で，Tの部分だけ可変
        # 上位桁から見て，bだけbitが立っていて，aが立っていない場合，aに移していく
        
        #むり
        if T>S:
            return False
        if (S-T)%2==1:
            return False
        
        # 以下，T<S　かつ　差が偶数とする
        
        # 基本的には
        # 最小は　(S-T)//2
        # 最大が　(S-T)//2 + T
        # になるはず
        
        if T==S:
            # T=Sの場合，Tの立っているbitのうち，Tの立っているbitを割り振りたいが全てが偏るとダメ （a=0が取れないので）
            cnt=0 #　立っているbitの数，これが1だと分けられない
            m=inf #　一番小さいbitに対応する数
            T2=T
            a=0
            b=0
            for j in range(M,-1,-1):#上位桁から見て
                p=1<<j
                if p<=T2:
                    T2-=p
                    m=p
                    cnt+=1
                    if a+p<=A[0]:
                        a+=p# 可能なら足していく
                    else:
                        b+=p
                    
            if cnt==1:
                return False
            if a==0: # 何も足せなかった
                return False
            if b==0: # 全てaにたしてしまった
                a-=m # 最下位をbに譲る
            return a
        
        # aが最小のパターンでさえ，移動でaを作れん
        if (S-T)//2 > A[0]:
            return False
        
        # Tと関与しない部分の合計値=S2を先に作り，それとT部分でbitがかぶらなければOK
        T2=T
        S2=(S-T)//2
        a=S2 # S2部分は確定している
        b=S2 # S2部分は確定している
        for i in range(M,-1,-1): # 上から見ていき，
            p=1<<i
            ft=0#T2がわ
            fs=0#S2側
            if p<=T2:
                T2-=p
                ft=1
            if p<=S2:
                S2-=p
                fs=1
                
            if ft and fs:#立っているbitが被った
                return False
            
            if ft:
                if a+p<=A[0]: # 可能ならaに足す
                    a+=p
                else:
                    b+=p
                
            
        return a
    

                 
            
            
        
            

    ans=inf
    for i in range(1,N):
        S=A[0]+A[i]
        T=A[0]^A[i]^allx
        
        a=calc(S,T)
        
        if a!=0:
            # print(i,a,A[0]-a)
            ans=min(ans,A[0]-a)
            
    if ans==inf:
        ans=-1
    print(ans)
        
    
            
            
            
        
        
        
        
    
    

main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    xor = 0
    for i in range(2, n):
        xor ^= a[i]
    s = a[0] + a[1]
    dp = [[[-1 for k in range(2)] for j in range(2)] for i in range(45)]
    p = a[0]
    dp[0][0][0] = 0
    for i in range(44):
        crrx = xor&1
        crrs = s&1
        crrp = p&1
        for j in range(2):
            for k in range(2):
                if dp[i][j][k] == -1:
                    continue
                for nxtp in range(2):
                    for nxtq in range(2):
                        nxti = i+1
                        nxtj = 0
                        nxtk = k
                        if (nxtp ^ nxtq) != crrx:
                            continue
                        nxts = nxtp+nxtq+j
                        if nxts%2 != crrs:
                            continue
                        if nxts >= 2:
                            nxtj = 1
                        if crrp < nxtp:
                            nxtk = 1
                        elif crrp == nxtp:
                            nxtk = k
                        else:
                            nxtk = 0
                        dp[nxti][nxtj][nxtk] = max(dp[nxti][nxtj][nxtk], dp[i][j][k]+(1<<i)*nxtp)
        xor //= 2
        s //= 2
        p //= 2
    if dp[-1][0][0] > 0:
        print(a[0] - dp[-1][0][0])
    else:
        print(-1)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

# a = A_1, b = A_2, x = A_3 ^ ... ^ A_N, s = a + b とする
a, b = A[0], A[1]
x = 0
for i in range(2, N):
    x ^= A[i]
s = a + b

M = 42
# dp[桁][繰り上げフラグ][これまでの桁でAより大きいフラグ] := Aとなり得る値の最大値
dp = [[[-1] * 2 for _ in range(2)] for _ in range(M + 1)]
dp[0][0][0] = 0
v = 1
for i in range(M):
    cs = s & 1
    cx = x & 1
    ca = a & 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):
                    # 条件1: na ^ nb = x
                    if na ^ nb != cx:
                        continue
                    # 条件2: na + nb = S
                    ns = na + nb + j
                    if ns & 1 != cs:
                        continue
                    
                    # 遷移先のi, j, kを求める
                    ni = i + 1
                    nj = 1 if ns >= 2 else 0
                    if na > ca:
                        nk = 1
                    elif na < ca:
                        nk = 0
                    else:
                        nk = k
                    
                    # 遷移先を最大化
                    dp[ni][nj][nk] = max(dp[ni][nj][nk], dp[i][j][k] + na * v)
    s >>= 1
    x >>= 1
    a >>= 1
    v <<= 1

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

Submission status: Accepted

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

a, b = A[0], A[1]
X = 0
for i in range(2, N):
    X ^= A[i]
S = a + b

M = 42
dp = [[[-1] * 2 for _ in range(2)] for _ in range(M + 1)]
dp[0][0][0] = 0
v = 1
for i in range(M):
    cs = S & 1
    cx = X & 1
    ca = a & 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):
                    # 条件②: A' ^ B' = X
                    if na ^ nb != cx:
                        continue
                    # 条件①: A' + B' = S
                    ns = na + nb + j
                    if ns & 1 != cs:
                        continue
                    
                    ni = i + 1
                    nj = 1 if ns >= 2 else 0
                    if na > ca:
                        nk = 1
                    elif na < ca:
                        nk = 0
                    else:
                        nk = k
                    
                    dp[ni][nj][nk] = max(dp[ni][nj][nk], dp[i][j][k] + na * v)
    S >>= 1
    X >>= 1
    a >>= 1
    v <<= 1

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

Submission status: Accepted

Solution code:
import sys
INF = float("inf")
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from functools import reduce
from operator import xor
from itertools import product
def resolve():
    n = int(input())
    A = list(map(int, input().split())) + [0]
    a = A[0]
    s = sum(A[:2])
    u = reduce(xor, A[2:])

    if s < u or (s + u) & 1:
        print("-1")
        return

    v = (s - u) // 2
    # find maximum x s.t. 0 <= x <= a and there exists y s.t. x ^ y = u and x & y = v
    dp = [0, -INF]
    for d in range(60, -1, -1):
        ndp = [-INF, -INF]
        ad = a >> d & 1
        ud = u >> d & 1
        vd = v >> d & 1
        for lt, xd, yd in product(range(2), repeat = 3):
            if (not lt) and ad < xd:
                continue
            if xd ^ yd != ud:
                continue
            if xd & yd != vd:
                continue
            nlt = max(lt, ad > xd)
            ndp[nlt] = max(ndp[nlt], dp[lt] + (xd << d))
        dp = ndp

    pile = max(dp)
    if pile <= 0:
        print(-1)
    else:
        print(a - pile)
resolve()

Submission status: Accepted

Solution code:
import sys

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

        K = D
        dbit = [0] * 41
        for i in range(41):
            dbit[i] = K % 2
            K //= 2
            
        A0 = D
        for i in range(41):
            if rbit[40 - i] == dbit[40 - i] and rbit[40 - i] == 1:
                print(-1)
                return 0
            else:
                if rbit[40 - i] == 1:
                    if A0 + pow(2, 40 - i) <= A[0]:
                        A0 += pow(2, 40 - i)
        if A0 > 0: print(A[0] - A0)
        else: print(-1)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

a, b = A[:2]
xor = 0
for x in A[2:]:
    xor ^= x

INF = 10**13

@lru_cache(None)
def F(a, b, xor):
    if (a & 1) ^ (b & 1) != (xor & 1):
        return INF
    if xor == 0:
        return INF if a < b else (a - b) // 2
    # 1の位を放置
    x = 2 * F(a // 2, b // 2, xor // 2)
    # 1の位を移動
    y = 2 * F((a - 1) // 2, (b + 1) // 2, xor // 2) + 1
    x = min(x, y)
    if x >= INF:
        x = INF
    return x

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

Submission status: Accepted

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

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

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

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from functools import lru_cache
import sys
input = sys.stdin.readline

@lru_cache(maxsize=None)
def dfs(a, b, c):
    if (a ^ b) & 1 != c & 1:
        return float('inf')
    if a == 0:
        return 0 if b == c else float('inf')
    return min(2 * dfs(a >> 1, b >> 1, c >> 1), 2 * dfs((a - 1) >> 1, (b + 1) >> 1, c >> 1) + 1)

N = int(input())
A = list(map(int, input().split()))
B = 0
for i in range(2, N):
    B ^= A[i]
ans = dfs(A[0], A[1], B)
print(ans if ans < float('inf') and A[0] > ans else -1)

Submission status: Accepted

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

x = 0
for i in A:
    x ^= i

# 0以上A1未満
# a1 ^ a2 -> (a1-n) ^ (a2+n)
# x -> 0

# a + b = 0 -> b=-aは逆元
# a * b = 1 -> b=1/aは逆元
# a ^ a = 0 -> aが逆元
# -> 自由に式変形しやすい

# a1^a2^あまり=x
# b1^b2^あまり=0
# a1^a2^x=b1^b2

# 上のビットからやる
old = A[0] ^ A[1] ^ x

# b0 ^ b1 = old

# b0 + b1 - 2 * (b0 & b1) = old

b0pb1 = A[0] + A[1]
# print(A[0], A[1], b0pb1, old, file=sys.stderr)

if b0pb1 < old or (b0pb1 - old) % 2 == 1:
    print(-1)
    exit(0)

b0andb1 = (b0pb1 - old) // 2
print(A[0], A[1], b0pb1, old, b0andb1, file=sys.stderr)

if (b0andb1 & old) != 0:
    print(-1)
    exit(0)


# A[0]を減らして
# A[0] & ~old = b0andb1
# にするのが最終目標

if A[0] < b0andb1:
    print(-1)
    exit(0)

ans = b0andb1
for i in reversed(range(0,40)):
    if((old >> i) & 1) == 0:
        continue
    if ans + (1 << i) <= A[0]:
        ans += 1 << i

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

print(A[0] - ans)

Submission status: Accepted

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

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



if __name__ == '__main__':
    main()

Submission status: Accepted

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

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



if __name__ == '__main__':
    main()

Submission status: Accepted

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

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



if __name__ == '__main__':
    main()

Submission status: Accepted

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

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



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np

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

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


def main():
    s = 0
    for a in A[2:]:
        s ^= a
    t = A[0] + A[1]
    f = lambda x: list(map(int, format(x, "050b")[::-1]))
    sb = f(s)
    tb = f(t)
    ab = f(A[0])

    dp = np.full((51, 2, 2), -1, dtype=int)
    dp[0][0][0] = 0
    for i in range(50):
        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 != sb[i] or (na + nb + j) % 2 != tb[i]:
                            continue
                        nj = (na + nb + j) // 2
                        if na == ab[i]:
                            nk = k
                        elif na == 1:
                            nk = 1
                        else:
                            nk = 0
                        v = dp[i][j][k] + (2 ** i) * na
                        dp[i + 1][nj][nk] = max(dp[i + 1][nj][nk], v)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
X=0
for i in range(2,N):
  X^=A[i]
S=A[0]+A[1]
T=S-X
Y=0
for i in range(41):
  if (1<<(i+1))&T:
    Y+=(1<<i)
if Y^(S-Y)^X:
  print(-1)
  exit()
for i in range(41,-1,-1):
  if X&(1<<i) and (Y+(1<<i))<=A[0]:
    Y+=(1<<i)
if 0<Y<=A[0]:
  print(A[0]-Y)
else:
  print(-1)

Submission status: Accepted

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

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

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

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

ok = False
u = 0
v = 0

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

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

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

Submission status: Accepted

Solution code:
# AFTER EDITORIAL


def solve(ls):
    import math

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

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

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

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

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

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

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


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


if __name__ == "__main__":
    import sys

    main(sys.stdin, sys.stdout)