Problem p02609 (python)

Fixed submission:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

# import random
# N = random.randint(0, 2*100000)
# X = ""
# for i in range(N):
#     if random.random() < 0.5:
#         X += "0"
#     else:
#         X += "1"
# print(N, X)


N = INT()
X = input()

def popcount(n):
    cnt = 0
    while n:
        n %= "{:b}".format(n).count("1")
        cnt += 1
    return cnt

pl = [0]*(N+1)
for i in range(N+1):
    pl[i] = popcount(i)
bn = X.count("1")

modp = [0]*N
modm = [0]*N

for i in range(N):
    if X[i] == "1":
        modp[i] = pow(2, N-1-i, bn+1)
        if not bn == 1:
            modm[i] = pow(2, N-1-i, bn-1)

sp = sum(modp)
sm = sum(modm)
ans = [0]*N
for i in range(N):
    if X[i] == "1":
        if bn == 1:
            ans[i] = 0
            continue
        s = sm
        s -= modm[i]
        s %= bn-1
        ans[i] = pl[s]+1
    else:
        s = sp
        s += pow(2, N-1-i, bn+1)
        s %= bn+1
        ans[i] = pl[s]+1

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

Buggy submission (verdict: Runtime Error):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
X = input()
def popcount(n):
    cnt = 0
    while n:
        n %= "{:b}".format(n).count("1")
        cnt += 1
    return cnt

pl = [0]*(N+1)
for i in range(N+1):
    pl[i] = popcount(i)
bn = X.count("1")

modp = [0]*N
modm = [0]*N

for i in range(N):
    if X[i] == "1":
        modp[i] = pow(2, N-1-i, bn+1)
        modm[i] = pow(2, N-1-i, bn-1)

sp = sum(modp)
sm = sum(modm)
ans = [0]*N
for i in range(N):
    if X[i] == "1":
        if bn == 1:
            ans[i] = 0
            continue
        s = sm
        s -= modm[i]
        s %= bn-1
        ans[i] = pl[s]+1
    else:
        s = sp
        s += pow(2, N-1-i, bn+1)
        s %= bn+1
        ans[i] = pl[s]+1

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

Buggy submission (verdict: Runtime Error):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
X = input()
def popcount(n):
    cnt = 0
    while n:
        n %= "{:b}".format(n).count("1")
        cnt += 1
    return cnt

pl = [0]*(N+1)
for i in range(N+1):
    pl[i] = popcount(i)
bn = X.count("1")

modp = [0]*N
modm = [0]*N

for i in range(N):
    if X[i] == "1":
        modp[i] = pow(2, N-1-i, bn+1)
        modm[i] = pow(2, N-1-i, bn-1)

sp = sum(modp)
sm = sum(modm)
ans = [0]*N
for i in range(N):
    if X[i] == "1":
        if bn == 1:
            ans[i] = 0
            continue
        s = sp
        s -= modm[i]
        s %= bn-1
        ans[i] = pl[s]+1
    else:
        s = sm
        s += pow(2, N-1-i, bn+1)
        s %= bn+1
        ans[i] = pl[s]+1

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

Buggy submission (verdict: Runtime Error):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
X = input()
def popcount(n):
    cnt = 0
    while n:
        n %= "{:b}".format(n).count("1")
        cnt += 1
    return cnt
pl = [0]*(N+1)
for i in range(N+1):
    pl[i] = popcount(i)
bn = X.count("1")

modp = [0]*N
modm = [0]*N

for i in range(N):
    if X[i] == "1":
        modp[i] = pow(2, N-1-i, bn+1)
        modm[i] = pow(2, N-1-i, bn-1)

ans = [0]*N
for i in range(N):
    if X[i] == "1":
        if bn == 1:
            ans[i] = 0
            continue
        s = sum(modm)
        s -= modm[i]
        s %= bn-1
        ans[i] = pl[s]+1
    else:
        s = sum(modp)
        s += pow(2, N-1-i, bn+1)
        s %= bn+1
        ans[i] = pl[s]+1

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

Buggy submission (verdict: Runtime Error):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()

X = list(map(int, list(input())))
bit_num = sum(x==1 for x in X)
bp = [0]*N
bm = [0]*N
for i in range(N):
    if X[i]:
        bp[i] = pow(2, N-1-i, bit_num+1)
        bm[i] = pow(2, N-1-i, bit_num-1)
flag = sum(X) == 1
ans = [0]*N
for i in range(N):
    if X[i]:
        if flag:
            ans[i] = 0
            continue
        s = sum(bm)
        s -= bm[i]
        b = bit_num-1
        s %= b
        cnt = 1
        tmp = s
        nex = list(map(int, "{:b}".format(s)))
        b = sum(x==1 for x in nex)
        while tmp:
            for j in range(len(nex)):
                if nex[-(j+1)]:
                    tmp += pow(2, j, b)
                    tmp %= b
            nex = list(map(int, "{:b}".format(tmp)))
            b = sum(x==1 for x in nex)
            cnt += 1
    else:
        s = sum(bp)
        b = bit_num+1
        s += pow(2, N-i-1, bit_num+1)
        s %= b
        cnt = 1
        tmp = s
        nex = list(map(int, "{:b}".format(s)))
        b = sum(x==1 for x in nex)
        while tmp:
            for j in range(len(nex)):
                if nex[-(j+1)]:
                    tmp += pow(2, j, b)
                    tmp %= b
            nex = list(map(int, "{:b}".format(tmp)))
            b = sum(x==1 for x in nex)
            cnt += 1
    ans[i] = cnt

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

Buggy submission (verdict: Runtime Error):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()

X = list(map(int, list(input())))
bit_num = sum(x==1 for x in X)
bp = [0]*N
bm = [0]*N
for i in range(N):
    if X[i]:
        bp[i] = pow(2, N-1-i, bit_num+1)
        bm[i] = pow(2, N-1-i, bit_num-1)
flag = sum(X) == 1
ans = [0]*N
for i in range(N):
    if X[i]:
        if flag:
            ans[i] = 0
            continue
        s = sum(bm)
        s -= bm[i]
        b = bit_num-1
        s %= b
        cnt = 1
        tmp = s
        nex = list(map(int, "{:b}".format(s)))
        b = sum(x==1 for x in nex)
        while tmp:
            for j in range(len(nex)):
                if nex[-(j+1)]:
                    tmp += pow(2, j, b)
                    tmp %= b
            nex = list(map(int, "{:b}".format(tmp)))
            b = sum(x==1 for x in nex)
            cnt += 1
    else:
        s = sum(bp)
        b = bit_num+1
        s += pow(2, N-i-1, bit_num+1)
        s %= b
        cnt = 1
        tmp = s
        nex = list(map(int, "{:b}".format(s)))
        b = sum(x==1 for x in nex)
        while tmp:
            for j in range(len(nex)):
                if nex[-(j+1)]:
                    tmp += pow(2, j, b)
                    tmp %= b
            nex = list(map(int, "{:b}".format(tmp)))
            b = sum(x==1 for x in nex)
            cnt += 1
    ans[i] = cnt

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

Buggy submission (verdict: Runtime Error):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.buffer.readline()[:-1]
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''
    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)
    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f

N = INT()
X = input()
X = int(X, 2)
for i in range(N):
    Y = X^(1<<(N-i-1))
    cnt = 0
    while Y:
        Y = Y%popcount(Y)
        cnt += 1
    print(cnt)