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:
n = int(input())
alst = list(map(int, input().split()))
if n == 2:
    if sum(alst) % 2 != 0:
        print(-1)
    elif alst[0] < alst[1]:
        print(-1)
    else:
        print((alst[0] - alst[1]) // 2)
    exit()

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

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

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

Submission status: Wrong Answer

Solution code:
print(1)

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

Solution code:
print(0)

Submission status: Wrong Answer

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

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

ans = 0
for i in range(10**7):
    if (A[0]-i)<=0:
        print(-1)
        break
    if ((A[0]-i) ^ (A[1]+i) ^ mm) == 0:
        print(i)
        break

Submission status: Wrong Answer

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
    for i in range(NN):
        if g1 ^ g2 == g3:
            if ans != A[0]:
                print(ans)
            else:
                print(-1)
            exit()
        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
            elif r1 > r2:
                g1 -= r2
                g2 += r2
                ans += r2
            else:
                print(-1)
                exit()
    if g1 ^ g2 == g3:
        if ans != A[0]:
            print(ans)
        else:
            print(-1)
        exit()
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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):
        free_keta.append(i)
    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: Wrong Answer

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
    for i in range(NN-1, -1, -1):
        if g1 ^ g2 == g3:
            if ans != A[0]:
                print(ans)
            else:
                print(-1)
            exit()
        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
            elif r1 > r2:
                g1 -= r2
                g2 += r2
                ans += r2
            else:
                print(-1)
                exit()
    print(-1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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()
x=(l[0]+l[1]-sx)//2
y=x
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: Wrong Answer

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:
    print(-1)
else:
    print(a - n)

Submission status: Wrong Answer

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

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
    for i in range(NN-1, -1, -1):
        if g1 ^ g2 == g3:
            if ans != A[0]:
                print(ans)
            else:
                print(-1)
            exit()
        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
            else:
                g1 -= r2
                g2 += r2
                ans += r2
    print(-1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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(45):
    if C & (1 << i):
        free_keta.append(i)
    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: Wrong Answer

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 or z<0 or z&w:
    print(-1)
else:
    z //= 2
    """
    z = p&q
    v = p^q
    """
    #print(z,v,z&w)
    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: Wrong Answer

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(40):
    if C & (1 << i):
        free_keta.append(i)
    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: Wrong Answer

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
        strMinMove = bin(minStoneMovement)[2:]
        lenStrXOR = len(strXOR)
        cannotMove = False
        if len(strMinMove) > len(strXOR):
            cannotMove = True
        else:
            for i in range(lenStrXOR):
                if strXOR[i] == '0' and i >= len(strXOR) - len(strMinMove) and strMinMove[i + len(strMinMove) - len(strXOR)] == '1':
                    cannotMove = True
                    break
                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: Wrong Answer

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 or z<0:
    print(-1)
else:
    z //= 2
    """
    z = p&q
    v = p^q
    """
    #print(z,v)
    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: Wrong Answer

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()
x=(l[0]+l[1]-sx)//2
y=x
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)
print(l[0]-x)

Submission status: Wrong Answer

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:
    print(-1)
    exit()
else:
    z //= 2
    """
    z = p&q
    v = p^q
    """
    #print(z,v)
    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: Wrong Answer

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
        lenStrXOR = len(strXOR)
        for i in range(lenStrXOR):
            if strXOR[i] == '1' and minStoneMovement >= 2 ** (lenStrXOR - 1 - i):
                minStoneMovement -= 2 ** (lenStrXOR - 1 - i)
        if minStoneMovement == A[0]:
            print(-1)
        else:
            print(minStoneMovement)

Submission status: Wrong Answer

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
        lenStrXOR = len(strXOR)
        for i in range(lenStrXOR):
            if strXOR[i] == '1' and minStoneMovement >= 2 ** (lenStrXOR - 1 - i):
                minStoneMovement -= 2 ** (lenStrXOR - 1 - i)
        print(minStoneMovement)

Submission status: Wrong Answer

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

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)
    print("fdojfodjfod")
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: Time Limit Exceeded

Solution code:

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





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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
xor = 0
for i in range(2, n):
    xor ^= a[i]
for i in range(a[0]):
    if (a[0] - i) ^ (a[1] + i) == xor:
        print(i)
        exit()
print(-1)

Submission status: Time Limit Exceeded

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

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

ans = -1
for i in range(a[0]):
    a0 = (a[0] - i) ^ (a[1] + i)
    if a0 ^ a2 == 0:
        ans = i
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce

INF = float("inf")

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

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

Solution code:
N = int(input())
a = 0
A = []
for i in map(int,input().split()):
    A.append(i)
for i in range(2,N):
    a = a ^ A[i]
a0 = A[0]
p = -1
for i in range(1,a0):
    n0 = a0 - i
    n1 = A[1] + i
    n = n0 ^ n1
    if n ^ a == 0:
        p = i
        break
print(p)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
N = int(input())
A = [int(i) for i in input().split()]
if N > 2:
    x = reduce(lambda x,y:x^y, A[2:])
elif N == 1:
    x = A[-1]
else:
    x = 0
for i in range(A[0]):
    if x^(A[0]-i)^(A[1]+i) == 0:
        print(i)
        break
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
n, *A = map(int, open(0).read().split())
s = 0
if n >= 3:
  for a in A[2:]:
    s ^= a

