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:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

# (A0 - m) ^ (A1 + m) == XORとなる最小のmを考える

#処理内容
def main():
	N = int(input())
	A = getlist()
	XOR = 0	
	for i in range(2, N):
		XOR ^= A[i]

	Asum = A[0] + A[1]
	ans = INF
	AA = Asum
	# print(A[0], A[1], XOR)
	a0 = 0; a1 = 0
	# XORが1のbitの値を先に引く
	for i in range(50, -1, -1):
		if (2 ** i) & XOR == (2 ** i):
			AA -= 2 ** i

	# print(AA)

	# XORが0のbitの01を決める
	for i in range(50, -1, -1):
		if (2 ** i) & XOR == 0:
			if AA >= 2 ** (i + 1):
				AA -= 2 ** (i + 1)
				a0 += 2 ** i
				a1 += 2 ** i
			else:
				pass

	# print(a0, a1)

	# a0のbitをどん欲に決める
	for i in range(50, -1, -1):
		if (2 ** i) & XOR == (2 ** i):
			if a0 + 2 ** i <= A[0]:
				a0 += 2 ** i
			else:
				a1 += 2 ** i

	if a0 == 0 or a0 > A[0] or a0 + a1 != Asum or a0 ^ a1 != XOR:
		print(-1)
	else:
		print(A[0] - a0)

	# print(a0, a1)


if __name__ == '__main__':
	main()

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


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
    swappable = []
    while b:
        bx = x & b
        if bx == 0:
            # print('bx=0', s)
            # print(f'{b:040b}')
            # print(f'{p:040b}')
            # print(f'{q:040b}')
            # print(f'{a0:040b}')
            # print(f'{a1:040b}')
            # print()
            if s >= 2 * b:
                if p | b <= a0:
                    p |= b
                    q |= b
                    s -= 2 * b
                elif swappable:
                    bs = swappable.pop()
                    p ^= bs
                    q ^= bs
                    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
                swappable.append(b)
            else:
                q |= b
            s -= b

            # print('bx=1', s)
            # print(f'{b:040b}')
            # print(f'{p:040b}')
            # print(f'{q:040b}')
            # print(f'{a0:040b}')
            # print(f'{a1:040b}')
            # print()

        b >>= 1

    if p == 0:
        return -1
    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:
import sys
n = int(input())
a = list(map(int, input().split()))
c = a[0] + a[1]

t = 0

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

bit_len = c.bit_length()+1

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

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

b1 = (c - t) // 2


a1 = b1
a2 = b1


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

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

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

Submission status: Accepted

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

