Contest Duration: - (local time) (100 minutes) Back to Home

Submission #17632953

Source Code Expand

Copy
```"""TLE?"""
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

MAX = 1 << 24

@njit
def precompute(A):
N = len(A)
dp = np.zeros(MAX, np.int64)
for i in range(N):
a = A[i]
mod = 0
for d in range(MAX):
# d 日目の状況
if mod < a:
dp[d] |= 1 << i
mod += 1
if mod >= a + a:
mod -= a + a
popcount = np.zeros(1 << N, np.int64)
for n in range(1 << N):
popcount[n] = popcount[n // 2] + (n % 2)
return dp, popcount

@njit
def test(A, popcount, K, D):
# D 日間集計して、Hall conditionを満たすかどうか確認する
full = (1 << N) - 1
dp = np.zeros(1 << N, np.int64)
for d in range(D):
s = A[d]
dp[full ^ s] += 1
# subset zeta
for n in range(N):
for s in range(1 << N):
t = s ^ 1 << n
if s < t:
continue
dp[t] += dp[s]
return np.all((D - dp - popcount * K) >= 0)

def main(A, K):
B, popcount = precompute(A)
l, r = 0, MAX
while l + 1 < r:
x = (l + r) // 2
if test(B, popcount, K, x):
r = x
else:
l = x
return r

print(main(A, K))```

Submission Info

Submission Time 2020-10-24 22:21:23+0900 E - Medals maspy Python (3.8.2) 700 1704 Byte AC 1899 ms 249932 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
 AC × 3
 AC × 40
Set Name Test Cases
Sample 00_sample_01, 00_sample_02, 00_sample_03
All 00_sample_01, 00_sample_02, 00_sample_03, 10_small_01, 10_small_02, 10_small_03, 10_small_04, 10_small_05, 10_small_06, 10_small_07, 10_small_08, 10_small_09, 10_small_10, 20_random_01, 20_random_02, 20_random_03, 20_random_04, 20_random_05, 20_random_06, 20_random_07, 20_random_08, 20_random_09, 20_random_10, 30_max_01, 30_max_02, 30_max_03, 30_max_04, 30_max_05, 31_max_01, 31_max_02, big_00, big_01, big_02, big_03, big_04, sml_00, sml_01, sml_02, sml_03, sml_04
Case Name Status Exec Time Memory
00_sample_01 AC 1899 ms 244600 KB
00_sample_02 AC 1276 ms 246292 KB
00_sample_03 AC 1120 ms 244468 KB
10_small_01 AC 1110 ms 244604 KB
10_small_02 AC 1118 ms 244504 KB
10_small_03 AC 1104 ms 244524 KB
10_small_04 AC 1118 ms 244676 KB
10_small_05 AC 1112 ms 245132 KB
10_small_06 AC 1113 ms 245344 KB
10_small_07 AC 1178 ms 244496 KB
10_small_08 AC 1202 ms 245468 KB
10_small_09 AC 1137 ms 244832 KB
10_small_10 AC 1168 ms 244776 KB
20_random_01 AC 1391 ms 245868 KB
20_random_02 AC 1387 ms 246896 KB
20_random_03 AC 1391 ms 245896 KB
20_random_04 AC 1111 ms 244648 KB
20_random_05 AC 1538 ms 249448 KB
20_random_06 AC 1151 ms 244832 KB
20_random_07 AC 1241 ms 246052 KB
20_random_08 AC 1113 ms 245164 KB
20_random_09 AC 1062 ms 245088 KB
20_random_10 AC 1359 ms 246860 KB
30_max_01 AC 1483 ms 247024 KB
30_max_02 AC 1586 ms 249252 KB
30_max_03 AC 1618 ms 249352 KB
30_max_04 AC 1490 ms 247868 KB
30_max_05 AC 1616 ms 249344 KB
31_max_01 AC 1626 ms 249356 KB
31_max_02 AC 1618 ms 249348 KB
big_00 AC 1496 ms 249204 KB
big_01 AC 1509 ms 249456 KB
big_02 AC 1530 ms 249160 KB
big_03 AC 1549 ms 249932 KB
big_04 AC 1536 ms 249136 KB
sml_00 AC 1208 ms 245276 KB
sml_01 AC 1183 ms 246180 KB
sml_02 AC 1209 ms 246020 KB
sml_03 AC 1207 ms 245624 KB
sml_04 AC 1198 ms 245544 KB