Problem:


Score : 400 points

Problem Statement

Let \mathrm{popcount}(n) be the number of 1s in the binary representation of n.
For example, \mathrm{popcount}(3) = 2, \mathrm{popcount}(7) = 3, and \mathrm{popcount}(0) = 0.

Let f(n) be the number of times the following operation will be done when we repeat it until n becomes 0: "replace n with the remainder when n is divided by \mathrm{popcount}(n)." (It can be proved that, under the constraints of this problem, n always becomes 0 after a finite number of operations.)

For example, when n=7, it becomes 0 after two operations, as follows:

\mathrm{popcount}(7)=3, so we divide 7 by 3 and replace it with the remainder, 1.

\mathrm{popcount}(1)=1, so we divide 1 by 1 and replace it with the remainder, 0.

You are given an integer X with N digits in binary.
For each integer i such that 1 \leq i \leq N, let X_i be what X becomes when the i-th bit from the top is inverted.
Find f(X_1), f(X_2), \ldots, f(X_N).

Constraints

1 \leq N \leq 2 \times 10^5

X is an integer with N digits in binary, possibly with leading zeros.

Input

Input is given from Standard Input in the following format:

N
X

Output

Print N lines. The i-th line should contain the value f(X_i).

Sample Input 1

3
011

Sample Output 1

2
1
1

X_1 = 7, which will change as follows: 7 \rightarrow 1 \rightarrow 0. Thus, f(7) = 2.

X_2 = 1, which will change as follows: 1 \rightarrow 0. Thus, f(1) = 1.

X_3 = 2, which will change as follows: 2 \rightarrow 0. Thus, f(2) = 1.

Sample Input 2

23
00110111001011011001110

Sample Output 2

2
1
2
2
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
3



Sample input:
3
011


Sample output:
2
1
1

Submission status: Runtime Error

Solution code:
import sys
import itertools
import math

def popcount(num):
    bit_table_256 = [
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
    ]
    count = 0
    count += bit_table_256[num & 0xFF]
    count += bit_table_256[(num >> 8) & 0xFF]
    count += bit_table_256[(num >> 16) & 0xFF]
    count += bit_table_256[(num >> 24) & 0xFF]
    return count

if __name__ == "__main__":
    N = int(sys.stdin.readline())
    X = sys.stdin.readline()
    X = int(X, 2)
    for i in reversed(range(N)):
        num = int(X ^ (2**i))
        count = 0
        while num != 0:
            num = num % popcount(num)
            # print("num:", num)
            count += 1
        print(count)

Submission status: Runtime Error

Solution code:
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def popcorn(i,k):
    num = 0
    ii = i
    while ii > 0:
        if ii&1:
            num += 1
        ii //= 2
    if i%num:
        return popcorn(i%num,k+1)
    else:
        return k+1

def main():
    n = int(ipt())
    x = list(map(int,input()))
    si = sum(x)
    su = si+1
    sd = si-1
    amu = 0
    amd = 0
    n2u = [1]
    if si == 2:
        n2d = [0]
    else:
        n2d = [1]
    for i in x[::-1]:
        if i:
            amu = (amu+n2u[-1])%su
            amd = (amd+n2d[-1])%sd
        n2u.append((n2u[-1]*2)%su)
        n2d.append((n2d[-1]*2)%sd)
    for i,xi in enumerate(x):
        if xi:
            ni = (amd-n2d[-2-i])%sd
            if si == 1:
                print(0)
            elif ni == 0:
                print(1)
            else:
                print(popcorn(ni,1))
        else:
            ni = (amu+n2u[-2-i])%su
            if ni == 0:
                print(1)
            else:
                print(popcorn(ni,1))


    return None

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# from heapq import heapify, heappop, heappush
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    n=int(input())
    x=input()

    digit=x.count('1')+1
    l=[0]*digit

    def F(n):
        cnt=0
        while True:
            if n==0: break
            n%=bin(n).count('1')
            cnt+=1
        return cnt
    
    Rem=[0]*digit
    for i in range(digit):
        Rem[i]=F(i)
    
    for i in reversed(range(len(x))):
        tenx=int(x,2)
        nx=tenx^(2**i)
        rem=nx%(bin(nx).count('1'))
        if rem==0: print(1)
        else: print(Rem[rem]+1)



    
