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

if c < t:
    flg = 1

if (c - t) % 2:
    flg = 1

b1 = (c - t) // 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)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
    n = ni()
    f, s, *a = nm()
    x = 0
    for c in a: x ^= c
    if (f + s - x) % 2 or ((f + s - x) // 2) & x:
        print(-1)
        return
    y = (f + s - x) // 2
    for i in range(40, -1, -1):
        if x & (1 << i) and y | (1 << i) <= f:
            y |= 1 << i
    print(f - y if f >= y > 0 else -1)
    return

solve()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
    n = ni()
    f, s, *a = nm()
    x = 0
    for c in a: x ^= c
    if (f + s - x) % 2 or ((f + s - x) // 2) & x:
        print(-1)
        return
    y = (f + s - x) // 2
    for i in range(40, -1, -1):
        if x & (1 << i) and y | (1 << i) < f:
            y |= 1 << i
    print(f - y if f >= y > 0 else -1)
    return

solve()

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 != 0:
  print(-1)
  exit()

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

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
S=A[0]+A[1]
X=0
for i in range(2,N):
    X=X^A[i]
if (S-X)%2==1 or S<X:
    print(-1)
    exit()
D=(S-X)//2
if X&D!=0:
    print(-1)
    exit()
a=0
#print(X,D)
B=[0 for i in range(42)]
for k in range(41,-1,-1):
    x=(X&(1<<k))>>k
    d=(D&(1<<k))>>k
    if (x,d)==(0,0):
        pass
    elif (x,d)==(0,1):
        a=a^(1<<k)
    elif (x,d)==(1,0):
        B[k]=1
    else:
        pass
for k in range(41,-1,-1):
    if B[k]==0:
        continue
    if a^(1<<k)<A[0]:
        a=a^(1<<k)
if 0<a<=A[0]:
    print(A[0]-a)
else:
    print(-1)

Submission status: Accepted

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]
    s=a0+a1

    # ans=0
    # #print(bin(a0),bin(a1),bin(ref))
    # INF=10**13
    # @lru_cache(None)
    # def dfs(a0,a1,ref):
    #     inf=INF
    #     if (a0 & 1) ^ (a1 & 1) != (ref & 1):
    #         return inf
        
    #     if a0<0:
    #         return inf
    #     if ref == 0:
    #         return inf if a0<a1 else (a0-a1)//2
    #     a01=a0&1
    #     a11=a1&1
    #     ref1=ref&1
    #     ans=inf
    #     if a01^a11==ref1:
    #         ans=min(ans,2*dfs(a0>>1,a1>>1,ref>>1))
    #     ans=min(ans,2*dfs((a0-1)//2,(a1+1)//2,ref>>1)+1)

    #     return ans
    # x=dfs(a0,a1,ref)
    # if x>=a0:
    #     print(-1)
    
    ##桁dp
    dp=[[[-1]*2 for _ in range(2)] for _ in range(43)]
    refi=ref
    si=s
    dp[0][0][0]=0
    shift=1
    a=a0
    for i in range(42):
        ni=i+1
        for j in range(2):
            for k in range(2):
                cur=dp[i][j][k]
                if cur==-1:
                    continue
                for ai in range(0,2):
                    bi=(refi&1)^ai
                    if (bi+j+ai)&1!=si&1:
                        continue
                    if ai>a&1:
                        nk=1
                    elif ai==a&1:
                        nk=k
                    else:
                        nk=0

                    nj=0
                    if bi+j+ai>1:
                        nj=1
                    
                    dp[ni][nj][nk]=max(dp[ni][nj][nk],cur|shift*ai)
                    
        refi=(refi>>1)
        si>>=1
        a>>=1
        shift<<=1
    x=dp[-1][0][0]
    if x==-1 or x==0:
        print(-1)
    else:
        print(a0-x)


                





if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache


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

    b = 1 << 40
    MASK = (b << 1) - 1

    @lru_cache(maxsize=None)
    def dfs(p, b):
        if b == 0:
            return p
        m = (MASK ^ (b - 1)) << 1
        q = p ^ x & m
        if x & b == 0:
            if s >= p + q + 2 * b:
                if p | b <= a0:
                    return dfs(p | b, b >> 1)
                else:
                    return -1
            return dfs(p, b >> 1)
        else:
            if s < p + q + b:
                return -1
            if p | b <= a0:
                ret = dfs(p | b, b >> 1)
                if ret != -1:
                    return ret
            return dfs(p, b >> 1)

    ret = dfs(0, b)

    if ret <= 0:
        return -1
    return a0 - ret


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

Submission status: Accepted

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))
    INF=10**13
    @lru_cache(None)
    def dfs(a0,a1,ref):
        inf=INF
        if (a0 & 1) ^ (a1 & 1) != (ref & 1):
            return inf
        
        if a0<0:
            return inf
        if ref == 0:
            return inf if a0<a1 else (a0-a1)//2
        a01=a0&1
        a11=a1&1
        ref1=ref&1
        ans=inf
        if a01^a11==ref1:
            ans=min(ans,2*dfs(a0>>1,a1>>1,ref>>1))
        ans=min(ans,2*dfs((a0-1)//2,(a1+1)//2,ref>>1)+1)

        return ans
    x=dfs(a0,a1,ref)
    if x>=a0:
        print(-1)
    else:
        print(x)
    # 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: Accepted

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

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

S=A[0]+A[1]
X=0
for i in range(2,N):
  X = X^A[i]
D=(S-X)//2
if ((S-X) % 2) == 1 or (S-X < 0) or (D & X != 0) or (D>A[0]):
  print(-1)
  sys.exit()
#print(S,X,bin(X))
Y = 0
for i in range(2,len(bin(X))):
  if bin(X)[i] != "0":
    tmp = 2 ** (len(bin(X))-i-1) #立っているビット分足す
    if D^(tmp+Y) <= A[0]: #小さければ
#      print('add')
      Y += tmp #update
#    else:
#      print('exceed!')
else:
  if Y:
    ans = A[0]-(D^Y)
    print(ans)
  else:
    print(-1)

Submission status: Accepted

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
    last_b = -1
    while b:
        bx = x & b
        if bx == 0:
            if s >= 2 * b:
                if p | b <= a0:
                    p |= b
                    q |= b
                    s -= 2 * b
                elif last_b > 0:
                    p ^= last_b
                    q ^= last_b
                    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
                last_b = b
            else:
                q |= b
            s -= b

        b >>= 1

    if p == 0:
        return -1
    assert s == 0
    assert p ^ q == x
    assert a0 - p == q - a1
    return a0 - p


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

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
X=0
if N>2:
    X=A[2]
for i in range(3,N):
    X=(X|A[i])-(X&A[i])
S=A[0]+A[1]
if (S-X)%2==1 or (S-X)<0:
    print(-1)
else:
    D=(S-X)//2
    if D&X>0:
        print(-1)
    else:
        a=D
        for i in range(50,-1,-1):
            if ((X>>i)&1) and ((a+(1<<i))<A[0]):
                a+=(1<<i)
        if a>0 and A[0]>=a:
            print(A[0]-a)
        else:
            print(-1)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    x, y = a[0], a[1]
    nim = 0
    for i in range(2, n):
        nim ^= a[i]
    ans = 0

    while((x ^ y) != nim):
        for i in range(50, -1, -1):
            j = (nim >> i) & 1
            xy = ((x >> i) ^ (y >> i)) & 1
            if j != xy:
                m = min(x % (2**i)+1, 2**i-(y % (2**i)))
                if x % (2**i)+1 == 2**i-(y % (2**i)):
                    print(-1)
                    return
                x -= m
                y += m
                ans += m
                if x <= 0:
                    print(-1)
                    return
                break
        else:
            if (x ^ y) != nim:
                print(-1)
                return
    print(ans)


main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

N = I()
A = LI()

a = A[0]
b = A[1]
c = 0
if len(A) >= 3:
    for i in range(2,N):
        c ^= A[i]

INF = 10**12

from functools import lru_cache

@lru_cache(maxsize=None)
def f(s,t,u):
    '''
    (s-x) ^ (t+x) == u たる x の最小値を返す
    '''
    if s == 0:
        if t == u:
            return 0
        else:
            return INF
    else:
        if (s & 1) ^ (t & 1) == u & 1:
            return min(2*f(s//2,t//2,u//2),2*f((s-1)//2,(t+1)//2,u//2)+1)  # 1の位が0か1か
        else:
            return INF

ans = f(a,b,c)
if ans >= a:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

N = I()
A = LI()

a = A[0]
b = A[1]
c = 0
if len(A) >= 3:
    for i in range(2,N):
        c ^= A[i]

from functools import lru_cache

@lru_cache(maxsize=None)
def f(s,t,u):
    '''
    (s-x) ^ (t+x) == u たる x の最小値を返す
    '''
    if s == 0:
        if t == u:
            return 0
        else:
            return float('inf')
    else:
        if (s & 1) ^ (t & 1) == u & 1:
            return min(2*f(s//2,t//2,u//2),2*f((s-1)//2,(t+1)//2,u//2)+1)  # 1の位が0か1か
        else:
            return float('inf')

ans = f(a,b,c)
if ans >= a:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N = I()
A = IL()

B = 0
if N >= 3:
  for a in A[2:]:
    B ^= a

S = A[0]+A[1]

if (S-B)%2:
  print(-1)
  exit()  
D = (S-B)//2
if D&B or D>A[0]:
  print(-1)
  exit()
ans = D
for i in range(50)[::-1]:
  if ans+(B&(1<<i)) < A[0]:
    ans += B&(1<<i)
ans = A[0]-ans if ans else -1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


# def sub(kouho, target):
#     l = len(kouho)
#     best = None
#     for b in range(1<<l):
#         v = 0
#         for i in range(l.bit_length()):
#             if b>>i&1:
#                 v += 1<<i
#         if 
                

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

val = 0
for num in a[2:]:
    val ^= num
k = a[0] + a[1]
if (k-val)%2!=0 or k<val:
    ans = -1
else:
    tmp = (k-val)//2
    if tmp<0 or 2*tmp>k:
        ans = -1
    else:
        v1 = tmp
        v2 = tmp
        kouho = []
        ans = None
#         if tmp>a[0]:
#             ans = -1
        diff = k - 2*tmp
        for i in range(diff.bit_length()):
            if (diff&1<<i) & tmp:
                ans = -1
                break
            elif diff&1<<i:
                kouho.append(1<<i)
        s = sum(kouho)
        if ans is None:
            for num in kouho[::-1]:
                s -= num
                if v2+s<a[1]:
                    v2 += num
                elif v1+num<=a[0]:
                    v1 += num
                else:
                    v2 += num
            if v1==0 or v1>a[0]:
                ans = -1
            else:
                ans = a[0]-v1
        else:
            ans = -1
        
print(ans)

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]

c = 0
l = []
for i in range(40):
    if 2**i&X==2**i:
        c += 2**i
    else:
        l.append(2**i)

S -= c
a = 0
b = 0
for n in l:
    if 2*n&S==2*n:
        a += n
        b += n
if a+b==S:
    for i in range(40,-1,-1):
        if 2**i&c==2**i and a+2**i<A[0]:
            a += 2**i   
    if a != 0:      
        ans = max(A[0]-a,-1)
    else:
        ans = -1
else:
    ans = -1
print(ans)

Submission status: Accepted

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

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

n = A[0] + A[1] - xor
if n < 0 or n%2:
    print(-1)
    quit()

n //= 2
a = b = 0
digit = 1
d = []
while n or xor:
    n0 = n & 1; xor0 = xor & 1
    if n0:
        if xor0:
            print(-1)
            quit()
        else:
            a += digit
            b += digit
    else:
        if xor0:
            b += digit
            d.append(digit)

    digit *= 2
    n >>= 1; xor >>= 1

if a > A[0]:
    print(-1)
    quit()

while d:
    dd = d.pop()
    if a + dd <= A[0]:
        a += dd; b -= dd

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

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


# def sub(kouho, target):
#     l = len(kouho)
#     best = None
#     for b in range(1<<l):
#         v = 0
#         for i in range(l.bit_length()):
#             if b>>i&1:
#                 v += 1<<i
#         if 
                

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

val = 0
for num in a[2:]:
    val ^= num
k = a[0] + a[1]
if (k-val)%2!=0 or k<val:
    ans = -1
else:
    tmp = (k-val)//2
    if tmp<0 or 2*tmp>k:
        ans = -1
    else:
        v1 = tmp
        v2 = tmp
        kouho = []
        ans = None
        if tmp>a[0]:
            ans = -1
        diff = k - 2*tmp
        for i in range(diff.bit_length()):
            if (diff&1<<i) & tmp:
                ans = -1
                break
            elif diff&1<<i:
                kouho.append(1<<i)
        s = sum(kouho)
        if ans is None:
            for num in kouho[::-1]:
                s -= num
                if v2+s<a[1]:
                    v2 += num
                elif v1+num<=a[0]:
                    v1 += num
                else:
                    v2 += num
            if v1==0:
                ans = -1
            else:
                ans = a[0]-v1
        else:
            ans = -1
        
print(ans)

Submission status: Accepted

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

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

n = A[0] + A[1] - xor
if n < 0 or n%2:
    print(-1)
    quit()

n //= 2
a = b = 0
digit = [1]
d = []
count = 0    
while n or xor:
    n0 = n & 1; xor0 = xor & 1
    if n0:
        if xor0:
            print(-1)
            quit()
        else:
            a += digit[-1]
            b += digit[-1]
    else:
        if xor0:
            b += digit[-1]
            d.append(count)

    digit.append(digit[-1] * 2)
    count += 1
    n >>= 1; xor >>= 1

if a > A[0]:
    print(-1)
    quit()

while d:
    c = d.pop()
    if a + digit[c] <= A[0]:
        a += digit[c]; b -= digit[c]

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

Submission status: Accepted

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

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

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

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

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

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]
if s < x or (s-x) % 2 == 1:
    print(-1)
    exit()
d = (s-x)//2
if d & x != 0 or d > a[0]:
    print(-1)
    exit()
i = 50
ans = d
while i >= 0:
    if x >> i & 1:
        if (1 << i) + ans <= a[0]:
            ans += 1 << i
    i -= 1
if ans == 0:
    print(-1)
    exit()
print(a[0]-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 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 = 0
b = 2**64
while b>0:
  if (D&b)!=0:
    a |= b
  elif (X&b)!=0:
    if (a|b|D&(b-1))<=A[0]:
      a |= b
  b >>= 1
if a==0:
  print(-1)
  exit(0)
print(A[0]-a)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
S = sum(a[:2])
X = 0
for i in range(2, n):
    X ^= a[i]
if S - X < 0 or (S - X) % 2 != 0:
    print(-1)
    exit(0)
D = (S - X) // 2
if D > a[0] or D & X:
    print(-1)
    exit(0)
res = D
for i in range(60, -1, -1):
    if X & (1 << i):
        Q = res | (1 << i)
        if Q <= a[0]:
            res = Q
print(-1 if res == 0 else a[0] - res)