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

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:
        ans = -1
    else:
        v1 = tmp
        v2 = tmp
        kouho = []
        s = 0
        v = 1
        ans = None
        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)
                
        if ans is None:
            for num in kouho[::-1]:
                s -= num
                if 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: Wrong Answer

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

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

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
print(a[0]-ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a,b,*c=map(int,input().split())
aaa=a
bbb=b
x=0
for i in c:x^=i
t=[0]*41
xt=[0]*41
c=a+b
for i in range(41):
  if c&(1<<i):t[i]=1
  if x&(1<<i):xt[i]=1
for i in range(40,0,-1):
  if xt[i]==0:
    tt=t[i]%2
    t[i]-=tt
    t[i-1]+=tt*2
  else:
    tt=(t[i]+1)%2
    t[i]-=tt
    t[i-1]+=tt*2
ans=0
for i in range(40,0,-1):
  if t[i]>=4:exit(print(-1))
  z=1<<i
  if t[i]==0:
    if a&z:
      v=a-(z-1)
      ans+=v
      b+=v
      a-=v
  if t[i]==1:
    if (a&z)==(b&z)==0:
      v=z-b
      ans+=v
      b+=v
      a-=v
    elif (a&z)==(b&z)==z:
      v=a-(z-1)
      ans+=v
      b+=v
      a-=v
  if t[i]==2:
    if (b&z)==0:
      v=z-b
      ans+=v
      b+=v
      a-=v
  if a&z:a-=z
  if b&z:b-=z
if not(0<=ans<aaa):exit(print(-1))
if (aaa-ans)^(bbb+ans)!=x:exit(print(-1))
print(ans)

Submission status: Wrong Answer

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 + a1 != Asum or a0 ^ a1 != XOR:
		print(-1)
	else:
		print(A[0] - a0)

	# print(a0, a1)


if __name__ == '__main__':
	main()

Submission status: Wrong Answer

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:
		print(-1)
	else:
		print(A[0] - a0)

	# print(a0, a1)


if __name__ == '__main__':
	main()

Submission status: Wrong Answer

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(35, -1, -1):
		if (2 ** i) & XOR == (2 ** i):
			AA -= 2 ** i

	# print(AA)

	# XORが0のbitの01を決める
	for i in range(35, -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(35, -1, -1):
		if (2 ** i) & XOR == (2 ** i):
			if a0 + 2 ** i <= A[0]:
				a0 += 2 ** i
			else:
				a1 += 2 ** i

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

	# print(a0, a1)


if __name__ == '__main__':
	main()

Submission status: Wrong Answer

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
    while b:
        bx = x & b
        if bx == 0:
            # print('bx', 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
                else:
                    return -1
        else:
            if s < b:
                return -1
            if p | b <= a0 and q | b > a1:
                p |= b
            else:
                q |= b
            s -= b

        # 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: Wrong Answer

Solution code:
import numpy as np
n=int(input())
a=np.array(list(map(int,input().split())))
s=np.bitwise_xor.reduce(a)
if s==0:
  print(0)
  exit()
s2=a[0]^a[1]^s
a_0=a[0]
a_1=a[1]
k=a[0]
for i in range(k):
  a_1+=1
  a_0+=-1
  if a_1^ a_0 ^ s2 ==0:
    print(i+1)
    exit()
print(-1)

Submission status: Wrong Answer

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 & 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: Wrong Answer

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))
    def dfs(a0,a1,ref):
        q=[(0,a0,a1,ref,0)]
        visited=set()
        while q:
            tot,a0,a1,ref,j=heappop(q)#ここをpopleftにすると幅優先探索BFSになる
            
            if a0 in visited:
                continue
            if a0^a1==ref:
                return tot
            visited.add(a0)


            if ((a0>>j)&1)^((a1>>j)&1)!=(ref>>j)&1:
                heappush(q,(tot,a0,a1,ref,j+1))
            a0-=1<<j
            a1+=1<<j
            if a0>0:
                heappush(q,(tot+(1<<j),a0,a1,ref,j+1))

        return -1
    print(dfs(a0,a1,ref))
    # 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: Wrong Answer

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
    while b:
        bx = x & b
        if bx == 0:
            # print('bx', 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
                else:
                    return -1
        else:
            if s < b:
                return -1
            if p + b <= a0 and q + b > a1:
                p |= b
            else:
                q |= b
            s -= b

        # 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: Wrong Answer

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))
    def dfs(a0,a1,ref):
        q=[(0,a0,a1,ref,0)]
        # visited=set()
        while q:
            tot,a0,a1,ref,j=heappop(q)#ここをpopleftにすると幅優先探索BFSになる
            
            # if a0 in visited:
            #     continue
            if a0^a1==ref:
                return tot
            #visited.add(a0)


            if ((a0>>j)&1)^((a1>>j)&1)!=(ref>>j)&1:
                heappush(q,(tot,a0,a1,ref,j+1))
            a0-=1<<j
            a1+=1<<j
            if a0>=0:
                heappush(q,(tot+(1<<j),a0,a1,ref,j+1))

        return -1
    print(dfs(a0,a1,ref))
    # 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: Wrong Answer

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 << 50
    while b:
        bx = x & b
        if bx == 0:
            # print('bx', 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
                else:
                    return -1
        else:
            if s < b:
                return -1
            if p + b <= a0 and q + b > a1:
                p |= b
            else:
                q |= b
            s -= b

        # 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
    return a0 - p


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