resolve()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(5000)
n = int(input())
X = input()
nx = int(X, 2)
def f(n):
    pc = bin(n).count('1')
    nn = n%pc
    if nn == 0:
        return 1
    return f(nn) + 1

for i in range(n-1, -1, -1):
    # ibit目を反転させる # つまりi**2を引く
    tmp = pow(2, i)

    if (nx>>i)&1:
        nx -= tmp
        print(f(nx))
        nx += tmp
    else:
        nx += tmp
        print(f(nx))
        nx -= tmp

Submission status: Runtime Error

Solution code:
N = int(input())
X = int(input(),2)

def f(x, n):
  c = format(x, 'b').count("1")
  if x%c==0:
    return n+1
  else:
    return f(x%c, n + 1)

for i in range(N):
  print(f(X^(2**(N-1-i)),0))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# 整数の入力
N = int(input())
# 文字列の入力
X = input()
one = 0
intX = 0
bitcount = 1
for i in reversed(range(len(X))):
    if X[i] == '1':
        one += 1
        intX += bitcount
    bitcount *= 2
hi = one + 1
lo = one - 1
hirembase = intX % hi
lorembase = intX % lo
# print(intX)
# print(hi)
# print(lo)
# print(hirembase)
# print(lorembase)
bo = []
for i in range(200010):
    num = 0
    while i != 0:
        bit = bin(i)
        bitnum = 0
        for j in range(len(bit)):
            if j == 0 or j == 1:
                continue
            if bit[j] == '1':
                bitnum += 1
        i = i % bitnum
        num += 1
    bo.append(num)
ans = []
hirem = 1
lorem = 1
for i in reversed(range(len(X))):
    if X[i] == '0':
        num = (hirembase + hirem + hi) % hi
        ans.append(bo[num] + 1)
    else:
        if bitcount == 1:
            ans.append(0)
        else:
            num = (lorembase - lorem + lo) % lo
            ans.append(bo[num] + 1)
    hirem = (hirem * 2) % hi
    lorem = (lorem * 2) % lo
# print(ans)
# 出力
for i in reversed(range(len(ans))):
    print(ans[i])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
x = input().rstrip()  
for i in range(n):
    newstr= x
    m = int(x[i])
    m^=1
    s = newstr[:i]+str(m)+newstr[i+1:]
    dec = int(s,2)
    rem = 1
    ans = 0
    while rem !=0:
        ans+=1
        count = 0
        num = dec
        while dec!=0 :
            dec &=(dec-1)
            count+=1
        rem = num%count
        dec = rem
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)

def pow_k(x, n):
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return K * x

n = int(input())
x = list(input())

popcount = [0] * (10**5 + 1)
for i in range(10**5+1):
    popcount[i] = format(i, 'b').count('1')

counter = x.count('1')
number = int(''.join(x), 2)

def f(num, cnt):
    if num == 0:
        return cnt
    return f(num % popcount[num], cnt+1)

for i in range(n):    
    if x[i] == '0':
        m = number + pow_k(2, n-i-1)
        print(f(m % (counter+1), 1))
    if x[i] == '1':
        m = number - pow_k(2, n-i-1)
        print(f(m % (counter-1), 1))

Submission status: Runtime Error

Solution code:
#import sys
#input = sys.stdin.readline
from collections import Counter
def func(x):
    cnt = 0
    y = x
    while x > 0:
        if x%2 == 1:
            cnt += 1
        x //= 2
    return y%cnt
        
def main():
    N = int( input())
    X = list( map( int, list( input())))
    base_plus = 0
    base_minus = 0
    r = 1
    one = Counter(X)[1]
    for x in X[::-1]:
        base_plus += r*x
        base_plus %= one+1
        r *= 2
        r %= one+1
    r = 1
    for x in X[::-1]:
        base_minus += r*x
        base_minus %= one-1
        r *= 2
        r %= one-1

    ANS = [0]*N
    # print(base)
    # print(bin(base))
    for i in range(N):
        if one == 1:
            if X[i] == 1:
                ANS[i] = 0
                continue
        if X[i] == 1:
            xi = (base_minus -  pow(2,N-1-i,one-1))%(one-1)
            # print(i, bin(base -  pow(2,N-1-i)), one-1)
        else:
            xi = (base_plus +  pow(2,N-1-i,one+1))%(one+1)
            # print(i, bin(base +  pow(2,N-1-i)), one+1)
        # print(i,xi)
        if xi == 0:
            ANS[i] = 1
            continue
        ans = 1
        while xi > 0:
            ans += 1
            xi = func(xi)
        ANS[i] = ans
    print("\n".join( map( str, ANS)))
    
    
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
X = input().strip()

