Problem p02609 (python)

Fixed submission:
from functools import lru_cache


def popcnt(x):
    return bin(x).count("1")


@lru_cache(maxsize=None)
def rec(n):
    if n == 0:
        return 0
    else:
        return rec(n % popcnt(n)) + 1


ret = [rec(x) for x in range(2 * 10**5 + 1)]


n = int(input())
arr = input()

ALL_ARR = int(arr, 2)

cnt = popcnt(int(arr, 2))
init_big = ALL_ARR % (cnt + 1)
if cnt == 1:
    init_small = 0
else:
    init_small = ALL_ARR % (cnt - 1)


li = [0] * n
for i in range(n):
    if arr[i] == "0":
        li[i] = (init_big + pow(2, n - i - 1, cnt + 1)) % (cnt + 1)
    elif ALL_ARR - (1 << (n - i - 1)) == 0 or cnt - 1 == 0:
        li[i] = "flg"
    else:
        li[i] = (init_small - pow(2, n - i - 1, cnt - 1)) % (cnt - 1)


ans = []

for x in li:
    if x == "flg":
        ans.append(0)
    else:
        ans.append(ret[x] + 1)

print(*ans, sep="\n")

Buggy submission (verdict: Runtime Error):
from functools import lru_cache


def popcnt(x):
    return bin(x).count("1")


@lru_cache(maxsize=None)
def rec(n):
    if n == 0:
        return 0
    else:
        return rec(n % popcnt(n)) + 1


n = int(input())
x = int(input(), 2)

# 事前計算
cnt = popcnt(arr)
init_big = x % (cnt + 1)
if cnt == 1:
    init_small = 0
else:
    init_small = x % (cnt - 1)

# 差分計算
result = []
for i in range(n):
    if not (x >> i) & 1:
        result.append((init_big + pow(2, i, cnt + 1)) % (cnt + 1))
    elif arr == 1 << i or cnt - 1 == 0:
        result.append(0)
    else:
        result.append((init_small - pow(2, i, cnt - 1)) % (cnt - 1))

ans = []
for x in result[::-1]:
    ans.append(rec(x) + 1)

print(*ans, sep="\n")

Buggy submission (verdict: Runtime Error):
from functools import lru_cache


def popcnt(x):
    return bin(x).count("1")


@lru_cache(maxsize=None)
def rec(n):
    if n == 0:
        return 0
    else:
        return rec(n % popcnt(n)) + 1


n = int(input())
arr = input()

cnt = popcnt(int(arr, 2))
init_big = int(arr, 2) % (cnt + 1)
if cnt == 1:
    init_small = 0
else:
    init_small = int(arr, 2) % (cnt - 1)

li = []
for i in range(n):
    if arr[i] == "0":
        li.append((init_big + (1 << (n - i - 1))) % (cnt + 1))
    else:
        li.append((init_small - (1 << (n - i - 1))) % (cnt - 1))


ans = []

for x in li:
    ans.append(rec(x) + 1)

for i in range(n):
    x = arr[:i] + str(1 ^ int(arr[i])) + arr[i + 1:]
    if int(x, 2) == 0:
        ans[i] = 0

print(*ans, sep="\n")

Buggy submission (verdict: Runtime Error):
from functools import lru_cache


def popcnt(x):
    return bin(x).count("1")


@lru_cache(maxsize=None)
def rec(n):
    if n == 0:
        return 0
    else:
        return rec(n % popcnt(n)) + 1


n = int(input())
arr = input()

cnt = popcnt(int(arr, 2))
init_big = int(arr, 2) % (cnt + 1)
init_small = int(arr, 2) % (cnt - 1)

li = []
for i in range(n):
    if arr[i] == "0":
        li.append((init_big + (1 << (n - i - 1))) % (cnt + 1))
    else:
        li.append((init_small - (1 << (n - i - 1))) % (cnt - 1))


ans = []

for x in li:
    ans.append(rec(x) + 1)

if int(arr, 2) == 1:
    ans[-1] = 0

print(*ans, sep="\n")

Buggy submission (verdict: Runtime Error):
from functools import lru_cache


def popcnt(x):
    return bin(x).count("1")


@lru_cache(maxsize=None)
def rec(n):
    if n == 0:
        return 0
    else:
        return rec(n % popcnt(n)) + 1


n = int(input())
arr = input()

cnt = popcnt(int(arr, 2))
init_big = int(arr, 2) % (cnt + 1)
init_small = int(arr, 2) % (cnt - 1)

