Submission #14737629


Source Code Expand

Copy
import sys
from functools import lru_cache

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, *A = map(int, read().split())

a, b = A[:2]
xor = 0
for x in A[2:]:
    xor ^= x

INF = 10**13

@lru_cache(None)
def F(a, b, xor):
    if (a & 1) ^ (b & 1) != (xor & 1):
        return INF
    if xor == 0:
        return INF if a < b else (a - b) // 2
    # 1の位を放置
    x = 2 * F(a // 2, b // 2, xor // 2)
    # 1の位を移動
    y = 2 * F((a - 1) // 2, (b + 1) // 2, xor // 2) + 1
    x = min(x, y)
    if x >= INF:
        x = INF
    return x

x = F(a, b, xor)
if x >= a:
    x = -1
print(x)

Submission Info

Submission Time
Task F - Unfair Nim
User maspy
Language Python (3.8.2)
Score 600
Code Size 693 Byte
Status
Exec Time 36 ms
Memory 9640 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt
All 600 / 600 hand_01.txt, hand_02.txt, n2_01.txt, n2_02.txt, n2_03.txt, n2_04.txt, n3_01.txt, n3_02.txt, n3_03.txt, n3_04.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt
Case Name Status Exec Time Memory
hand_01.txt 26 ms 9436 KB
hand_02.txt 26 ms 9472 KB
n2_01.txt 22 ms 9476 KB
n2_02.txt 23 ms 9560 KB
n2_03.txt 33 ms 9424 KB
n2_04.txt 35 ms 9420 KB
n3_01.txt 34 ms 9544 KB
n3_02.txt 29 ms 9312 KB
n3_03.txt 32 ms 9420 KB
n3_04.txt 30 ms 9624 KB
random_01.txt 31 ms 9640 KB
random_02.txt 23 ms 9440 KB
random_03.txt 30 ms 9508 KB
random_04.txt 22 ms 9496 KB
random_05.txt 31 ms 9456 KB
random_06.txt 26 ms 9640 KB
random_07.txt 27 ms 9336 KB
random_08.txt 25 ms 9324 KB
sample_01.txt 34 ms 9592 KB
sample_02.txt 36 ms 9604 KB
sample_03.txt 26 ms 9420 KB
sample_04.txt 24 ms 9476 KB
sample_05.txt 31 ms 9340 KB