Submission #17669024


Source Code Expand

Copy
"""TLE"""
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

@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]
    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 0
Code Size 1359 Byte
Status TLE
Exec Time 2760 ms
Memory 124308 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1000
Status
AC × 2
AC × 52
TLE × 24
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 550 ms 107080 KB
001.txt AC 551 ms 106224 KB
002.txt AC 542 ms 106224 KB
003.txt AC 544 ms 107032 KB
004.txt AC 546 ms 106620 KB
005.txt AC 506 ms 106240 KB
006.txt AC 513 ms 106588 KB
007.txt AC 528 ms 106216 KB
008.txt AC 535 ms 106276 KB
009.txt AC 538 ms 105784 KB
010.txt AC 537 ms 106328 KB
011.txt AC 532 ms 106352 KB
012.txt AC 536 ms 106380 KB
013.txt AC 527 ms 106388 KB
014.txt AC 537 ms 106324 KB
015.txt AC 536 ms 107028 KB
016.txt AC 530 ms 106552 KB
017.txt AC 533 ms 107080 KB
018.txt AC 524 ms 107004 KB
019.txt AC 532 ms 106544 KB
020.txt AC 532 ms 107088 KB
021.txt AC 532 ms 106592 KB
022.txt AC 521 ms 106324 KB
023.txt AC 519 ms 105828 KB
024.txt AC 520 ms 106584 KB
025.txt AC 519 ms 105896 KB
026.txt AC 523 ms 106552 KB
027.txt AC 528 ms 106328 KB
028.txt AC 525 ms 106336 KB
029.txt AC 532 ms 106328 KB
030.txt AC 529 ms 106288 KB
031.txt AC 522 ms 106388 KB
032.txt AC 526 ms 106620 KB
033.txt AC 534 ms 107016 KB
034.txt AC 534 ms 106340 KB
035.txt AC 517 ms 105904 KB
036.txt AC 516 ms 106308 KB
037.txt AC 526 ms 106324 KB
038.txt AC 517 ms 107004 KB
039.txt AC 522 ms 107092 KB
040.txt AC 525 ms 105904 KB
041.txt AC 526 ms 107148 KB
042.txt AC 527 ms 106580 KB
043.txt AC 525 ms 107008 KB
044.txt AC 522 ms 105912 KB
045.txt AC 529 ms 106376 KB
046.txt AC 532 ms 106344 KB
047.txt AC 533 ms 106612 KB
048.txt AC 533 ms 106544 KB
049.txt AC 507 ms 107128 KB
050.txt TLE 2760 ms 123708 KB
051.txt TLE 2760 ms 123356 KB
052.txt TLE 2760 ms 124308 KB
053.txt TLE 2760 ms 123476 KB
054.txt TLE 2760 ms 123740 KB
055.txt TLE 2760 ms 124148 KB
056.txt TLE 2760 ms 124152 KB
057.txt TLE 2760 ms 123512 KB
058.txt TLE 2760 ms 124216 KB
059.txt TLE 2760 ms 123700 KB
060.txt TLE 2760 ms 123708 KB
061.txt TLE 2760 ms 123068 KB
062.txt TLE 2760 ms 123476 KB
063.txt TLE 2760 ms 123480 KB
064.txt TLE 2760 ms 123728 KB
065.txt TLE 2760 ms 123652 KB
066.txt TLE 2760 ms 123692 KB
067.txt TLE 2760 ms 124296 KB
068.txt TLE 2760 ms 124152 KB
069.txt TLE 2760 ms 124144 KB
070.txt TLE 2760 ms 123044 KB
071.txt TLE 2760 ms 123052 KB
072.txt TLE 2760 ms 123044 KB
073.txt TLE 2760 ms 123472 KB
example0.txt AC 524 ms 106588 KB
example1.txt AC 489 ms 106700 KB