if (s + A[0] + A[1]) % 2:
  print(-1)
  exit()
if s > A[0] + A[1]:
  print(-1)
  exit()

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

Submission status: Time Limit Exceeded

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

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

n = I()
mylist = LI()
mylist.append(0)

#初期化
before = 0
for i in mylist[2:]:
    before = before ^ i
a = mylist[0]
b = mylist[1]

for i in range(a):
    if (a-i) ^ (b+i) ^ before == 0:
        print(i)
        sys.exit()
        
print(-1)

Submission status: Time Limit Exceeded

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

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

n = I()
mylist = LI()
mylist.append(0)

#初期化
before = 0
for i in mylist[2:]:
    before = before ^ i
a = mylist[0]
b = mylist[1]

for i in range(a):
    if (a-i) ^ (b+i) ^ before == 0:
        print(i)
        sys.exit()
        
print(-1)

Submission status: Time Limit Exceeded

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

INF=10**18
def calc(a,b,xor):
  if (a&1)^(b&1)!=(xor&1):
    return INF
  if xor==0:
    if a<b:
      return INF
    else:
      return (a-b)//2
  x=2*calc(a//2,b//2,xor//2)
  y=2*calc((a-1)//2,(b+1)//2,xor//2)+1
  return min(x,y)

n=int(input())
arr=list(map(int,input().split()))
a,b=arr[0],arr[1]
xor=0
for i in range(2,n):
  xor^=arr[i]
ans=calc(a,b,xor)
if ans>=a:
  print(-1)
else:
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
INF=10**18
def calc(a,b,xor):
  if (a&1)^(b&1)!=(xor&1):
    return INF
  if xor==0:
    if a<b:
      return INF
    else:
      return (a-b)//2
  x=2*calc(a//2,b//2,xor//2)
  y=2*calc((a-1)//2,(b+1)//2,xor//2)+1
  return min(x,y)

n=int(input())
arr=list(map(int,input().split()))
a,b=arr[0],arr[1]
xor=0
for i in range(2,n):
  xor^=arr[i]
ans=calc(a,b,xor)
if ans>=a:
  print(-1)
else:
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from operator import xor
n = int(input())
A1, A2, *A = list(map(int, input().split()))
if A:
    Axor = reduce(xor, A)
else:
    Axor = 0

for a in range(A1):
    if (A1-a) ^ (A2+a) == Axor:
        print(a)
        break
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from collections import defaultdict
N = int(input())
A = list(map(int,input().split()))

r = reduce(lambda x,y : x^y , A[2:],0)

a,b = A[:2]

def answer(ta,tb,tr):
    for i in range(ta):
        if (ta-i)^(tb+i) == tr:
            ans = i
            break
    else:
        ans = -1
    return ans

def solve(a,b,r):
    orga = a

    ans = 0
    l = max(map(lambda x : len(bin(x)), [a,b,r])) - 2
    cand = {(a,b,r):0}
    for i in range(l):
        temp = defaultdict(lambda : 10**10)
        for (a,b,r),s in cand.items():
            x,y,z = a%2,b%2,r%2
            if not x^y == z:
                continue
            else:
                if s < temp[(a//2,b//2,r//2)]:
                    temp[(a//2,b//2,r//2)] = s
                a -= 1
                b += 1
                if a < 0:
                    continue
                s += (1<<i)
                if s < temp[(a//2,b//2,r//2)]:
                    temp[(a//2,b//2,r//2)] = s
        cand = temp

    if not (0,0,0) in cand:
        ans = -1
    else:
        ans = cand[(0,0,0)]
        if ans == orga:
            ans = -1
    return ans

print(answer(a,b,r))

Submission status: Time Limit Exceeded

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

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 == 0:
			c = i
			break
	print(c)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
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 == 0:
		c = i
		break
print(c)

Submission status: Time Limit Exceeded

Solution code:
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 == 0:
		c = i
		break
print(c)

Submission status: Time Limit Exceeded

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

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


main()

Submission status: Time Limit Exceeded

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

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


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
#import numpy as np
#from collections import defaultdict
import math
#from collections import deque

#input = sys.stdin.readline
#import numpy as n
import bisect



def main():
    N = int(input())

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

    a1= A.pop(0)
    a2 = A.pop(0)
    ans =0
    for i in A:
        ans ^=i


    for i in range(a1):
        stone_n = (a1-i)^(a2+i)
        if stone_n == ans:
            print(i)
            exit()
    print(-1)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from operator import xor
from functools import reduce

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

s = reduce(xor, A)
flg = False
for i in range(A[0]):
    if i != 0:
        A[0] -= 1
        A[1] += 1
    s = reduce(xor, A)
    if reduce(xor, A)==0:
        print(i)
        flg = True
        break

if not flg:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    xor = 0
    for i in range(2, N):
        xor ^= A[i]
    ans = 0
    for idx in range(40)[::-1]:
        base = 2**idx
        diff = 0
        if xor & base and A[0] < base and A[1] < base:
            if A[0] + A[1] >= base:
                ans += base - A[1]
                A[0] = A[1] + A[0] - base
                A[1] = base
            else:
                print(-1)
                return
    for i in range(A[0]):
        if (A[0]-i) ^ (A[1]+i) == xor:
            print(i)
            return
    print(-1)


if __name__ == "__main__":
    main()