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

Submission #15177277

Source Code Expand

Copy
```import sys
import numpy as np
import numba
from numba import njit
i8 = numba.int64

@njit((i8, ), cache=True)
def popcount(n):
ret = 0
while n:
ret += n & 1
n >>= 1
return ret

@njit((i8, ), cache=True)
def f(n):
t = 0
while n:
t += 1
n %= popcount(n)
return t

@njit((i8[:], ), cache=True)
def main(X):
N = len(X)
popX = X.sum()
MOD1 = popX + 1
MOD2 = popX - 1
if popX == 1:
MOD2 = 1
pow1 = np.ones_like(X)
pow2 = np.ones_like(X)
for n in range(1, N):
pow1[n] = 2 * pow1[n - 1] % MOD1
pow2[n] = 2 * pow2[n - 1] % MOD2

X1, X2 = 0, 0
for x in X:
X1 = (2 * X1 + x) % MOD1
X2 = (2 * X2 + x) % MOD2

ans = np.empty(N, np.int64)
for i in range(N):
x = X[N - 1 - i]
if x == 0:
nxt = (X1 + pow1[i]) % (popX + 1)
ans[i] = 1 + f(nxt)
elif x == 1:
if popX == 1:
ans[i] = 0
else:
nxt = (X2 - pow2[i]) % (popX - 1)
ans[i] = 1 + f(nxt)
return ans[::-1]

X = np.array(list(read().rstrip()), np.int64) - ord('0')
ans = main(X)
print('\n'.join(map(str, ans.tolist())))```

#### Submission Info

Submission Time 2020-07-11 22:26:50+0900 D - Anything Goes to Zero maspy Python (3.8.2) 400 1411 Byte AC 610 ms 127520 KB

#### Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt
All 400 / 400 hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, hand_06.txt, hand_07.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, sample_01.txt, sample_02.txt
Case Name Status Exec Time Memory
hand_01.txt 568 ms 106796 KB
hand_02.txt 548 ms 106192 KB
hand_03.txt 571 ms 115648 KB
hand_04.txt 545 ms 106992 KB
hand_05.txt 596 ms 127520 KB
hand_06.txt 599 ms 126488 KB
hand_07.txt 605 ms 126876 KB
random_01.txt 608 ms 126436 KB
random_02.txt 604 ms 126864 KB
random_03.txt 607 ms 127504 KB
random_04.txt 610 ms 126900 KB
random_05.txt 594 ms 122192 KB
random_06.txt 544 ms 106156 KB
random_07.txt 595 ms 119088 KB
random_08.txt 561 ms 111336 KB
random_09.txt 607 ms 126640 KB
random_10.txt 549 ms 110220 KB
random_11.txt 598 ms 122284 KB
random_12.txt 570 ms 117476 KB
sample_01.txt 542 ms 106124 KB
sample_02.txt 540 ms 105632 KB