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:
# -*- coding: utf-8 -*-
import sys
from functools import lru_cache
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=input()
A=tuple(map(int,input().split()))
X=0
for x in A[2:]:
    X^=x
S=A[0]+A[1]
if (S-X)%2:
    print(-1)
    exit()
D=(S-X)//2
ans=0
tmp=0
ttmp=0
f=False
for i in range(50):
    if (D>>i)&1==(X>>i)&1==1:
        print(-1)
        exit()
    elif (D>>i)&1==1 and (X>>i)&1==0: # (1,1)
        if (A[0]>>i)&1==0:
            ans-=1<<i
            f=True
    elif (D>>i)&1==0 and (X>>i)&1==1: # (1,0), (0,1)
        if (A[0]>>i)&1==1 and f:
            tmp=1<<i
            ans+=ttmp
            ttmp=0
            f=False
        elif (A[0]>>i)&1==0:
            ttmp-=1<<i
    else: # (0,0)
        if (A[0]>>i)&1==1:
            ans+=1<<i
            tmp=0
            ans+=ttmp
            ttmp=0
            f=False
if f:
    print(-1)
else:
    if ans+tmp>=A[0]:
        print(-1)
    else:
        print(ans+tmp)

Submission status: Accepted

Solution code:
N = int(input())
A,B,*C = list(map(int,input().split()))
X = 0
for c in C:
    X ^= c
S = A+B

K = 43
dp = [[[-1]*2 for _ in range(2)] for _ in range(K)]
dp[0][0][0] = 0

for i in range(K-1):
    cx = (X>>i)&1
    cs = (S>>i)&1
    ca = (A>>i)&1
    for j in range(2):
        for k in range(2):
            if dp[i][j][k] == -1: continue
            for na in range(2):
                nb = na^cx
                ns = na+nb+j
                if ns%2 != cs: continue
                nj = ns//2
                if ca < na:
                    nk = 1
                elif ca == na:
                    nk = k
                else:
                    nk = 0
                dp[i+1][nj][nk] = max(dp[i+1][nj][nk], dp[i][j][k] + 2**i * na)
a = dp[-1][0][0]
if a==0 or a==-1:
    print(-1)
else:
    print(A - a)

Submission status: Accepted

Solution code:
N = int(input())
A,B,*C = list(map(int,input().split()))
X = 0
for c in C:
    X ^= c
S = A+B

K = 43
dp = [[[-1]*2 for _ in range(2)] for _ in range(K)]
dp[0][0][0] = 0

for i in range(K-1):
    cx = (X>>i)&1
    cs = (S>>i)&1
    ca = (A>>i)&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
                    ns = na+nb+j
                    if ns%2 != cs: continue
                    nj = ns//2
                    if ca < na:
                        nk = 1
                    elif ca == na:
                        nk = k
                    else:
                        nk = 0
                    dp[i+1][nj][nk] = max(dp[i+1][nj][nk], dp[i][j][k] + 2**i * na)
a = dp[-1][0][0]
if a==0 or a==-1:
    print(-1)
else:
    print(A - a)

Submission status: Accepted

Solution code:
def examA():
    N = I()
    ans = N + N**2 + N**3
    print(ans)
    return

def examB():
    S = SI()
    T = SI()
    ans = 0
    for s,t in zip(S,T):
        if s!=t:
            ans += 1
    print(ans)
    return

def examC():
    N, M, K = LI()
    A = LI()
    B = LI()
    SA = 0
    b = 0
    SB = 0
    for i in range(M):
        if SB+B[i]>K:
            break
        SB += B[i]
        b += 1
    #print(b,SB)
    ans = 0
    ans = max(ans,b)
    for i in range(N):
        SA += A[i]
        if SA+SB>K:
            while(b>=0):
                if SA+SB<=K:
                    break
                SB -= B[b-1]
                b -= 1
        if b==-1:
            break
        #print(i,b,SA,SB)

        ans = max(ans,b+i+1)
    print(ans)
    return