if not '1' in X:
    for i in range(N):
        print(0)
    exit()

M = 2*10**5+ 1
pc = [0]*(M+2)
for i in range(1,M+2):
    j = i
    t = 0
    while i > 0:
        k = bin(i).count('1')
        i %= k
        t += 1
    pc[j] = t

X1 = X.count('1')
X0 = N - X1

Rp1 = []
Rm1 = []
Bp1 = []
Bm1 = []
for i, x in enumerate(list(X[::-1])):
    tp1 = pow(2,i,X1+1)
    tm1 = pow(2,i,X1-1)
    Bp1.append(tp1)
    Bm1.append(tm1)
    if x == '1':
        Rp1.append(tp1)
        Rm1.append(tm1)
    else:
        Rp1.append(0)
        Rm1.append(0)

basep1 = sum(Rp1)
basem1 = sum(Rm1)
Rp1 = Rp1[::-1]
Rm1 = Rm1[::-1]
Bp1 = Bp1[::-1]
Bm1 = Bm1[::-1]

#print("base",basep1)
#print("base",basem1)
for bp1,bm1,x in zip(Bp1,Bm1,X):
    if x == '1':
        t = basem1 - bm1
        MOD = X1 - 1
    else:
        t = basep1 + bp1
        MOD = X1 + 1

    #print("x",x,"t",t)
    #print(t % MOD,MOD)
    print(pc[t % MOD] + 1)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))
#%%code

def naive(a):
    assert a>0
    b=a
    for i in range(1,1000000):
        t=bin(b).count("1") #popcount
        b%=t
        if b==0:
            return i
    assert b==0
def resolve():
    N,=pin()
    X=int(input(),2)
    #print(+X)
    cnt=0
    for i in range(N):
        temp=X^(1<<(N-i-1))
    #    print(temp,";")
        print(naive(temp))
#%%submit!
resolve()

Submission status: Runtime Error

Solution code:
N = int(input())
X = str(input())


def popcount(p):
    return bin(p).count('1')


def get_answer(i):
    ans = 0

    while True:
        tmp = i % popcount(i)

        ans = ans + 1
        if tmp == 0:
            break
        i = tmp

    return ans

for i in range(len(X)):
    t = list(X)

    if t[i] == '0':
        t[i] = '1'
    else:
        t[i] = '0'

    print(get_answer(int("".join(t), 2)))

Submission status: Runtime Error

Solution code:
#create date: 2020-07-11 21:18

import sys
stdin = sys.stdin

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def popcount(m):
    res = 0
    while m:
        if m & 1:
            res += 1
        m //= 2
    return res
def f(m):
    cnt = 0
    while m:
        #print("test", m)
        m = m % popcount(m)
        cnt += 1
    return cnt

def main():
    n = ni()
    x = ns()
    pop0 = x.count("1") + 1
    pop1 = x.count("1") - 1
    y0 = 0; y1 = 0
    for i, xi in enumerate(x):
        r = n - i - 1
        if xi == "1":
            y0 += pow(2, r, pop0)
            y1 += pow(2, r, pop1)
    y0 %= pop0
    y1 %= pop1

    for i, xi in enumerate(x):
        r = n - i - 1
        if xi == "0":
            m = (y0 + pow(2, r, pop0)) % pop0
            print(f(m) + 1)
        else:
            m = (y1 - pow(2, r, pop1)) % pop1
            print(f(m) + 1)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = input()
d = {}
def sub(val):
    if val in d:
        return d[val]
    pc = 0
    for i in range(val.bit_length()):
        if val>>i&1:
            pc += 1
    if pc==0:
        ans = 0
    else:
        tmp = val % pc
        if tmp==0:
            ans = 1
        else:
            ans = sub(tmp) + 1
    d[val] = ans
    return ans
