Problem p02609 (python)

Fixed submission:
def popcount(n):
    return bin(n).count("1")


def f(n):
    if n == 0:
        return 0
    return 1 + f(n % popcount(n))


N = int(input())
X = input()

c = X.count('1')
t1 = [0] * N
t1[0] = 1 % (c + 1)
for i in range(1, N):
    t1[i] = (t1[i - 1] << 1) % (c + 1)
x1 = 0
for i in range(N):
    if X[i] == '0':
        continue
    x1 += t1[N - 1 - i]

if c - 1 != 0:
    t2 = [0] * N
    t2[0] = 1 % (c - 1)
    for i in range(1, N):
        t2[i] = (t2[i - 1] << 1) % (c - 1)
    x2 = 0
    for i in range(N):
        if X[i] == '0':
            continue
        x2 += t2[N - 1 - i]

result = []
for i in range(N):
    if X[i] == '0':
        n = (x1 + t1[N - 1 - i]) % (c + 1)
    elif X[i] == '1':
        if c - 1 == 0:
            result.append(0)
            continue
        n = (x2 - t2[N - 1 - i]) % (c - 1)
    result.append(1 + f(n))
print(*result, sep='\n')

Buggy submission (verdict: Runtime Error):
from sys import setrecursionlimit
setrecursionlimit(10 ** 6)


def popcount(n):
    return bin(n).count("1")

cache = [-1] * (2 * 10 ** 5 + 1)


def f(n):
    if cache[n] != -1:
        return cache[n]
    if n == 0:
        return 0
    t = n % popcount(n)
    if t == 0:
        cache[n] = 1
    else:
        cache[n] = f(t) + 1
    return cache[n]

def g(n, m):
    if n < 60:
        return (1 << n) % m
    else:
        t = n // 2
        return g(t, m) * g(n - t, m) % m


N = int(input())
X = input()

c = X.count('1')
t1 = [0] * N
t2 = [0] * N
for i in range(N):
    n = N - 1 - i
    t1[i] = g(n, c - 1)
    t2[i] = g(n, c + 1)

x1, x2 = 0, 0
for i in range(N):
    if X[i] == '1':
        x1 += t1[i]
        x2 += t2[i]

result = []
for i in range(N):
    if X[i] == '1':
        n = x1 - t1[i]
        n %= c - 1
    elif X[i] == '0':
        n = x2 + t2[i]
        n %= c + 1
    result.append(f(n) + 1)
print(*result, sep='\n')

Buggy submission (verdict: Runtime Error):
from sys import setrecursionlimit
setrecursionlimit(10 ** 6)


def popcount(n):
    return bin(n).count("1")

cache = [-1] * (2 * 10 ** 5 + 1)


def f(n):
    if cache[n] != -1:
        return cache[n]
    return f(n % popcount(n)) + 1

def g(n, m):
    if n < 60:
        return (1 << n) % m
    else:
        t = n // 2
        return g(t, m) * g(n - t, m) % m


N = int(input())
X = input()

c = X.count('1')
t1 = [0] * N
t2 = [0] * N
for i in range(N):
    n = N - 1 - i
    t1[i] = g(n, c - 1)
    t2[i] = g(n, c + 1)

x1, x2 = 0, 0
for i in range(N):
    if X[i] == '1':
        x1 += t1[i]
        x2 += t2[i]

result = []
for i in range(N):
    if X[i] == '1':
        n = x1 - t1[i]
        n %= c - 1
    elif X[i] == '0':
        n = x2 + t2[i]
        n %= c + 1
    result.append(f(n) + 1)
print(*result, sep='\n')

Buggy submission (verdict: Runtime Error):
from sys import setrecursionlimit
setrecursionlimit(10 ** 6)


def popcount(n):
    return bin(n).count("1")

cache = [-1] * (2 * 10 ** 5 + 1)


def f(n):
    if cache[n] != -1:
        return cache[n]
    return f(n % popcount(n)) + 1