def examD():
    def primes(n):
        is_prime = [True] * (n + 1)
        is_prime[0] = False
        is_prime[1] = False
        for i in range(2, int(n ** 0.5) + 1):
            if not is_prime[i]:
                continue
            for j in range(i * 2, n + 1, i):
                is_prime[j] = False
        return [i for i in range(n + 1) if is_prime[i]]
    N = I()
    P = primes(N)
    #print(P)
    D = [1]*(N+1)
    for p in P:
        for i in range(1,1+N//p):
            cnt = 1
            cur = i
            while(cur%p==0):
                cnt += 1
                cur //= p
            D[p*i] *= (1+cnt)

    ans = 0
    for i in range(1,N+1):
        ans += i*D[i]
    print(ans)
    return

def examE():
    class combination():
        # 素数のmod取るときのみ　速い
        def __init__(self, n, mod):
            self.n = n
            self.mod = mod
            self.fac = [1] * (n + 1)
            self.inv = [1] * (n + 1)
            for j in range(1, n + 1):
                self.fac[j] = self.fac[j - 1] * j % mod

            self.inv[n] = pow(self.fac[n], mod - 2, mod)
            for j in range(n - 1, -1, -1):
                self.inv[j] = self.inv[j + 1] * (j + 1) % mod

        def comb(self, n, r):
            if r > n or n < 0 or r < 0:
                return 0
            return self.fac[n] * self.inv[n - r] * self.inv[r] % self.mod
    N, M = LI()
    # 被りあり
    dp = [0] * (N + 1)
    dp[2] = 1
    for n in range(3, N + 1):
        dp[n] += (dp[n - 1] + dp[n - 2]) * (n - 1)
        dp[n] %= mod
    #print(dp)
    C = combination(M,mod)
    Acur = C.fac[M]
    Acur %= mod
    #print(Acur)
    for i in range(1,N+1):
        cur = C.comb(N,i)*C.fac[M-i]*C.inv[M-N]
        cur %= mod
        if i%2==1:
            Acur = Acur + mod - cur
        else:
            Acur = Acur + mod + cur
        Acur %= mod
        #print(Acur,cur)
    if N%2==1:
        Acur += 1
    ans = dp[N] * ((C.fac[M] * (C.inv[M-N])))
    ans %= mod
    print(ans)
    return

def examE2():
    class combination():
        # 素数のmod取るときのみ　速い
        def __init__(self, n, mod):
            self.n = n
            self.mod = mod
            self.fac = [1] * (n + 1)
            self.inv = [1] * (n + 1)
            for j in range(1, n + 1):
                self.fac[j] = self.fac[j - 1] * j % mod

            self.inv[n] = pow(self.fac[n], mod - 2, mod)
            for j in range(n - 1, -1, -1):
                self.inv[j] = self.inv[j + 1] * (j + 1) % mod

        def comb(self, n, r):
            if r > n or n < 0 or r < 0:
                return 0
            return self.fac[n] * self.inv[n - r] * self.inv[r] % self.mod

    N, M = LI()
    C = combination(M,mod)
    cnt = 0
    for i in range(N+1):
        cur = C.comb(N,i)*C.fac[M-i]*C.inv[M-N] % mod
        if i%2==1:
            cnt -= cur
            cnt += mod
            cnt %= mod
        else:
            cnt += cur
            cnt %= mod
    ans = cnt * (C.fac[M]*C.inv[M-N])
    ans %= mod
    print(ans)
    return

def examF():
    bit = 40
    N = I()
    A = LI()
    aim = 0
    start = A[0]+A[1]
    for a in A[2:]:
        aim ^= a
    #print(aim)

    cnt = 0
    stack = deque()
    candi = []

    for i in range(bit):
        if (1<<i)&aim:
            cnt += (1<<i)
            candi.append(1<<i)
        else:
            stack.append(1<<i)
    a = 0
    b = 0

    while(stack):
        now = stack.pop()
        if cnt+now*2<=start:
            cnt += now*2
            a += now
            b += now
        if cnt==start:
            break
    #print(start,aim)

    if start!=cnt:
        print(-1)
        return

    if a>A[0]:
        print(-1)
        return
    #print(candi,a)
    for c in candi[::-1]:
        if a+c<=A[0]:
            a += c
    ans = A[0]-a
    if ans==A[0]:
        print(-1)
        return

    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examF()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

Solution code:
#写経
#https://atcoder.jp/contests/abc172/submissions/14777611

def resolve():
    N = int(input())
    A = [int(a) for a in input().split()]
    x = 0
    for a in A[2:]:
        x ^= a                              # ^はXOR計算
    s = sum(A[:2])
    if s < x or (s ^ x) & 1:
        print(-1)
        return
    d = (s-x) // 2
    a = A[0]
    n = 0
    for i in range(40)[::-1]:
        b,c = (x >> i) & 1, (d >> i) & 1    # >> i は右方向iビットシフト
        if b == c == 1:
            print(-1)
            return
        if b == 0 and c == 1:
            n += 1 << i
    for i in range(40)[::-1]:
        b,c = (x >> i) & 1, (d >> i) & 1
        if b == 1 and c == 0:
            if n + (1 << i) <= a:
                n += 1 << i
    if n > a or n == 0:
        print(-1)
    else:
        print(a-n)
resolve()

Submission status: Accepted

Solution code:
import sys

N_MAX = 200000 + 5
INF = 10**9 + 7
sys.setrecursionlimit(N_MAX)
MOD = 10**9 + 7

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

K = 43

#
A = Arr[0]
B = Arr[1]

S = A + B
X = 0
for i in range(2, len(Arr)):
    X ^= Arr[i]

# print(S, X)

# 次を満たすa, b が見つかるか？
#  a+b=S, a^b=X, a<=A

# 桁DP : 桁を一つずつ決めていくようなDP
# dp[今の桁数 = 0:42][繰り上がりがあるか = 0,1][今までがA以下かどうか 0=以下、1=より大きい] = 最大値
# 値は最大値。満たすものがなければ -1
dp = [[[-1 for x in [0, 1]] for _ in [0, 1]] for _ in range(K)]

dp[0][0][0] = 0  # 最初

v = 1
for i in range(K - 1):  # 桁数
    cx = X & 1  # current X
    cs = S & 1  # current S
    ca = A & 1  # current A
    for j in range(2):  # 繰り上がりある／ない
        for k in range(2):  # 今までの範囲が A 以下かどうか
            if dp[i][j][k] == -1:  #
                continue

            for na in range(2):
                for nb in range(2):
                    ni = i + 1
                    nj = 0
                    nk = k
                    if na ^ nb != cx:  # a ^ b = A か？
                        continue

                    ns = na + nb + j
                    if ns % 2 != cs:  # a + b = S か？
                        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
    # print(v)

a = dp[K - 1][0][0]
if a == -1 or a == 0:
    print(-1)
else:
    print(Arr[0] - a)

Submission status: Accepted

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

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

S=A[0]+A[1]

DP=[[[1<<60]*2 for i in range(2)] for j in range(60)]
DP[0][0][1]=0

for i in range(59):
    CX=0
    if XOR & (1<<i)!=0:
        CX=1

    CS=0
    if S & (1<<i)!=0:
        CS=1

    CA=0
    if A[1] & (1<<i)!=0:
        CA=1
    
    for j in range(2):
        for k in range(2):
            if DP[i][j][k]==1<<60:
                continue

            for na,nb in [(0,0),(0,1),(1,0),(1,1)]:
                if na^nb != CX:
                    continue
                if (na+nb+j)%2 != CS:
                    continue
                
                if na+nb+j>=2:
                    nj=1
                else:
                    nj=0

                if CA<nb:
                    nk=1
                elif CA==nb:
                    nk=k
                else:
                    nk=0

                DP[i+1][nj][nk]=min(DP[i+1][nj][nk],DP[i][j][k]|((1<<i)*nb))
                #print(i,j,k,nj,nk,DP[i][j][k]|((1<<i)*nb))

ANS=DP[59][0][1]-A[1]

if ANS>=A[0]:
    print(-1)
else:
    print(ANS)

Submission status: Accepted

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

al = 0
for i in range(2,n):
    al ^= a[i]
ans = 0
s = a[0]+a[1]
if s-al<0 or (s-al)%2:
    ans = -1
else:
    d = (s-al)//2
    now = d
    for i in range(65,-1,-1):
        if (1 << i)&al and (1 << i)+now<=a[0]:
            now += 1 << i
    if now==0 or now>a[0] or d&al!=0:
        ans = -1
    else:
        ans = a[0]-now

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]

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

