Submission #15177277


Source Code Expand

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

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

@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]

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

Submission Info

Submission Time
Task D - Anything Goes to Zero
User maspy
Language Python (3.8.2)
Score 400
Code Size 1411 Byte
Status
Exec Time 610 ms
Memory 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