Submission status: Wrong Answer

Solution code:
n=int(input())
a,b,*c=map(int,input().split())
aaa=a
bbb=b
x=0
for i in c:x^=i
t=[0]*41
xt=[0]*41
c=a+b
for i in range(41):
  if c&(1<<i):t[i]=1
  if x&(1<<i):xt[i]=1
for i in range(40,0,-1):
  if xt[i]==0:
    tt=t[i]%2
    t[i]-=tt
    t[i-1]+=tt*2
  else:
    tt=(t[i]+1)%2
    t[i]-=tt
    t[i-1]+=tt*2
ans=0
for i in range(40,0,-1):
  z=1<<i
  if t[i]==0:
    if a&z:
      v=a-(z-1)
      ans+=v
      b+=v
      a-=v
  if t[i]==1:
    if (a&z)==(b&z)==0:
      v=z-b
      ans+=v
      b+=v
      a-=v
    elif (a&z)==(b&z)==z:
      v=a-(z-1)
      ans+=v
      b+=v
      a-=v
  if t[i]==2:
    if (b&z)==0:
      v=z-b
      ans+=v
      b+=v
      a-=v
  if a&z:a-=z
  if b&z:b-=z
if aaa==ans:exit(print(-1))
if (aaa-ans)^(bbb+ans)!=x:exit(print(-1))
print(ans)

Submission status: Wrong Answer

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))
    def dfs(a0,a1,ref):
        q=[(0,a0,a1,ref,0)]
        visited=set()
        while len(q):
            tot,a0,a1,ref,j=heappop(q)#ここをpopleftにすると幅優先探索BFSになる
            
            if a0 in visited:
                continue
            if a0^a1==ref:
                return tot
            visited.add(a0)


            if ((a0>>j)&1)^((a1>>j)&1)!=(ref>>j)&1:
                a0-=1<<j
                a1+=1<<j
                if a0>=0:
                    heappush(q,(tot+(1<<j),a0,a1,ref,j+1))
            else:
                heappush(q,(tot,a0,a1,ref,j+1))
                a0-=1<<j
                a1+=1<<j

                if a0>=0:
                    heappush(q,(tot+(1<<j),a0,a1,ref,j+1))
        return -1
    print(dfs(a0,a1,ref))
    # 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: Wrong Answer

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))
    def dfs(a0,a1,ref):
        q=[(0,a0,a1,ref,0)]
        visited=set()
        while len(q):
            tot,a0,a1,ref,j=heappop(q)#ここをpopleftにすると幅優先探索BFSになる
            
            if a0 in visited:
                continue
            if a0^a1==ref:
                return tot
            visited.add(a0)


            if ((a0>>j)&1)^((a1>>j)&1)!=ref>>j&1:
                a0-=1<<j
                a1+=1<<j
                if a0>=0:
                    heappush(q,(tot+(1<<j),a0,a1,ref,j+1))
            else:
                heappush(q,(tot,a0,a1,ref,j+1))
                a0-=1<<j
                a1+=1<<j

                if a0>=0:
                    heappush(q,(tot+(1<<j),a0,a1,ref,j+1))
        return -1
    print(dfs(a0,a1,ref))
    # 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: Wrong Answer

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
    while b:
        bx = x & b
        if bx == 0:
            # print('bx', 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
                else:
                    return -1
        else:
            if s < b:
                return -1
            if p + b <= a0 and q + b > a1:
                p |= b
            else:
                q |= b
            s -= b

        # 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
    if p ^ q != x:
        return -1
    if p > a0:
        return -1
    return a0 - p


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

Submission status: Wrong Answer

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

X=0
if N>2:
    for i in range(2,N):
        X^=L[i]
#print(X)

ans=10**13

for i in range(41):
    if L[0]>(2**i):
        if (2**i-1)^(L[1]+1+L[0]-2**i)==X:
            ans=min(ans,L[0]-2**i+1)
#print(ans)
for i in range(41):
    if 2**i-L[1]<L[0] and 2**i>=L[1]:
        if 2**i^(L[0]-2**i+L[1])==X:
            ans=min(ans,2**i-L[1])
if ans==10**13:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

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