dp = [[[-1] * 2 for _ in range(2)] for _ in range(60)]
dp[0][0][0] = 0

for i in range(59) :
  cs = (S >> i) & 1
  cx = (X >> i) & 1
  ca = (A[0] >> i) & 1
  for j in (0, 1) :
    for k in (0, 1) :
      if dp[i][j][k] < 0 : continue
      for na in (0, 1) :
        for nb in (0, 1) :
          ni = i + 1
          nj = 0
          nk = k
          if na ^ nb != cx : continue
          ns = 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] | (na << i))
          
if 1 <= dp[-1][0][0] <= A[0] :
  print(A[0] - dp[-1][0][0])
else :
  print(-1)

Submission status: Accepted

Solution code:
import sys

N_MAX = 200000 + 5
INF = 10**9 + 7
sys.setrecursionlimit(N_MAX)
MOD = 10**9 + 7


def main():
    _ = int(sys.stdin.readline().rstrip())
    Arr = [int(x) for x in sys.stdin.readline().rstrip().split()]

    K = 43

    #
    A = Arr[0]
    B = Arr[1]

    S = A + B
    X = 0
    for i in range(2, len(Arr)):
        X ^= Arr[i]

    # print(S, X)

    # 次を満たすa, b が見つかるか？
    #  a+b=S, a^b=X, a<=A

    # 桁DP : 桁を一つずつ決めていくようなDP
    # dp[今の桁数 = 0:42][繰り上がりがあるか = 0,1][今までがA以下かどうか 0=以下、1=より大きい] = 最大値
    # 値は最大値。満たすものがなければ -1
    dp = [[[-1 for x in [0, 1]] for _ in [0, 1]] for _ in range(K)]

    dp[0][0][0] = 0  # 最初

    v = 1
    for i in range(K - 1):  # 桁数
        cx = X & 1  # current X
        cs = S & 1  # current S
        ca = A & 1  # current A
        for j in range(2):  # 繰り上がりある／ない
            for k in range(2):  # 今までの範囲が A 以下かどうか
                if dp[i][j][k] == -1:  #
                    continue

                for na in range(2):
                    for nb in range(2):
                        ni = i + 1
                        nj = 0
                        nk = k
                        if na ^ nb != cx:  # a ^ b = A か？
                            continue

                        ns = na + nb + j
                        if ns % 2 != cs:  # a + b = S か？
                            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
        # print(v)

    a = dp[K - 1][0][0]
    if a == -1 or a == 0:
        print(-1)
    else:
        print(Arr[0] - a)