li = []
for i in range(n):
    if arr[i] == "0":
        li.append((init_big + (1 << (n - i - 1))) % (cnt + 1))
    else:
        li.append((init_small - (1 << (n - i - 1))) % (cnt - 1))


ans = []

for x in li:
    ans.append(rec(x) + 1)

if int(arr, 2) == 1:
    ans[-1] = 0

print(*ans, sep="\n")

Buggy submission (verdict: Runtime Error):
from functools import lru_cache


def popcnt(x):
    return bin(x).count("1")


@lru_cache(maxsize=None)
def rec(n):
    if n == 0:
        return 0
    else:
        return rec(n % popcnt(n)) + 1


n = int(input())
arr = input()

cnt = popcnt(int(arr, 2))
init_big = int(arr, 2) % (cnt + 1)
init_small = int(arr, 2) % (cnt - 1)

li = []
for i in range(n):
    if arr[i] == "0":
        li.append((init_big + (1 << (n - i - 1))) % (cnt + 1))
    else:
        li.append((init_small - (1 << (n - i - 1))) % (cnt - 1))


ans = []

for x in li:
    ans.append(rec(x) + 1)

if int(arr, 2) == 1:
    ans[-1] = 0

print(*ans, sep="\n")

Buggy submission (verdict: Runtime Error):
def popcnt(x):
    return bin(x).count("1")


@lru_cache(maxsize=None)
def rec(n):
    if n == 0:
        return 0
    else:
        return rec(n % popcnt(n)) + 1


n = int(input())
arr = input()

cnt = popcnt(int(arr, 2))
init_big = int(arr, 2) % (cnt + 1)
init_small = int(arr, 2) % (cnt - 1)

li = []
for i in range(n):
    if arr[i] == "0":
        li.append((init_big + (1 << (n - i - 1))) % (cnt + 1))
    else:
        li.append((init_small - (1 << (n - i - 1))) % (cnt - 1))


ans = []

for x in li:
    ans.append(rec(x) + 1)

if int(arr, 2) == 1:
    ans[-1] = 0

print(*ans, sep="\n")

Buggy submission (verdict: Runtime Error):
from functools import lru_cache


def popcnt(x):
    return bin(x).count("1")


@lru_cache(maxsize=None)
def rec(n):
    if n == 0:
        return 0
    else:
        return rec(n % popcnt(n)) + 1


n = int(input())
arr = input()

for i in range(n):
    x = arr[:i] + str(1 ^ int(arr[i])) + arr[i + 1:]
    print(rec(x))

Buggy submission (verdict: Runtime Error):
from functools import lru_cache


@lru_cache(maxsize=None)
def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    x = x + (x >> 64)
    return x & 0x0000007f


@lru_cache(maxsize=None)
def rec(n):
    if n == 0:
        return 0
    else:
        return rec(n % popcount(n)) + 1


n = int(input())
arr = input()

li = []

for i in range(n):
    tmp = arr[:i] + str(1 ^ int(arr[i])) + arr[i + 1:]
    li.append(int(tmp, 2))

for x in li:
    print(rec(x))

Buggy submission (verdict: Runtime Error):
from functools import lru_cache


@lru_cache(maxsize=None)
def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    x = x + (x >> 64)
    return x & 0x0000007f


@lru_cache(maxsize=None)
def rec(n):
    if n == 0:
        return 0
    else:
        return rec(n % popcnt(n)) + 1


n = int(input())
arr = input()

li = []

for i in range(n):
    tmp = arr[:i] + str(1 ^ int(arr[i])) + arr[i + 1:]
    li.append(int(tmp, 2))

for x in li:
    print(rec(x))

Buggy submission (verdict: Runtime Error):
from functools import lru_cache


@lru_cache(maxsize=None)
def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


@lru_cache(maxsize=None)
def rec(n):
    if n == 0:
        return 0
    else:
        return rec(n % popcnt(n)) + 1


n = int(input())
arr = input()

li = []

for i in range(n):
    tmp = arr[:i] + str(1 ^ int(arr[i])) + arr[i + 1:]
    li.append(int(tmp, 2))

for x in li:
    print(rec(x))

Buggy submission (verdict: Runtime Error):
from functools import lru_cache


def popcnt(n):
    c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c >> 8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c >> 16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c >> 32) & 0x00000000ffffffff)
    return c


@lru_cache(maxsize=None)
def rec(n):
    if n == 0:
        return 0
    else:
        return rec(n % popcnt(n)) + 1


n = int(input())
arr = input()

li = []

for i in range(n):
    tmp = arr[:i] + str(1 ^ int(arr[i])) + arr[i + 1:]
    li.append(int(tmp, 2))

for x in li:
    print(rec(x))