pc = sum(item=="1" for item in a)
val0 = 0 # pc-1
val1 = 0 # pc+1
for i in range(n):
    if a[i]=="1":
        val0 += pow(2,n-1-i,pc-1)
        val1 += pow(2,n-1-i,pc+1)
        
ans = [None]*n
# print(a)
for i in range(n):
    if a[i]=="1":
        val = (val0 - pow(2,n-1-i,pc-1))%(pc-1) #(1<<(n-1-i))
        ans[i] = sub(val) + 1
#         print(1, bin(val)[2:], pc-1)
    else:
        val = (val1 + pow(2,n-1-i,pc+1))%(pc+1) #(1<<(n-1-i))
        ans[i] = sub(val) + 1
#         print(0, bin(val)[2:], pc+1)
write("\n".join(map(str, ans)))

Submission status: Runtime Error

Solution code:
def popcount(n,ans):
	if n==0: return ans
	if n < len(dp) and dp[n] != -1: return dp[n]
	ne = n%str(bin(n)).count("1")
	ans = popcount(ne,ans+1)
	dp[ne] = ans
	return ans

global dp
n = int(input())
s = input()
#print(int(s,2))
x = int(s,2)
d = str(bin(x)).count("1")
ans = x%d
dp = []
for i in range(ans): dp.append(-1)

for i in range(n):
	if s[i] == "1":
		temp_d = d-1
		temp = int(s[:i] + "0" + s[i+1:],2)
	else:
		temp_d = d+1
		temp = int(s[:i] + "1" + s[i+1:],2)
	next_temp = temp%temp_d
	print(popcount(next_temp,1))

Submission status: Runtime Error

Solution code:
import sys
import itertools
import math
from tqdm import tqdm

def popcount(num):
    bit_table_256 = [
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
    ]
    count = 0
    count += bit_table_256[num & 0xFF]
    count += bit_table_256[(num >> 8) & 0xFF]
    count += bit_table_256[(num >> 16) & 0xFF]
    count += bit_table_256[(num >> 24) & 0xFF]
    return count

if __name__ == "__main__":
    N = int(sys.stdin.readline())
    X = sys.stdin.readline()
    X = int(X, 2)
    for i in reversed(range(0, N)):
        num = int(X ^ (2**i))
        count = 0
        while num != 0:
            num = num % popcount(num)
            # print("num:", num)
            count += 1
        print(count)

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()

N_ub = 2 * 10 ** 5
f = [-1] * (N_ub + 1)
f[0] = 0
for n in range(1, N_ub + 1):
    pc = format(n, "b").count("1")
    f[n] = f[n % pc] + 1

X_pc = X.count("1")
X_res_m1 = 0
X_res_p1 = 0
for i, s in enumerate(reversed(X)):
    if s == "1":
        X_res_m1 += pow(2, i, X_pc - 1)
        X_res_m1 %= X_pc - 1

        X_res_p1 += pow(2, i, X_pc + 1)
        X_res_p1 %= X_pc + 1

ans = []
for i, s in enumerate(reversed(X)):
    if s == "1":
        fx = (X_res_m1 - pow(2, i, X_pc - 1)) % (X_pc - 1)
        ans.append(f[fx] + 1)
    else:
        fx = (X_res_p1 + pow(2, i, X_pc + 1)) % (X_pc + 1)
        ans.append(f[fx] + 1)

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

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
ones = 0
for i in x:
    if i=='1':
        ones += 1
mods = [0, 0]
for i in range(n):
    if x[n-i-1]=='1':
        if ones>0:
            mods[0] += pow(2, i, ones-1)
        if ones<n:
            mods[1] += pow(2, i, ones+1)
mods[0] %= ones-1
mods[1] %= ones+1
def f(x):
    if x==0:
        return 1
    cnt = 1
    while x>0:
        p = bin(x).count('1')
        x %= p
        cnt += 1
    return cnt
for i in range(n-1, -1, -1):
    if x[n-i-1]=='1':
        init = (mods[0] - pow(2, i, ones-1))%(ones-1)
    else:
        init = (mods[1] + pow(2, i, ones+1))%(ones+1)
    if x[n-i-1]=='1' and ones==1:
        print(0)
    else:
        print(f(init))