main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
xor = 0
if n == 2:
  a,b = a
  if a >= b and (a+b)%2 == 0:
    print((a+b)//2-b)
  else:
    print(-1)
  exit()
for i in range(2,n):
  xor ^= a[i]
a,b = a[0],a[1]
sm = a+b
ls = []
smt = 0
for i in range(50)[::-1]:
  if xor&1<<i:
    ls.append(1)
    smt += 1<<i
  else:
    if smt+(2<<i) > sm:
      ls.append(0)
    else:
      ls.append(2)
      smt += 2<<i
if smt != sm:
  print(-1)
  exit()
mn = 0
mx = 0
for i in range(50):
  if ls[49-i] == 1:
    mx += 1<<i
  elif ls[49-i] == 2:
    mn += 1<<i
    mx += 1<<i
if not mn <= a:
  print(-1)
  exit()
ans = mn
for i in range(50):
  if ls[i] == 1:
    if ans+(1<<(49-i)) > a:
      continue
    else:
      ans += 1<<(49-i)
if ans == 0:
  print(-1)
else:
  print(a-ans)

Submission status: Accepted

Solution code:
import sys

N_MAX = 200000 + 5
INF = 10**9 + 7
sys.setrecursionlimit(N_MAX)
MOD = 10**9 + 7


def main():
    _ = int(sys.stdin.readline().rstrip())
    Arr = [int(x) for x in sys.stdin.readline().rstrip().split()]

    K = 43

    #
    A = Arr[0]
    B = Arr[1]

    S = A + B
    X = 0
    for i in range(2, len(Arr)):
        X ^= Arr[i]

    # print(S, X)

    # 次を満たすa, b が見つかるか？
    #  a+b=S, a^b=X, a<=A

    # 桁DP : 桁を一つずつ決めていくようなDP
    # dp[今の桁数 = 0:42][繰り上がりがあるか = 0,1][今までがA以下かどうか 0=以下、1=より大きい] = 最大値
    # 値は最大値。満たすものがなければ -1
    dp = [[[-1 for x in [0, 1]] for _ in [0, 1]] for _ in range(K)]

    dp[0][0][0] = 0  # 最初

    v = 1
    for i in range(K - 1):  # 桁数
        cx = X & 1  # current X
        cs = S & 1  # current S
        ca = A & 1  # current A
        for j in range(2):  # 繰り上がりある／ない
            for k in range(2):  # 今までの範囲が A 以下かどうか
                if dp[i][j][k] == -1:  #
                    continue

                for na in range(2):
                    for nb in range(2):
                        ni = i + 1
                        nj = 0
                        nk = k
                        if na ^ nb != cx:  # a ^ b = A か？
                            continue

                        ns = na + nb + j
                        if ns % 2 != cs:  # a + b = S か？
                            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
        # print(v)

    a = dp[K - 1][0][0]
    if a == -1 or a == 0:
        print(-1)
    else:
        print(Arr[0] - a)


main()

Submission status: Accepted

Solution code:
# F - Unfair Nim

N = int(input())
A = list(int(a) for a in input().split())

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

dp = [[[-1] * 2 for i in range(2)] for j in range(50)]
dp[0][0][0] = 0

for i in range(49):
    cur_s = S>>i&1
    cur_x = X>>i&1
    cur_a = a>>i&1
    for j, k in ((0, 0), (0, 1), (1, 0), (1, 1)):
        if dp[i][j][k] == -1:
            continue
        for p, q in ((0, 0), (0, 1), (1, 0), (1, 1)):
            if p ^ q != cur_x:
                continue
            if (p + q + j)&1 != cur_s:
                continue
            ni = i + 1
            nj = 0
            if (p + q + j) >= 2:
                nj = 1
            if cur_a < p:
                nk = 1
            elif cur_a > p:
                nk = 0
            else:
                nk = k
            dp[ni][nj][nk] = max(dp[ni][nj][nk], dp[i][j][k]|(1<<i)*p)

tmp = dp[49][0][0]
if tmp == 0 or tmp == -1:
    print(-1)
else:
    print(a - tmp)

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:
from functools import reduce, lru_cache

INF = float("inf")

N, a, b, *A = map(int, open(0).read().split())
c = reduce(lambda a, b: a ^ b, A, 0)

@lru_cache(None)
def solve(a, b, c):
    if (a % 2) ^ (b % 2) != (c % 2):
        return INF
    if c == 0:
        return INF if a < b else (a - b) // 2

    return min(
        2 * solve(a // 2, b // 2, c // 2),
        1 + 2 * solve((a - 1) // 2, (b + 1) // 2, c // 2)
    )

print(-1 if (res := solve(a, b, c)) >= a else res)

Submission status: Accepted

Solution code:
from functools import lru_cache

def main():
    N = int(input())
    A = list(map(int, input().split()))
    x = 0
    for a in A[2:]:
        x ^= a
    a, b = A[0], A[1]
    if (a ^ b ^ x) & 1 != 0:
        return -1

    @lru_cache(None)
    def helper(a, b, x):
        if a == 0:
            return 0 if a ^ b == x else None
        if (a ^ b) & 1 != x & 1:
            return None
        t1 = helper(a // 2, b // 2, x // 2)
        t2 = helper((a - 1) // 2, (b + 1) // 2, x // 2)
        if t1 is None and t2 is None:
            return None
        if t1 is None:
            return t2 * 2 + 1
        if t2 is None:
            return t1 * 2
        t1 = t1 * 2
        t2 = t2 * 2 + 1
        return min(t1, t2)
    r = helper(a, b, x)
    if r is None or r >= a:
        return -1
    return r

print(main())

Submission status: Accepted

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

added = As[0] + As[1]
xored = 0
for A in As[2:]:
    xored ^= A

anded = added - xored
if anded % 2 == 1:
    print(-1)
    exit()
else:
    anded >>= 1

left_stones_l_A0 = '' # <= A[0] for sure.
left_stones_e_A0 = '' #not sure if this is <= A[0].
for i, (a, x) in enumerate(zip(format(anded, '045b'), format(xored, '045b'))):
    if x == '0':
        if a == '0':
            left_stones_l_A0 += '0'
            left_stones_e_A0 += '0'
        else:
            left_stones_l_A0 += '1'
            left_stones_e_A0 += '1'
    else:
        if a == '0':
            if int(left_stones_l_A0 + '1' + '1' * (44 - i), base = 2) <= As[0]:
                left_stones_l_A0 += '1'
            else:
                left_stones_l_A0 += '0'
            if int(left_stones_e_A0 + '1' + '1' * (44 - i), base = 2) <= As[0]:
                left_stones_e_A0 += '1'
                left_stones_l_A0 = left_stones_e_A0
            elif int(left_stones_e_A0 + '1' + '0' * (44 - i), base = 2) <= As[0]:
                left_stones_l_A0 = left_stones_e_A0 + '0'
                left_stones_e_A0 += '1'
            elif int(left_stones_e_A0 + '0' + '0' * (44 - i), base = 2) <= As[0]:
                left_stones_e_A0 += '0'
            else:
                left_stones_e_A0 = left_stones_l_A0
        else:
            print(-1)
            exit()

if int(left_stones_e_A0, base = 2) <= As[0]:
    ans = As[0] - int(left_stones_e_A0, base = 2)
else:
    ans = As[0] - int(left_stones_l_A0, base = 2)

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

Submission status: Accepted

Solution code:
from collections import defaultdict
mem = defaultdict(lambda : None)
mem[(0,0,0)] = 0
def dp(a,b,s):
  if mem[(a,b,s)] is not None:
    return mem[(a,b,s)]
  x = a&1
  y = b&1
  xor = s&1
  res = float("inf")
  if x^y != xor:
    mem[(a,b,s)] = res
    return res
  else:
    res = 2*dp(a>>1,b>>1,s>>1)
    if a > 1:
      pants = 2*dp((a-1)>>1,(b+1)>>1,s>>1)+1
      if pants < res:
        res = pants
  mem[(a,b,s)] = res
  return res

n = int(input())
a = list(map(int, input().split()))
s = 0
for i in a[2:]:
  s ^= i
b = a[1]
a = a[0]
ans = dp(a,b,s)
if ans == float("inf"):
  ans = -1
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
A=[int(i) for i in input().split()]

A1=A[0]
A2=A[1]

c=0
for ele in A[2:]:
    c^=ele

d=A1+A2-c
if d%2==1:
    print(-1)
else:
    d=d//2
    #print(bin(c),bin(d))
    flgs=[]
    
    for i in range(41):
        fand= d & (1<<i)
        fxor= c & (1<<i)
        
        if fand & fxor:
            print(-1)
            break
        elif fand:
            flgs.append(1)
        elif fxor:
            flgs.append(2)
        else:
            flgs.append(0)
    else:
        flgs=flgs[::-1]
        #print(flgs)
        ans=0
        for i in range(len(flgs)):
            if flgs[i]==1:
                ans+=2**(41-i-1)
        
        if ans>A1:
            print(-1)
        else:
            
            for i in range(len(flgs)):
                if flgs[i]==2:
                    if ans + 2**(41-i-1) <= A1:
                        ans+=2**(41-i-1)
            
            #print(ans)
            
            if ans==0:
                print(-1)
            else:
                print(A1-ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

K = 43


def main(input, print):
    n = int(input())
    a = list(map(int, input().split()))
    a1 = a[0]
    a2 = a[1]
    s = a1 + a2
    x = 0
    for i in range(2, n):
        x ^= a[i]

    dp = [[[-1 for _ in range(2)] for _ in range(2)] for _ in range(K)]
    dp[0][0][0] = 0
    v = 1
    for i in range(K-1):
        cx = x & 1
        cs = s & 1
        ca = a1 & 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):
                        ni = i + 1
                        nj = 0
                        nk = k
                        if na ^ nb != cx:
                            continue
                        ns = 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
        a1 >>= 1
        v <<= 1

    ans = dp[K-1][0][0]
    if ans == -1 or ans == 0:
        print(-1)
    else:
        print(a[0]-ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    A = LI()

    x = 0
    for i in A[2:]:
        x ^= i

    s = A[0] + A[1]
    if s - x < 0 or (s - x) % 2:
        print(-1)
        return

    a = (s-x)//2
    if a & x:
        print(-1)
        return

    b = 1 << (A[0].bit_length() - 1)
    while b > 0:
        if b & x and a + b <= A[0]:
            a += b
        b >>= 1
    if 0 < a <= A[0]:
        print(A[0] - a)
    else:
        print(-1)


if __name__ == '__main__':
    main()

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

x = 0
s = l[0]+l[1]
for i in l[2:]:
    x ^= i
if x > s or (s-x)%2 or ((s-x)//2)&x:
    print(-1)
    exit()
a = (s-x)//2
if a > l[0]:
    print(-1)
    exit()
for i in range(50,-1,-1):
    if 1<<i & x:
        if a+ (1<<i) <= l[0]:
            a += 1<<i
if a == 0:
    print(-1)
else:
    print(l[0]-a)

Submission status: Accepted

Solution code:
from functools import lru_cache

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

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

INF = 10 ** 18

@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 #xor = 0にできるのは aとbが同じときだけ --> aのほうが大きい必要がある
    #1の位を放置
    x = 2 * F(a // 2, b // 2, xor // 2)
    #1の位を移動
    y = 2 * F((a - 1) // 2, (b + 1) // 2, xor // 2) + 1 # +1 は移動コスト

    x = min(x, y)
    if x >= INF:
        x = INF
    
    return x

x = F(A[0], A[1], tmp)
if x >= A[0]:
    x = -1

print (x)

Submission status: Accepted

Solution code:

def resolve():
    # 後手必勝になる移動個数の最小を求める
    # 移動して A1xorA2 == A3~AN xor になるか
    # 移動個数を1つずつ試すとTLE なのでA1+A2を2つに分けて条件を満たす方法を探す
    N = int(input())
    A = list(map(int, input().split()))

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

    # 3～N番目のxor
    xor = 0
    for a in A[2:]:
        xor ^= a

    # S == A1xorA2 + 2(A1&A2) -> 2(A1&A2) == S - A3~AN xor
    # 2で割れなければ不可能
    S -= xor
    if S%2 == 1:
        return print(-1)

    S //= 2
    # A1&A2 と A1xorA2が同じ箇所のビットが立っていたら不可能
    if (S&xor) != 0 or S > A[0]:
        return print(-1)

    # A1 に残す個数は最低A1&A2であり、A1xorA2を上の桁から貪欲に、
    # i桁目が1かつ、減らす個数に加えてもAi以上にならないように加えていく
    b = S
    for i in range(41, -1, -1):
        if xor>>i & 1 == 1:
            if b + (1<<i) <= A[0]:
                b += 1<<i

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


if __name__ == "__main__":
    resolve()