if n == 2:
  if a[0] >= a[1] and (a[0] - a[1]) % 2 == 0:
    print((a[0] - a[1]) // 2)
  else:
    print(-1)
else:
  num = 0
  for i in range(2, n):
    num ^= a[i]
  
  _and = (a[0] + a[1] - num)
  if  _and % 2 != 0 or a[0] < _and // 2 or (_and // 2) & num != 0:
    print(-1)
  else:
    _and //= 2
    
    max_2 = 1
    while max_2 <= num:
      max_2 *= 2
    
    a0 = _and
    while max_2 >= 1:
      if num & max_2 != 0 and a0 + max_2 <= a[0]:
        a0 += max_2
      max_2 //= 2
    
    if a0 != 0:
      print(a[0] - a0)
    else:
      print(-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)


def solve(N: int, A: "List[int]"):
    def _to_bits(v):
        xb = []
        h = {}
        i = 0
        while v > 0:
            xb.append((2 ** i, v % 2))
            h[2 ** i] = v % 2
            v //= 2
            i += 1
        return xb, h
    xor = 0
    for i in range(2, N):
        xor ^= A[i]
    s = A[0] + A[1]
    #print(xor, s)
    rest = s - xor
    if rest < 0 or rest % 2 or (rest // 2) > A[0]:
        ret = -1
    else:
        ret = 0
        rest //= 2
        xb, xx = _to_bits(xor)
        rb, rr = _to_bits(rest)
        for k, v in rr.items():
            if v == 1 and k in xx and xx[k] == 1:
                ret = -1
                print(ret)
                return
        #print(xb)
        #print(rb)
        #print(rest)
        xb.reverse()
        tmp = rest
        for base, v in xb:
            #if v:
            #    print(base, v, tmp)
            if v and tmp + base < A[0]:
                tmp += base
        if tmp > 0:
            ret = A[0] - tmp
        else:
            ret = -1
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = [int(a) for a in input().split()]
t = 0
for a in A[2:]:
    t ^= a
s = sum(A[:2])
if s < t or (s ^ t) & 1:
    print(-1)
    exit()
 
u = (s - t) // 2
a = A[0]
n = 0
for i in range(40)[::-1]:
    b, c = (t >> i) & 1, (u >> i) & 1
    if b == c == 1:
        print(-1)
        exit()
    if b == 0 and c == 1:
        n += 1 << i
for i in range(40)[::-1]:
    b, c = (t >> i) & 1, (u >> 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)

Submission status: Accepted

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

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

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

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

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

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

goal = dif

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

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

print(start-goal)

Submission status: Accepted

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

if ALL == 0:
    print(0)
    sys.exit()

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

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

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

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

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

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

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

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

print(A[0] - ans)

Submission status: Accepted

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

X = 0

#print(bin(A[0]))
#print(bin(A[2]))
for i in range(2,N):
    X ^= A[i]
if X>A[0]+A[1]:
    print(-1)
else:
    Y = A[0]+A[1]-X
    bY = bin(Y)[2:][::-1]
    bX = bin(X)[2:][::-1]
    if bY[0]=="1":
        print(-1)
    else:
        flag = True
        for i in range(1,len(bY)):
            if bY[i]=="1":
                if i-1<len(bX):
                    if bX[i-1]=="1":
                        flag = False
                        break
        if flag:
            if Y//2>A[0]:
                #print(X,Y)
                print(-1)
            else:
                a = Y//2
                #print(a)
                #print(bX)
                for i in range(len(bX)):
                    if bX[len(bX)-i-1]=="1":
                        if a + 2**(len(bX)-i-1) <= A[0]:
                            #print(i)
                            a += 2**(len(bX)-i-1)
                            #print(a)
                if a!=0:
                    print(A[0]-a)
                else:
                    print(-1)
        else:
            print(-1)

Submission status: Accepted

Solution code:
"""

Xorを0にする

(A1-X)^(A2+X) ^ C == 0
となる最小のX

合計が決まっている
C側からありえそうなものだけ出す？
1なら 10 , 01
0なら 00 , 11
大きい方から決めていく
0の桁が両0 or 1は確定する
1は好きな方に割り振っていい
A1以下最大になるように寄せればおｋ

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

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

a = A[0]
b = A[1]

remc = a+b
ori = 0

#print (remc)
lis = [None] * 60
for i in range(59,-1,-1):

    np = 2**i

    if np & c > 0:
        lis[i] = -1 #自由
        remc -= np
    else:
        if remc >= np*2:
            remc -= np * 2
            lis[i] = 1
            ori |= np
        else:
            lis[i] = 0
#print (remc,lis)
if remc != 0 or ori > a:
    print (-1)
    sys.exit()

ao = ori
#print (lis)
for i in range(59,-1,-1):

    np = 2**i
    if lis[i] == -1 and ao|np <= a:
        ao |= np

if ao > 0:
    print (a-ao)
else:
    print (-1)

Submission status: Accepted

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
    cnt = 0
    while True:
        cnt += 1
        if cnt == 10000:
            print(-1)
            exit()
        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: Accepted

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

S = a[0] + a[1]
C = 0
for i in range(2, n):
    C ^= a[i]

D = S - C

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

D //= 2

ans = 0

free_keta = []

for i in range(100):
    if (C & (1 << i)) != 0:
        free_keta.append(i)
        if (D & (1 << i)) != 0:
            print(-1)
            exit()
    else:
        ans += (D & (1 << i))

if ans > a[0]:
    print(-1)
    exit()
        
for keta in free_keta[::-1]:
    if ans + (1 << keta) <= a[0]:
        ans += (1 << keta)

if ans == 0:
    print(-1)
    exit()
    
print(a[0] - ans)

Submission status: Accepted

Solution code:
import sys
def input():return sys.stdin.readline()[:-1]
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
n=N()
l=L()
sx=0
for i in l[2:]:
    sx^=i
if sx>l[0]+l[1]:
    print(-1)
    quit()
if (l[0]+l[1]-sx)%2==1:
    print(-1)
    quit()
if sx^l[0]^l[1]==0:
    print(0)
    quit()
x=(l[0]+l[1]-sx)//2
y=x
if x&sx>0:
    print(-1)
    quit()
if x>l[0]:
    print(-1)
    quit()
for i in range(45,-1,-1):
    if sx>>i&1:
        if l[0]>=(x+(1<<i)):
            x+=(1<<i)
if x==0:
    print(-1)
    quit()
print(l[0]-x)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
xorValue = 0
sumValue = A[0] + A[1]
for i in range(2,N):
    xorValue ^= A[i]
if sumValue % 2 != xorValue % 2:
    print(-1)
else:
    Base = (sumValue - xorValue) // 2
    if Base > A[0]:
        print(-1)
    else:
        strXOR = bin(xorValue)[2:]
        minStoneMovement = A[0] - Base
        strBase = bin(Base)[2:]
        lenStrXOR = len(strXOR)
        cannotMove = False
        if Base < 0:
            cannotMove = True
        for i in range(-1,-1 * min(len(strXOR),len(strBase)) - 1,-1):
            if strBase[i] == '1' and strXOR[i] == '1':
                cannotMove = True
                break
        if not cannotMove:
            for i in range(lenStrXOR):
                if strXOR[i] == '1' and minStoneMovement >= 2 ** (lenStrXOR - 1 - i):
                    minStoneMovement -= 2 ** (lenStrXOR - 1 - i)
        if minStoneMovement == A[0] or cannotMove:
            print(-1)
        else:
            print(minStoneMovement)

Submission status: Accepted

Solution code:
import sys

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

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

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

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

main()

Submission status: Accepted

Solution code:
N = int(input())
A = [int(a) for a in input().split()]
t = 0
for a in A[2:]:
    t ^= a
s = sum(A[:2])
if s < t or (s ^ t) & 1:
    print(-1)
    exit()

u = (s - t) // 2
a = A[0]
n = 0
for i in range(40)[::-1]:
    b, c = (t >> i) & 1, (u >> i) & 1
    if b == c == 1:
        print(-1)
        exit()
    if b == 0 and c == 1:
        n += 1 << i
for i in range(40)[::-1]:
    b, c = (t >> i) & 1, (u >> 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)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,*a = map(int,read().split())

v = 0
for i in a[2:]:
    v ^= i

w = a[0]+a[1]

z = w-v
if z&1==1 or z<0:
    print(-1)
else:
    z //= 2
    """
    z = p&q
    v = p^q
    """
    if z&v:
        print(-1)
        exit()

    ans = z
    for i in range(60,-1,-1):
        m = 1<<i
        if v&m:
            if ans+m <= a[0]:
                ans += m
                #print(ans,i)

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

Submission status: Accepted

Solution code:
import bisect

N=int(input())
A=list(map(int,input().split()))
x=0
for i in range(2,N):
    x^=A[i]
#print(x)
if (A[0]+A[1]-x)%2!=0:
    print(-1)
else:
    AND=(A[0]+A[1]-x)//2
    u=AND
    v=AND
    if AND&x!=0:
        print(-1)
        exit()
    t=[i for i in range(40) if x>>i &1==1]
    #print(t)
    k=len(t)//2
    data1=[]
    data2=[]
    for i in range(2**k):
        temp=0
        for j in range(k):
            if i>>j&1==1:
                temp+=2**t[j]
        data1.append(temp)
    for i in range(2**(len(t)-k)):
        temp=0
        for j in range(len(t)-k):
            if i>>j&1==1:
                temp+=2**t[k+j]
        data2.append(temp)

    #print(data1,data2)
    ans=-1
    val=float("inf")
    for test in data1:
        temp=test+u
        #print(temp)
        id=bisect.bisect_right(data2,A[0]-temp)
        if id!=0:
            temp+=data2[id-1]
            if val>A[0]-temp and A[0]>=temp and temp!=0:
                val=A[0]-temp
                ans=temp
        else:
            if val>A[0]-temp and A[0]>=temp and temp!=0:
                val=A[0]-temp
                ans=temp
        #print(val,"jfkdjfd")
        #print(data1,data2,temp)
    #print(data1,data2)

    if val!=float("inf"):
        print(val)
    else:
        print(-1)

Submission status: Runtime Error

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
if m>a[0]or(m&X)!=0:exit(print(-1))
l=1<<max(x.bit_length(),m.bit_length())
while l > 0:
 if (m&l)!=0and(a|b)<=a[0]:a|=b
 b>>=1
print(a[0]-m if a!=0else-1)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
T = 0
if N > 2:
  for i in range(2,N):
    T ^= A[i]
N = A[0]^A[1]^T
n = len(bin(A[0]))-2
ans = 0
for i in range(n):
  if bin(N)[-(i+1)] == "0" and bin(N)[-(i+2)] == "1":
    A[0] -= 2**i
    A[1] += 2**i
    N = A[0]^A[1]^T
    ans += 2**i
  if N == 0:
    break
else:
  print(-1)
  exit()
if A[0] == 0:
  print(-1)
else:
  print(ans)

Submission status: Runtime Error

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' + '0' * (44 - i), base = 2) <= As[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
                raise ValueError
        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: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
def main():
	N = int(input())
	a = list(map(int,input().split()))
	b = 0
	c = -1
	for i in range(2,N):
		b = b^a[i]
	for i in range(a[0]):
	#print((a[0]-i) ^ b)
		if (a[0]-i) ^(a[1] + i) == 　b:
			c = i
			break
	print(c)
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
#define INF 5000000000000000000
#define ll long long
#define pll pair<ll, ll>
using namespace std;

int main() {
  ll N;
  cin >> N;
  vector<ll> A(N);
  ll either = 0;
  ll sum = 0;
  for (ll i = 0; i < N; ++i) {
    cin >> A.at(i);
    if (i > 1) {
      either ^= A.at(i);
    }
    else {
      sum += A.at(i);
    }
  }
  ll both = sum - either;
  if (both % 2 == 1 || both > A.at(0) * 2) {
    cout << -1 << "\n";
    return 0;
  }
  both /= 2;
  if ((either & both) != 0) {
    cout << -1 << "\n";
    return 0;
  }
  ll ans_small = 0;
  for (ll i = 40; i >= 0; --i) {
    if (either & 1 << i) {
      if (ans_small + pow(2, i) + both <= A.at(0)) {
        ans_small += pow(2, i);
      }
    }
  }
  if (both + ans_small == 0) {
    cout << -1 << "\n";
    return 0;
  }
  ll ans = A.at(0) - (both + ans_small);
  cout << ans << "\n";
}

Submission status: Runtime Error

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, b1,b2,b3 = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    L = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    R = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    A=[[L[i][j] for i in range(N)] for j in range(N)]
    aveL=0
    aveR=0
    for li, ri in zip(L,R):
        aveL+=sum(li)
        aveR+=sum(ri)
    aveL/=N**2
    aveR/=N**2
    tave=round((aveL+aveR)*0.5)

    for i in range(0,N):
        for j in range(0,N):
            kouho=set()
            l=L[i][j]
            r=R[i][j]
            
            for i2 in range(i-1):
                yoko=0
                for k in range(i2,i):
                    yoko+=A[k][j]
                    for b in (b1,b2,b3):
                        if l<=b-yoko<=r:
                            kouho.add((b-yoko,b))
            for j2 in range(j-1):
                tate=0
                for k in range(j2,j):
                    tate+=A[i][k]
                    for b in (b1,b2,b3):
                        if l<=b-tate<=r:
                            kouho.add((b-tate,b))
            if not kouho:
                if l<=tave<=r:
                    A[i][j]=tave
                elif tave<l:
                    A[i][j]=l
                else:A[i][j]=r
                continue
            opt=-10000000
            dif=1000000
            for (x,b) in kouho:
                cdif=-abs(x-tave)-b*10
                if cdif<dif:
                    opt=x
                    dif=cdif
            A[i][j]=opt

    for a in A:
        print(*a)
    f="./out.txt"

    with open(f,"w") as f1:
        for a in A:
            for ai in a:
                f1.write(str(ai)+" ")  
            f1.write("\n")





if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
n=int(input())
A=[int(i) for i in input().split()] #[random.randint(1,10**12) for _ in range(10)]

def f(A):
    s=0
    for a in A:
        s^=a
    return s

if n>=3:
    X=f(A[2:])
else:
    X=0

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

a = D#format(D,"045b")
b = K#format(K,"045b")
#print(S,X,D)
Y = format(0,"045b")
Y = list(Y)
X = format(X,"045b")
X = list(X)

if D <= A[0]:
    print(-1)
    sys.exit()
for i in range(45):
    #print(int("".join(X),2) ,int("".join(Y),2) )
    if X[i] == "0":
        continue
    
    Y[i] = "1"
    
    if D ^ int("".join(Y),2) <= A[0]:
        continue
    else:
        Y[i] = "0"
print(A[0] - D ^  int("".join(Y),2))

Submission status: Runtime Error

Solution code:
import random 

import sys
n=int(input())
A=[int(i) for i in input().split()] #[random.randint(1,10**12) for _ in range(10)]
def f(A):
    s=0
    for a in A:
        s^=a
    return s
if n>=3:
    X=f(A[2:])
else:
    X=0
S = A[0] + A[1]    
D = S - X
if D%2 != 0 or D<0:
    print(-1)
    sys.exit()
else:
    D //= 2

a = D#format(D,"045b")
b = K#format(K,"045b")
#print(S,X,D)
Y = format(0,"045b")
Y = list(Y)
X = format(X,"045b")
X = list(X)

for i in range(45):
    #print(int("".join(X),2) ,int("".join(Y),2) )
    if X[i] == "0":
        continue
    
    Y[i] = "1"
    
    if D ^ int("".join(Y),2) <= A[0]:
        continue
    else:
        Y[i] = "0"
print(A[0] - D ^  int("".join(Y),2))

Submission status: Runtime Error

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:
            ans += a << i
    i -= 1
print(a[0]-ans)