def g(n, m):
    if n < 60:
        return (1 << n) % m
    else:
        t = n // 2
        return g(t, m) * g(n - t, m) % m


N = int(input())
X = input()

c = X.count('1')
t1 = [0] * N
t2 = [0] * N
for i in range(N):
    n = N - 1 - i
    t1[i] = g(n, c - 1)
    t2[i] = g(n, c + 1)

x1, x2 = 0, 0
for i in range(N):
    if X[i] == '1':
        x1 += t1[i]
        x2 += t2[i]

result = []
for i in range(N):
    if X[i] == '1':
        n = x1 - t1[i]
        n %= c - 1
    elif X[i] == '0':
        n = x2 + t2[i]
        n %= c + 1
    result.append(f(n) + 1)
print(*result, sep='\n')

Buggy submission (verdict: Runtime Error):
from sys import setrecursionlimit
setrecursionlimit(10 ** 6)


def popcount(n):
    return bin(n).count("1")

cache = [-1] * (2 * 10 ** 5 + 1)


def f(n):
    if cache[X] != -1:
        return cache[X]
    return f(n % popcount(n)) + 1

def g(n, m):
    if n < 60:
        return (1 << n) % m
    else:
        t = n // 2
        return g(t, m) * g(n - t, m) % m


N = int(input())
X = input()

c = X.count('1')
t1 = [0] * N
t2 = [0] * N
for i in range(N):
    n = N - 1 - i
    t1[i] = g(n, c - 1)
    t2[i] = g(n, c + 1)

x1, x2 = 0, 0
for i in range(N):
    if X[i] == '1':
        x1 += t1[i]
        x2 += t2[i]

result = []
for i in range(N):
    if X[i] == '1':
        n = x1 - t1[i]
        n %= c - 1
    elif X[i] == '0':
        n = x2 + t2[i]
        n %= c + 1
    result.append(f(n) + 1)
print(*result, sep='\n')

Buggy submission (verdict: Runtime Error):
from sys import setrecursionlimit
setrecursionlimit(10 ** 6)


def popcount(n):
    return bin(n).count("1")

def g(n, m):
    if n < 60:
        return (1 << n) % m
    else:
        t = n // 2
        return g(t, m) * g(n - t, m) % m


N = int(input())
X = input()

c = X.count('1')
t1 = [0] * N
t2 = [0] * N
for i in range(N):
    n = N - 1 - i
    t1[i] = g(n, c - 1)
    t2[i] = g(n, c + 1)

x1, x2 = 0, 0
for i in range(N):
    if X[i] == '1':
        x1 += t1[i]
        x2 += t2[i]

result = []
for i in range(N):
    if X[i] == '1':
        n = x1 - t1[i]
        n %= c - 1
    elif X[i] == '0':
        n = x2 + t2[i]
        n %= c + 1
    t = 1
    while n != 0:
        n %= popcount(n)
        t += 1
    result.append(t)
print(*result, sep='\n')

Buggy submission (verdict: Runtime Error):
from sys import setrecursionlimit
setrecursionlimit(10 ** 6)


def popcount(n):
    return bin(n).count("1")

def g(n, m):
    if n < 60:
        return (1 << n) % m
    else:
        t = n // 2
        return g(t, m) * g(n - t, m) % m


N = int(input())
X = input()

c = X.count('1')
t1 = [0] * N
t2 = [0] * N
for i in range(N):
    n = N - 1 - i
    t1[i] = g(n, c - 1)
    t2[i] = g(n, c + 1)

x1, x2 = 0, 0
for i in range(N):
    if X[i] == '1':
        x1 += t1[i]
        x2 += t2[i]

result = []
for i in range(N):
    if X[i] == '1':
        n = x1 - t1[i]
        n %= c - 1
    elif X[i] == '0':
        n = x2 + t2[i]
        n %= c + 1
    t = 1
    while n != 0:
        n %= popcount(n)
        t += 1
    result.append(t)
print(*result, sep='\n')