Submission status: Runtime Error

Solution code:
def popcnt1(n):
    return bin(n).count("1")

def okikae(n):
    kaisu = 0
    if n == 0:
        return 0
    while 1:
        P = popcnt1(n)
        n %= P
        kaisu += 1
        if n == 0:
            return kaisu

OKI = [okikae(i) for i in range(20001)]
X = int(input())
Norig = input()
N = int(Norig,2)
Npop = Norig.count("1")
F = Npop + 1
H = Npop - 1
if H == 0:
    H = -1
FueAmari = N%(Npop + 1)
if Npop != 1:
    HeruAmari = N%(Npop - 1)
else:
    HeruAmari = -1
Fues = []
Herus = []
fue = 1
heru = 1
for i in range(2*(10**5+1)):#2^0の桁から
    fue %= F
    heru %= H
    Fues.append(fue)
    Herus.append(heru)
    fue *= 2
    heru *= 2
RNorig = reversed(Norig)
Results = []
Zougen = []#増えたらTrue
Kaisu = [0] * X
#上の桁から見ていく。ゼロなら減ってイチなら増える
for n,bit in enumerate(Norig):#2**(N-1-n)の桁
    if bit == "0":#増える
        Zougen.append(True)
        print(1+OKI[(FueAmari + Fues[X-1-n] )% F])
    else:
        if H == -1:
            print(0)
            continue
        Zougen.append(False)
        print(1+OKI[(HeruAmari - Herus[X-1-n]) % F])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

#from collections import defaultdict
#from heapq import heappush, heappop
#import numpy as np
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7

debug_indent = 0


def debug(*x):
    global debug_indent
    x = list(x)
    indent = 0
    if x[0].startswith("enter") or x[0][0] == ">":
        indent = 1
    if x[0].startswith("leave") or x[0][0] == "<":
        debug_indent -= 1
    x[0] = "  " * debug_indent + x[0]
    print(*x, file=sys.stderr)
    debug_indent += indent


def solve(N, X):
    o1 = ord("1")

    def f(n):
        p = bin(n).count("1")
        return n % p

    table = [0] * 20
    for i in range(1, 20):
        x = f(i)
        if x == 0:
            table[i] = 1
        else:
            table[i] = table[x] + 1

    numOne = X.count(o1)
    p2mod = [0] * N
    ret = [0] * N
    for i in range(N):
        if X[i] == o1:
            mod = numOne - 1
        else:
            mod = numOne + 1
        v = 0
        for j in range(N):
            v *= 2
            v %= mod
            if (X[j] == o1) ^ (i == j):
                v += 1
        v %= mod
        # debug(": v", v)
        if v == 0:
            ret[i] = 1
            continue
        if v < 20:
            ret[i] = table[v] + 1
            continue

        v = f(v)
        ret[i] = table[v] + 2

    # debug(": table", table)
    # debug(": ret", ret)
    return ret


def main():
    # parse input
    N = int(input())
    X = input().strip()
    print(*solve(N, X), sep="\n")


