Submission #11051429


Source Code Expand

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

N = int(readline())
A = list(map(int, read().decode().rstrip()))

U = N + 10
fact_ord = [0] * U
for n in range(1,U):
    fact_ord[n] = fact_ord[n//2] + (n//2)

def solve_01(A):
    ret = 0
    N = len(A) - 1
    comb_ord = [fact_ord[N] - fact_ord[i] - fact_ord[N-i] for i in range(N+1)]
    return sum(x * (y==0) for x,y in zip(A, comb_ord)) % 2

def solve(A):
    if len(A) == 1:
        return A[0]
    A = [abs(x - y) for x,y in zip(A, A[1:])]
    if all(x != 1 for x in A):
        B = [x // 2 for x in A]
        return 2 * solve_01(B)
    # 1 が存在
    A = [x % 2 for x in A]
    return solve_01(A)

print(solve(A))

Submission Info

Submission Time
Task B - 123 Triangle
User maspy
Language PyPy3 (2.4.0)
Score 700
Code Size 774 Byte
Status AC
Exec Time 476 ms
Memory 137112 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
AC × 2
AC × 48
Set Name Test Cases
Sample 0_000.txt, 0_001.txt
All 0_000.txt, 0_001.txt, 1_002.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 1_026.txt, 1_027.txt, 1_028.txt, 1_029.txt, 1_030.txt, 1_031.txt, 1_032.txt, 1_033.txt, 1_034.txt, 1_035.txt, 1_036.txt, 1_037.txt, 1_038.txt, 1_039.txt, 1_040.txt, 1_041.txt, 1_042.txt, 1_043.txt, 1_044.txt, 1_045.txt, 1_046.txt, 1_047.txt
Case Name Status Exec Time Memory
0_000.txt AC 163 ms 38256 KB
0_001.txt AC 163 ms 38256 KB
1_002.txt AC 163 ms 38256 KB
1_003.txt AC 163 ms 38256 KB
1_004.txt AC 163 ms 38256 KB
1_005.txt AC 163 ms 38256 KB
1_006.txt AC 168 ms 38256 KB
1_007.txt AC 166 ms 38256 KB
1_008.txt AC 476 ms 137112 KB
1_009.txt AC 462 ms 136088 KB
1_010.txt AC 462 ms 136088 KB
1_011.txt AC 458 ms 136088 KB
1_012.txt AC 468 ms 136088 KB
1_013.txt AC 452 ms 136088 KB
1_014.txt AC 458 ms 136088 KB
1_015.txt AC 454 ms 136088 KB
1_016.txt AC 327 ms 115268 KB
1_017.txt AC 340 ms 115276 KB
1_018.txt AC 340 ms 115276 KB
1_019.txt AC 332 ms 117268 KB
1_020.txt AC 333 ms 115148 KB
1_021.txt AC 333 ms 115148 KB
1_022.txt AC 322 ms 119532 KB
1_023.txt AC 334 ms 117268 KB
1_024.txt AC 348 ms 115276 KB
1_025.txt AC 322 ms 115276 KB
1_026.txt AC 332 ms 115404 KB
1_027.txt AC 329 ms 117316 KB
1_028.txt AC 317 ms 119500 KB
1_029.txt AC 330 ms 115148 KB
1_030.txt AC 315 ms 119476 KB
1_031.txt AC 322 ms 117396 KB
1_032.txt AC 254 ms 75464 KB
1_033.txt AC 256 ms 73928 KB
1_034.txt AC 259 ms 73928 KB
1_035.txt AC 250 ms 73800 KB
1_036.txt AC 268 ms 73672 KB
1_037.txt AC 257 ms 73544 KB
1_038.txt AC 257 ms 73544 KB
1_039.txt AC 257 ms 73800 KB
1_040.txt AC 463 ms 136088 KB
1_041.txt AC 463 ms 136088 KB
1_042.txt AC 338 ms 119500 KB
1_043.txt AC 332 ms 119500 KB
1_044.txt AC 324 ms 119500 KB
1_045.txt AC 321 ms 119500 KB
1_046.txt AC 460 ms 136168 KB
1_047.txt AC 460 ms 135996 KB