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

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

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:
                    raise RuntimeError
                    # 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: Runtime Error

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())
ans = solve(n, aaa)
if ans == -1:
    raise RuntimeError
print(solve(n, aaa))

Submission status: Runtime Error

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

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)

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n = int(readline())
lst2 = list(map(int,readline().split()))

res = 0
for i in lst2:
    res = res^i
print(res)
lst1 = []
for i in range(len(bin(res))):
    lst1.append((res>>i)&1)
if sum(lst1) == 0:
    print(0)
elif sum(lst1) == 1:
    if lst1[0] == 1:
        print(-1)
        exit()
    else:
        for i in range(len(lst1)):
            if lst1[i] == 1:
                if lst2[0] >= 1<<i
                print(i)
                exit()
print(-1)

Submission status: Runtime Error

Solution code:
import random

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

X = A[0]
Y = A[1]
Z = 0
for a in A[2:]:
  Z ^= a

if ((X^Y)&1)!=(Z&1):
  print(-1)
  exit(1)

def solve(X2, Y2):
  if ((X2^Y2)&1)!=(Z&1):
    return -1
  d = 0
  for i in range(1, 100):
    if (((X2-d)^(Y2+d))>>i&1)!=(Z>>i&1):
      d += 1<<(i-1)
  if d<X2:
    return d
  else:
    return -1

ans = solve(X, Y)
for i in range(10000):
  if ans<=2:
    break
  r = random.randint(1, ans-1)
  a = solve(X-r, Y+r)
  if a!=-1 and r+a<ans:
    ans = r+a
print(ans)

Submission status: Runtime Error

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()
if 
print(l[0]-x)

Submission status: Runtime Error

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
        for i in range(-1,-1 * min(len(strXOR),len(strBase)) - 1,-1):
            if Base[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: Runtime Error

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
        for i in range(-1,-1 * min(len(strXOR),str(Base)) - 1,-1):
            if Base[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: Runtime Error

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:
        assert False
        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()