# tests
T1 = """
3
011
"""


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    2
    1
    1
    """


T2 = """
23
00110111001011011001110
"""


def test_T2():
    """
    >>> as_input(T2)
    >>> main()
    2
    1
    2
    2
    1
    2
    2
    2
    2
    2
    2
    2
    2
    2
    2
    2
    2
    2
    2
    2
    2
    1
    3
    """
# add tests above


def _test():
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())

    def input():
        return bytes(f.readline(), "ascii")

    def read():
        return bytes(f.read(), "ascii")


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        print("testing")
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()

def p(x):
    return x.count('1')

# p(n)は高々2*10^5

from functools import lru_cache

@lru_cache(maxsize=None)
def f(n, k):
    b = bin(n) # binary str
    q = p(b[2:]) # 1の個数
    if n % q == 0:
        return k
    else:
        return f(n % q, k + 1)

cnt = p(x)
for i in range(n):
    if x[i] == '0':
        y = x[:i] + '1' + x[i + 1:]
    else:
        y = x[:i] + '0' + x[i + 1:]
    print(f(int(y, 2), 1))

Submission status: Runtime Error

Solution code:
N = int(input())
X = int(input(),2)

def pc(n):
    return(str(bin(n)).count("1"))
def reverse(i):
    return X^(1 << i-1)
def f(n):
    ans = 0
    while True:
        n = n%pc(n)
        ans += 1
        if n == 0:
            break
    return ans
for i in range(N,0,-1):
    print(f(reverse(i)))

Submission status: Runtime Error

Solution code:
import sys
input = lambda:sys.stdin.readline().rstrip()
from collections import defaultdict

sys.setrecursionlimit(10**7)
def solve(k, cnt):
    S = str(bin(k))[2:].zfill(k).count("1") 
    L = k % S
    if L == 0:
        return 1
    cnt += solve(L,cnt)
    return cnt 

N = int(input())
P = input()
for i in range(N):
    cnt = 1
    if P[i] == "1":
        tmp = int(P,2) - 2**(N-i-1)
    else:
        tmp = int(P,2) + 2**(N-i-1)    
    #print(tmp, bin(tmp))
    print(solve(tmp,cnt))
    
#print(solve(N,cnt))

Submission status: Runtime Error

Solution code:
n = int(input())
x = list(input())
p_origin = x.count('1')

def bit_count(x):
    count = 0
    while x > 0:
        if x & 1:
            count += 1
        x = x >> 1
    return count


def get_ans(i):
    ans = 1
    if x[i] == '0':
        p_first = (sum_plus + p_plus[i]) % (p_origin+1)
    else:
        p_first = (sum_minus - p_minus[i]) % (p_origin-1)
    while p_first != 0:
        p_first = p_first % bit_count(p_first)
        ans += 1
    return ans

p_minus = [0]*n # x%(p-1)
p_plus = [0]*n # x%(p+1)

t1 = 1
t2 = 1
for i in range(n):
    p_minus[n-1-i] = t1
    p_plus[n-1-i] = t2
    t1 *= 2
    t2 *= 2
    t1 %= p_origin-1
    t2 %= p_origin+1

sum_plus = 0
sum_minus = 0
for i in range(n):
    if x[i] == '1':
        sum_plus += p_plus[i]
        sum_minus += p_minus[i]

for i in range(n):
    print(get_ans(i))

Submission status: Runtime Error

Solution code:
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
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
N = int(readline())
S = readline().decode().rstrip()
one_cnt = S.count('1')
cnt = [0]*(one_cnt+1)
for i in range(1,one_cnt+1):
    j = i % popcnt(i)
    cnt[i] = 1 + cnt[j] 
    
n = int(S, 2)
for i in range(N):
    if S[i] == '1':
        tmp = n - 2**(N-i-1)
        tmp %= (one_cnt-1)
        print(1+cnt[tmp])
    else:
        tmp = n + 2**(N-i-1) 
        tmp %= (one_cnt+1)
        print(1+cnt[tmp])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)


def f(n):
    p = n % popcnt(n)
    if p == 0:
        return 1
    else:
        return f(p) + 1


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


def main(input, print):
    N = int(input())
    X = int(input(), 2)
    for i in reversed(range(N)):
        b = 1 << i
        a = X ^ b
        print(f(a))


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()

l = [0] * (2*10**5+1)
ans = [0] * (2*10**5+1)
for i in range(2*10**5+1):
  l[i] = bin(i).count('1')
  
for i in range(2*10**5+1):
  x = i
  y = 0
  while x!=0:
    y += 1
    x %= l[x]
    
  ans[i] = y
  
X_count = X.count('1')
plu = X_count + 1
mi = X_count - 1
plu_res = 0
mi_res = 0
X_int = int(X,2)

for i in range(N):
  if X[i]=='0':
    continue
  else:
    plu_res += pow(2,N-i-1,plu)
    plu_res %= plu
    if mi>=0:
      mi_res += pow(2,N-i-1,mi)
      mi_res %= mi
      
for i in range(N):
  if X[i]=='0':
    x = (plu_res + pow(2,N-i-1,plu)) % plu
    print(1 + ans[x])
  else:
    x = (mi_res - pow(2,N-i-1,mi)) % mi
    print(1 + ans[x])