提出 #11051429


ソースコード 拡げる

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

提出情報

提出日時
問題 B - 123 Triangle
ユーザ maspy
言語 PyPy3 (2.4.0)
得点 700
コード長 774 Byte
結果
実行時間 476 ms
メモリ 137112 KB

ジャッジ結果

セット名 得点 / 配点 テストケース
Sample 0 / 0 0_000.txt, 0_001.txt
All 700 / 700 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
ケース名 結果 実行時間 メモリ
0_000.txt 163 ms 38256 KB
0_001.txt 163 ms 38256 KB
1_002.txt 163 ms 38256 KB
1_003.txt 163 ms 38256 KB
1_004.txt 163 ms 38256 KB
1_005.txt 163 ms 38256 KB
1_006.txt 168 ms 38256 KB
1_007.txt 166 ms 38256 KB
1_008.txt 476 ms 137112 KB
1_009.txt 462 ms 136088 KB
1_010.txt 462 ms 136088 KB
1_011.txt 458 ms 136088 KB
1_012.txt 468 ms 136088 KB
1_013.txt 452 ms 136088 KB
1_014.txt 458 ms 136088 KB
1_015.txt 454 ms 136088 KB
1_016.txt 327 ms 115268 KB
1_017.txt 340 ms 115276 KB
1_018.txt 340 ms 115276 KB
1_019.txt 332 ms 117268 KB
1_020.txt 333 ms 115148 KB
1_021.txt 333 ms 115148 KB
1_022.txt 322 ms 119532 KB
1_023.txt 334 ms 117268 KB
1_024.txt 348 ms 115276 KB
1_025.txt 322 ms 115276 KB
1_026.txt 332 ms 115404 KB
1_027.txt 329 ms 117316 KB
1_028.txt 317 ms 119500 KB
1_029.txt 330 ms 115148 KB
1_030.txt 315 ms 119476 KB
1_031.txt 322 ms 117396 KB
1_032.txt 254 ms 75464 KB
1_033.txt 256 ms 73928 KB
1_034.txt 259 ms 73928 KB
1_035.txt 250 ms 73800 KB
1_036.txt 268 ms 73672 KB
1_037.txt 257 ms 73544 KB
1_038.txt 257 ms 73544 KB
1_039.txt 257 ms 73800 KB
1_040.txt 463 ms 136088 KB
1_041.txt 463 ms 136088 KB
1_042.txt 338 ms 119500 KB
1_043.txt 332 ms 119500 KB
1_044.txt 324 ms 119500 KB
1_045.txt 321 ms 119500 KB
1_046.txt 460 ms 136168 KB
1_047.txt 460 ms 135996 KB