Submission #17669216


Source Code Expand

Copy
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

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

B = 60

@njit((i8, b1[:]), cache=True)
def main(N, nums):
    """まずは愚直解。閉区間で持つ。
    A = np.zeros((N, N), np.bool_)
    n = 0
    for i in range(1, N):
        for j in range(i):
            A[i, j], n = nums[n], n + 1
            A[j, i] = not A[i, j]
    dp_1 = np.zeros((N, N), np.bool_)  # [l,r] で l が勝てる
    dp_2 = np.zeros((N, N), np.bool_)  # [l,r] で r が勝てる
    for n in range(N):
        dp_1[n, n] = dp_2[n, n] = 1
    for size in range(1, N + 1):
        for L in range(N - size):
            R = L + size
            ok = False
            for M in range(L + 1, R + 1):
                ok |= A[L, M] and dp_2[L + 1, M] and dp_1[M, R]
            dp_1[L, R] = ok

            ok = False
            for M in range(L, R):
                ok |= A[R, M] and dp_1[M, R - 1] and dp_2[L, M]
            dp_2[L, R] = ok
    ans = 0
    for M in range(0, N):
        ans += dp_1[M, N - 1] and dp_2[0, M]
    """
    """愚直解 2
    A = np.zeros((N, N), np.bool_)
    n = 0
    for i in range(1, N):
        for j in range(i):
            A[i, j], n = nums[n], n + 1
            A[j, i] = not A[i, j]
    dp_1 = np.zeros((N, N), np.bool_)  # dp_1[r,l] := [l,r] で l が勝てる
    dp_2 = np.zeros((N, N), np.bool_)  # [l,r] で r が勝てる
    for n in range(N):
        dp_1[n, n] = dp_2[n, n] = 1
    for size in range(1, N + 1):
        for L in range(N - size):
            R = L + size
            ok = False
            for M in range(L + 1, R + 1):
                ok |= A[L, M] and dp_2[L + 1, M] and dp_1[R, M]
            dp_1[R, L] = ok

            ok = False
            for M in range(L, R):
                ok |= A[R, M] and dp_1[R - 1, M] and dp_2[L, M]
            dp_2[L, R] = ok
    ans = 0
    for M in range(0, N):
        ans += dp_1[N - 1, M] and dp_2[0, M]"""
    """愚直解 2 を bit 並列化"""
    K = N // B
    A = np.zeros((N, K + 1), np.int64)
    n = 0
    for i in range(1, N):
        for j in range(i):
            x, n = nums[n], n + 1
            if x:
                A[i, j // B] |= 1 << (j % B)
            else:
                A[j, i // B] |= 1 << (i % B)
    dp_1 = np.zeros((N, K + 1), np.int64)  # dp_1[r,l] := [l,r] で l が勝てる
    dp_2 = np.zeros((N, K + 1), np.int64)  # [l,r] で r が勝てる
    for n in range(N):
        dp_1[n, n // B] = 1 << (n % B)
        dp_2[n, n // B] = 1 << (n % B)

    for size in range(1, N + 1):
        for L in range(N - size):
            R = L + size
            ok = np.any((A[L] & dp_2[L + 1] & dp_1[R]) > 0)
            if ok:
                dp_1[R, L // B] |= 1 << (L % B)

            ok = np.any((A[R] & dp_1[R - 1] & dp_2[L]) > 0)
            if ok:
                dp_2[L, R // B] |= 1 << (R % B)
    winner = dp_1[N - 1] & dp_2[0]
    ans = 0
    for x in winner:
        for _ in range(B):
            ans += x & 1
            x >>= 1
    return ans

N = int(readline())
S = read().rstrip().replace(b'0', b'0 ').replace(b'1', b'1 ')
nums = np.fromstring(S, dtype=np.bool_, sep=' ')

print(main(N, nums))

Submission Info

Submission Time
Task F - Random Tournament
User maspy
Language Python (3.8.2)
Score 1000
Code Size 3362 Byte
Status AC
Exec Time 1305 ms
Memory 114712 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1000 / 1000
Status
AC × 2
AC × 76
Set Name Test Cases
Sample example0.txt, example1.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, 043.txt, 044.txt, 045.txt, 046.txt, 047.txt, 048.txt, 049.txt, 050.txt, 051.txt, 052.txt, 053.txt, 054.txt, 055.txt, 056.txt, 057.txt, 058.txt, 059.txt, 060.txt, 061.txt, 062.txt, 063.txt, 064.txt, 065.txt, 066.txt, 067.txt, 068.txt, 069.txt, 070.txt, 071.txt, 072.txt, 073.txt, example0.txt, example1.txt
Case Name Status Exec Time Memory
000.txt AC 536 ms 106616 KB
001.txt AC 533 ms 107404 KB
002.txt AC 512 ms 106636 KB
003.txt AC 511 ms 106608 KB
004.txt AC 510 ms 106496 KB
005.txt AC 542 ms 106616 KB
006.txt AC 514 ms 106552 KB
007.txt AC 518 ms 106552 KB
008.txt AC 517 ms 107264 KB
009.txt AC 513 ms 106088 KB
010.txt AC 508 ms 106892 KB
011.txt AC 519 ms 106456 KB
012.txt AC 515 ms 106664 KB
013.txt AC 522 ms 106168 KB
014.txt AC 516 ms 106604 KB
015.txt AC 517 ms 107280 KB
016.txt AC 517 ms 106596 KB
017.txt AC 518 ms 106828 KB
018.txt AC 507 ms 106604 KB
019.txt AC 520 ms 106896 KB
020.txt AC 514 ms 106156 KB
021.txt AC 507 ms 107464 KB
022.txt AC 508 ms 106692 KB
023.txt AC 513 ms 106080 KB
024.txt AC 516 ms 106612 KB
025.txt AC 507 ms 106600 KB
026.txt AC 544 ms 106196 KB
027.txt AC 514 ms 106552 KB
028.txt AC 519 ms 107216 KB
029.txt AC 518 ms 106600 KB
030.txt AC 523 ms 106764 KB
031.txt AC 524 ms 107328 KB
032.txt AC 515 ms 106600 KB
033.txt AC 514 ms 106640 KB
034.txt AC 520 ms 107404 KB
035.txt AC 517 ms 106148 KB
036.txt AC 513 ms 107264 KB
037.txt AC 514 ms 106836 KB
038.txt AC 516 ms 106592 KB
039.txt AC 514 ms 107312 KB
040.txt AC 517 ms 106796 KB
041.txt AC 516 ms 106588 KB
042.txt AC 516 ms 107440 KB
043.txt AC 516 ms 106664 KB
044.txt AC 507 ms 106544 KB
045.txt AC 518 ms 107324 KB
046.txt AC 513 ms 106088 KB
047.txt AC 508 ms 106436 KB
048.txt AC 512 ms 107372 KB
049.txt AC 512 ms 106524 KB
050.txt AC 1245 ms 114188 KB
051.txt AC 1260 ms 113384 KB
052.txt AC 1289 ms 114572 KB
053.txt AC 1263 ms 113380 KB
054.txt AC 1266 ms 114672 KB
055.txt AC 1258 ms 114100 KB
056.txt AC 1271 ms 114544 KB
057.txt AC 1259 ms 114120 KB
058.txt AC 1280 ms 113804 KB
059.txt AC 1265 ms 114624 KB
060.txt AC 1262 ms 113892 KB
061.txt AC 1267 ms 113352 KB
062.txt AC 1291 ms 114072 KB
063.txt AC 1305 ms 114092 KB
064.txt AC 1295 ms 113992 KB
065.txt AC 1285 ms 114524 KB
066.txt AC 1284 ms 114600 KB
067.txt AC 1262 ms 114100 KB
068.txt AC 1296 ms 114712 KB
069.txt AC 1294 ms 114116 KB
070.txt AC 1268 ms 114160 KB
071.txt AC 1260 ms 114092 KB
072.txt AC 1261 ms 113904 KB
073.txt AC 1288 ms 113896 KB
example0.txt AC 524 ms 106440 KB
example1.txt AC 527 ms 106344 KB