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:
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 (input())
X = input()

for i in range(N):
  if X[i] == '0':
    X[i] = '1'
  else:
    X[i] = '0'
  print(popcount(int(bin(X))))
  if X[i] == '0':
    X[i] = '1'
  else:
    X[i] = '0'

Submission status: Runtime Error

Solution code:
import math

A = [0]*200001
for i in range(18):
    for j in range(2**i,2**(i+1)):
        if j <= 200000:
            A[j] = i + 1

def bii(x):
    a = A[x]
    o = [0]*a
    for i in range(a):
        o[i] = x % 2
        x //= 2
    return o

def f(x):
    bi = bii(x)
    popcount = sum(bi)
    a = x % popcount
    if a == 0:
        return 1
    else:
        return f(a)+1

N = int(input())
X = list(map(int,list(input())))
X.reverse()

popc = sum(X)
D = dict()
E = dict()
for j in [popc-1,popc+1]:
    E[j] = 0
    D[j] = [0]*N
    b = 1
    for i in range(N):
        D[j][i] = b
        E[j] += X[i] * b
        E[j] %= j
        b *= 2
        b %= j

aaaa = []
for i in range(N):
    an = X[-(i+1)]
    bb = 1 - 2 * an
    #もしi桁目が1ならば、ビット反転によってpopcとXは減る
    #もしi桁目が0ならば、ビット反転によってpopcとXは増える
    j = popc + bb
    su = (E[j] + bb * D[j][-(i+1)] + j) % j
    if su == 0:
        print(1)
    else:
        print(f(su)+1)

Submission status: Runtime Error

Solution code:
def popcount(n):
    n = n % bin(n).count('1')
    if n != 0:
        global num
        num = num + 1
        popcount(n)

N = int(input().rstrip())
X = input().rstrip()

for i in range(N):
    if X[i] == '0':
        reverse = '1'
    else:
        reverse = '0'
    x = X[:i] + reverse + X[i+1:]
    n = int(x, 2)
    num = 1
    popcount(n)
    print(num)

Submission status: Runtime Error

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

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

p = [-1 for _ in range(2*(10**5)+10)]
cnt = x.count('1')

def calc(a):
  #print('a=',a)
  if p[a] != -1:
    return p[a]
  else:
    if a == 0:
      ret = 0
    else:
      b = bin(a).count('1')
      ret = 1+calc(a%b)
    p[a] = ret
    return ret

x0 = int(x,2)%(cnt-1)
x1 = int(x,2)%(cnt+1)
for i in range(n):
  y = list(x)
  if y[i] == '0':
    xx = pow(2,n-i-1,cnt+1)
    print(calc((x1+xx)%(cnt+1))+1)
  else:
    xx = pow(2,n-i-1,cnt-1)
    print(calc((x0-xx)%(cnt-1))+1)

Submission status: Runtime Error

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

# N = 23
# A = '00110111001011011001110'

def popcount(n):
    B = format(n, 'b')
    c = 0
    for i in B:
        if i == '1':
            c += 1
    return c    

def div_pop(n):
    P = popcount(n)
    return n%P

c = 0
A10 = int(A,2)
for i in range(N):
    if A[i] == '1':
        c += 1


counter = []
AC = []
for i in range(N):
    if A[i] == '1':
        counter.append(c-1)
        AC.append(A10-2**(22-i))
        
    else:
        counter.append(c+1)
        AC.append(A10+2**(22-i))

for a in AC:
    ans = 0
    while a > 0:
        ans += 1
        a = div_pop(a)
    print(ans)

Submission status: Runtime Error

Solution code:
def popcount(x):
  c = 0
  while(x > 0):
    if x % 2 == 1:
      c += 1
    x = int(x / 2)
  return c

def calc(x):
  c = 0
  while(x > 0):
    x = x % popcount(x)
    c += 1
  return c

n=int(input())
x=input()
for i in range(0,n):
  j = 0
  if x[i] == '0':
    j = 1
  k = x[:i] + str(j) + x[i+1:]
  l = int(k, 2)
  print(calc(l))

Submission status: Runtime Error

Solution code:
from numba import njit

N = int(input())
X = list( i for i in str(input()))

@njit
def nisin(a, I):
  a = a.copy()
  if a[I] == '0':
    a[I] =  '1'
  elif a[I] == '1':
    a[I] = '0'
    
  return int(''.join(a), 2)

@njit
def solve(kazu):
  cnt = 0
  
  while True:
    if kazu == 0:
      break
    cnt += 1
    kazu2 = format(kazu,'b')
    c = kazu2.count('1')
    if kazu % c == 0:
      break
    kazu = kazu % c
  return cnt


for i in range(N):
  print(solve(nisin(X, i)))

Submission status: Runtime Error

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

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

counter = sum(list(map(int, x)))
number = sum([pow(2, n-i-1) for i in range(n) if x[i] == '1'])

def f(num, cnt):
    if num == 0:
        return cnt
    popcount = sum(list(map(int, format(num, 'b'))))
    return f(num % popcount, cnt+1)

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

Submission status: Runtime Error

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

B = 2**20 - 1

memo = [None for _ in range(2*n)]
memo[0] = 0


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


for i in range(1, n):
    tmp = i % popcount(i)
    memo[i] = memo[tmp] + 1

for i in range(n):
    tmp = x[:]
    tmp[i] = '1' if tmp[i] == '0' else '0'
    tmp = int(''.join(tmp), 2)
    tmp = tmp % popcount(tmp)
    print(memo[tmp] + 1)

Submission status: Runtime Error

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


def solve(N: int, X: str):
    def pc(n):
        return bin(n).count("1")
    
    popsc = [0] * 25
    for i in range(1,25):
        p = 0
        t = i
        k = -1
        while(k!= 0):
            p+=1
            k_ = t % pc(t)
            t = k
            k = k_
        popsc[i] = p

    x = int(X, 2)
    for i,xi in enumerate(X):
        if xi == "0":
            temp = (x + 2**(N-i-1))
        else:
            temp = (x - 2**(N-i-1))
        
        if temp > 24:
            temp = temp % bin(temp).count("1")
            p = 1
        else:
            p = 0

        print(popsc[temp]+p)

    
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    X = next(tokens)  # type: str
    solve(N, X)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

def ppc(k): #k:2進数 bin
  cnt1 = sum( list(map(int, list(k) ) ) )
  k_10 = int(k, 2) #１０進数
  return format( k_10 % cnt1, 'b') #2adic

for i in range(n):
  ly = list(x)
  if ly[i] == '0':
    ly[i] = '1'
    y = ''.join(ly)
  else:
    ly[i] = '0'
    y = ''.join(ly)
  cnt = 0
  
  while True:
    if y == '0':
      break
    y = ppc(y)
    cnt += 1
  print(cnt)

Submission status: Runtime Error

Solution code:
n=int(input())
x=input()
t=int(x,2)
c=x.count('1')
from functools import *
@lru_cache(None)
def popcount(x):
  if x==0: return 0
  return popcount(x%bin(x).count('1'))+1
for i in range(n):
  if int(x[i]):
    d=c-1
    print(popcount((t-pow(2,n-i-1,d))%d)+1)
  else:
    d=c+1
    if c<1: print(0)
    print(popcount((t+pow(2,n-i-1,d))%d)+1)

Submission status: Runtime Error

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

N = int(input())
X = int(input(), 2)


def popc(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

def func(n):
    count = 1
    while n % popc(n):
        n = n % popc(n)
        count += 1
    return count

def change(X, i):
    if X & (1<<(N-i-1)):
        X &= ~(1<<(N-i-1))
    else:
        X |= (1<<(N-i-1))
    return X

for i in range(N):
    print(func(change(X, i)))

Submission status: Runtime Error

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

#N = 23
#X = '00110111001011011001110'

def popcount(n):
    return str(bin(n)).count('1')

def func(n, l):
    n = n % popcount(n)
    if n == 0:
        return l
    else:
        return func(n, l+1)

list_X = list(X)
for i in range(N):
    #Xのi桁目を反転したbinary
    x = copy.copy(list_X)
    if x[i] == '0':
        x[i] = '1'
    else:
        x[i] = '0'
    z = int(''.join(x), 2)
    print(func(z, 1))

Submission status: Runtime Error

Solution code:
def popcount(a):
    s = str(bin(a))
    return s.count('1')

def func(a):
    cnt=0
    while True:
        a = a % popcount(a)
        cnt+=1
        if a==0:
            break
    return cnt

n = int(input(''))
x = input('')

for i in range(n):
    x2 = list(x)
    if x[i] =='0':
        x2[i] = '1'
    else:
        x2[i] = '0'
    x3 = "".join(x2)
    ans = func(int(x3,2))
#    print("{} -> [{}] ->{}".format(x3,int(x3,2),ans))
    print(ans)

Submission status: Runtime Error

Solution code:
def cal_nums(number, num_one=-1):
    cp = number
    cnt = 0
    pos = 0
    if num_one == -1:
        while(1):
            if (cp >> pos) == 0:
                break
            cnt += ((cp>>pos)&1)
            pos += 1
    else:
        cnt = num_one
    
    # cnt_cp = cnt
    # mul = 2
    # while(cnt < number):
    #     cnt *= mul
    #     mul = mul << 1

    # return (number - cnt // mul) % cnt_cp
    return number % cnt

def func(number, num_one):
    cnt = 0
    tmp = number
    while(1):
        cnt += 1
        if cnt == 1:
            tmp = cal_nums(tmp, num_one)
        else:
             tmp = cal_nums(tmp)
        if tmp == 0:
            break
    return cnt

n = int(input())
string = input()
length = len(string)
tmp = 0
for i in range(length):
    tmp *= 2
    if string[i] == '1':
        tmp += 1

cnt_0 = 0
cnt_1 = 0

for idx in range(length):
    if string[idx] == '0':
        cnt_0 += 1
    else:
        cnt_1 += 1

for idx in range(length):
    if string[idx] == '0':
        print(func(tmp+(1<<(length-idx-1)), cnt_1+1))
        # print(tmp+(1<<(length-idx-1)))
    else:
        print(func(tmp-(1<<(length-idx-1)), cnt_1-1))
        # print(tmp-(1<<(length-idx-1)))

Submission status: Runtime Error

Solution code:
def popcount(n):
    return bin(n).count('1')

N = int(input())
X = input()
XX = []
for j in X:
    XX.append(j)

for i in range(1,N+1):
    print('XX', XX)
    count = 0
    
    if XX[i-1] == '0':
        XX[i-1] = '1' 
        XXX = ''.join(XX)
        XX[i-1] = '0'
        x = int(XXX, 2)
        while x > 0:
            x = x % popcount(x)
            count += 1
        print(count)
    
    else:
        XX[i-1] = '0'
        XXX = ''.join(XX)
        XX[i-1] = '1'
        x = int(XXX, 2)
        while x > 0:
            x = x % popcount(x)
            count += 1
        print(count)

Submission status: Runtime Error

Solution code:
n = int(input())
s = input()[::-1]
cnt = s.count('1')

p1 = sum(pow(2, i, cnt+1) * (s[i] == '1') for i in range(n))
m1 = sum(pow(2, i, cnt-1) * (s[i] == '1') for i in range(n))

def op(n):
    popcnt = bin(n).count('1')
    return n%popcnt

pre = [0]*100000
for i in range(1,100000):
    pre[i] = pre[op(i)] + 1

def solve(i):
    if s[-i] == '0':
        r = (p1 + pow(2, n-i, cnt+1))%(cnt+1)
    else:
        if cnt == 1:
            return 1
        r = (m1 - pow(2, n-i, cnt-1))%(cnt-1)
    return 1 + pre[r]

for i in range(n):
    print(solve(i+1))

Submission status: Runtime Error

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_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 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
X = input()

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

n = X.count("1")

n1 = n-1
n2 = n+1

q_1 = [0]*N
q_2 = [0]*N
for i in range(N):
	q_1[i] = pow(2, i, n1)
	q_2[i] = pow(2, i, n2)

mod_sum_1 = 0
mod_sum_2 = 0

for i in range(N):
	if X[-i-1] == "1":
		mod_sum_1 += q_1[i]
		mod_sum_2 += q_2[i]

q_1 = q_1[::-1]
q_2 = q_2[::-1]

for i in range(N):
	if X[i] == "1":
		m = n1
		mod_sum = mod_sum_1 - q_1[i]
	else:
		m = n2
		mod_sum = mod_sum_2 + q_2[i]
	print(popcount(mod_sum%m)+1)

Submission status: Runtime Error

Solution code:
N = int(input())
X = str(input())
x_num_ = 0
x = 0
## 個数カウント
for i,Xi in zip(range(N)[::-1],X):
    x += int(Xi)
    x_num_ += int(Xi)*2**i
## popcount
def popcount(x):
    a = bin(x)[2:]
    b = 0
    for ai in a:
        b += int(ai)
    return b
n = int(2e5)
a = [0]*n
for i in range(n):
    a[i] = popcount(i+1)
##########
def f(x):
    ans = 0
    while x%a[x-1] != 0:
        x = x%a[x-1]
        ans += 1
    ans +=1
    return ans
##########
b = {0:1}
for i,Xi in zip(range(N)[::-1],X):
    ans = 0
    if Xi == '1':
        x_num = (x_num_ - 2**i)%(x - 1)
    else:
        x_num = (x_num_ + 2**i)%(x + 1)
    if x_num in b:
        ans += b[x_num]
    else:
        b[x_num] = f(x_num) + 1
        ans += b[x_num]
    print(ans)

Submission status: Runtime Error

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in R(V)]
    FromStdin=True if ls==None else False
    for i in R(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

ans=0

def f(x):
    c=0
    while x>0:
        c+=1
        y=bin(x).count('1')
        x%=y
    return c

def f_init(x):
    rt=[0]*3
    p=x.count('1')
    N=len(x)
    for i in range(N):
        if x[i]=='1':
            for j in [-1,0,1]:
                rt[j]+=b[j][N-1-i]
                rt[j]%=p+j
#    show('init',x,rt,1+a[rt[0]])
    ans=[0]*3
    for j in [-1,0,1]:
        ans[j]=1+f(rt[j])
    return rt,ans
    


n=I()
s=S_()

N=2*10**5+10
N=10
N=n
a=[0]*(N+1)

b=[[1]*(N+2) for i in rep(3)]

p=s.count('1')


for i in rep(N):
    #print(x,f(x),bin(x)[2:])
    a[i]=f(i)
    for j in [-1,0,1]:
        b[j][i+1]=(2*b[j][i])%(p+j)

rem,fx=f_init(s)
#show(rem,fx)

for i in rep(n):
    if s[i]=='0':
        j=1
    else:
        j=-1
        #R=rem[0]+b[1][N-1-i]
    t=(rem[j]+b[j][N-1-i])%(p+j)
    ans=a[t]+1 if t!=0 else 1
    #print(ans,'|',t,a[(rem[j]+b[j][N-1-i])%(p+j)],(rem[j]+b[j][N-1-i]),(p+j),'|',(rem[j],b[j][N-1-i],p+j),N,N-1-i)
    if s[i]=='1' and False:
        #R=rem[-1]+b[-1][N-1-i]
        ans=a[(rem[-1]+b[-1][N-1-i])%(p-1)]
    print(ans)

Submission status: Runtime Error

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


def solve(k, cnt):
    S = str(bin(k)).count("1") 
    L = k % S
    if L == 0:
        return 1
    cnt += solve(L,cnt)
    return cnt 

N = int(input())
P = input()
I = P.count("1")
Df = int(P,2)
Ans = [1]
for i in range(1, I+1):
    cnt = 1
    Ans.append(solve(i, cnt)+1)
#print(Ans)

for i in range(N-1):
    if P[i] == "1":
        tmp = Df - 2**(N-i-1)
    else:
        tmp = Df + 2**(N-i-1)    
    cur = str(bin(tmp)).count("1")    
    print(Ans[tmp%cur])
    #print(solve(tmp,cnt))

if P[N-1] == "1":
    tmp = Df - 1
else:
    tmp = Df
cur = str(bin(tmp)).count("1")
print(Ans[tmp%cur]+1)
#print(solve(N,cnt))

Submission status: Runtime Error

Solution code:
# import sys
import math #sqrt,gcd,pi
# import decimal
# import queue # queue
# import bisect
# import heapq # priolity-queue
# import time
# from itertools import product,permutations,\
    # combinations,combinations_with_replacement
# 重複あり順列、順列、組み合わせ、重複あり組み合わせ
# import collections # deque
# from operator import itemgetter,mul
# from fractions import Fraction
# from functools import reduce

mod = int(1e9+7)
# mod = 998244353
INF = 1<<50

def readInt():
    return list(map(int,input().split()))

def main():
    n = int(input())
    x = input()
    count = 0
    i_x = 0
    b = 1
    for i in range(n-1,-1,-1):
        i_x += int(x[i]) * b
        b *= 2
        if x[i]=='1':
            count += 1
    for i in range(n):
        ans = 0
        a = i_x
        if x[i]=='1':
            a -= 2**(n-i-1)
            a = a%(count-1)
            ans += 1
            while a!=0:
                c = a
                cnt = 0
                while c!=1:
                    cnt += c%2
                    c //= 2
                cnt += 1
                a = a%cnt
                ans += 1
        else:
            a += 2**(n-i-1)
            a = a%(count+1)
            ans += 1
            while a!=0:
                c = a
                cnt = 0
                while c!=1:
                    cnt += c%2
                    c //= 2
                cnt += 1
                a = a%cnt
                ans += 1
        print(ans)
    return

if __name__=='__main__':
    main()

Submission status: Runtime Error

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

n = int(input())
xs = list(input())[::-1]

x = 0
for i in range(n):
    if xs[i] == '1':
        x+=2**i

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

memo = {}
memo[0] = 0
memo[1] = 1
memo[2] = 2
def dfs(n, depth=0):
    if n in memo:
        return depth + memo[n]
    else:
        ret = dfs(n%popcount(n), depth+1)
        return ret

ans = []
for i in range(n):
    ans.append(dfs(x^(1<<i)))
for a in ans[::-1]:
    print(a)

Submission status: Runtime Error

Solution code:
import copy
N=int(input())
X=list(input())
c=0
def F(bi):
    global c
    stbi=bin(bi)
    pop=stbi.count("1")
    next=bi%pop
    c += 1
    if next == 0:
        return
    F(next)
    return
for n in range(N):
    c = 0
    x=copy.copy(X)
    if x[n]=="0":
        x[n]="1"
    else:
        x[n]="0"
    x="".join(x)
    F(int(x,2))
    print(c)

Submission status: Runtime Error

Solution code:
import sys
import  math
from heapq import *
import fractions
import bisect
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N=int(input())
X=list(ns())

num_1=0
for i in range(N):
    if(X[i]=='1'):
        num_1+=1

mlist_num_1up=[0]*N
mlist_num_1down=[0]*N
mlist_num_1up[0]=1
mlist_num_1down[0]=1
for i in range(1,N):
    mlist_num_1up[i]=(mlist_num_1up[i-1]*2)%(num_1+1)
    mlist_num_1down[i]=(mlist_num_1down[i-1]*2)%(num_1-1)

mlist_num_1up.reverse()
mlist_num_1down.reverse()

upmod_ori=0
downmod_ori=0
for i in range(N):
    if(X[i]=='1'):
        upmod_ori+=mlist_num_1up[i]
        downmod_ori+=mlist_num_1down[i]


fans=[0]*25
fans[0]=0
fans[1]=1
for i in range(2,25):
    mod=0
    for p in range(5):
        if((i>>p) & 1):
            mod+=1
    fans[i]=fans[i%mod]+1
    
for i in range(N):
    if(X[i]=='1'):
        mod=downmod_ori-mlist_num_1down[i]
        mod%=(num_1-1)
    else:
        mod=upmod_ori+mlist_num_1up[i]
        mod%=(num_1+1)
    mod1=0
    for p in range(20):
        if((mod>>p) & 1):
            mod1+=1
    print(fans[mod1]+1)

Submission status: Runtime Error

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

one_num = sum([1 if x == '1' else 0 for x in X])
x_list = []
for i in range(N):
    if X[i] == '0':
        r = '1'
        sign = 1
    else:
        r = '0'
        sign = -1
    x = X[:i] + r + X[i+1:]
    x_list.append((int('0b' + x, 0), one_num+sign)) 
x_list_raw = x_list[:]
x_list.sort(key=lambda x: x[0])
ans = {}
for x in x_list:
    if x in  ans.keys():
        print(ans[x])
    else:
        flag = True
        v = x[0]
        w = x[1]
        count = 0
        while flag:
            count += 1
            if v % w == 0:
                ans[x[0]] = count
                flag = False
                break
            else:
                v = v % w
                w = sum([int(bin(v)[i]) for i in range(2, len(bin(v)))])
for x in x_list_raw:
    print(ans[x[0]])

Submission status: Runtime Error

Solution code:
from collections import Counter
from copy import deepcopy

N = int(input())
bin_X = input()
dec_X = int(bin_X, 2)
X = list(bin_X)
total = Counter(X)['1']
for i in range(N):
    tmp_total = deepcopy(total)
    if X[i] == '1':
        tmp_total -= 1
        tmp_dec_X = dec_X - 2 ** (N - i - 1)
    else:
        tmp_total += 1
        tmp_dec_X = dec_X + 2 ** (N - i - 1)
    amari = tmp_dec_X % tmp_total
    count = 1
    if amari == 0:
        print(count)
        continue
    while True:
        tmp_total = Counter(bin(amari)[2:])['1']
        amari %= tmp_total
        count += 1
        if amari == 0:
            break
    print(count)

Submission status: Runtime Error

Solution code:
def main():
    n = int(input())
    x = input()
    cnt,num = 0,0
    for i in range(n):
        if x[i] == '1':
            cnt += 1
            num += 2**(n-i-1)
    dp = [0 for i in range(cnt+1)]
    for i in range(1,len(dp)):
        i_ = i
        c = 0
        while i_!=0:
            m = i_%2
            if m==1:
                c += 1
            i_ = i_//2
        dp[i] = 1 + dp[i%c]
    for i in range(n):
        if x[i]=='1':
            c = cnt - 1
            n_ = num - 2**(n-i-1)
        else:
            c = cnt + 1
            n_ = num + 2**(n-i-1)
        m = n_%c
        print(1+dp[m])

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
    memo = {0: 0}
    def fun(num):
        if num in memo: return memo[num]
        tmp = num % bin(num).count("1")
        cnt = 1 + fun(tmp)
        memo[num] = cnt
        return cnt       
        
    N = int(input())
    X = int(input(), 2)
    for i in range(N):        
        xi = X ^ ((2**(N-1)) >> i)
        cnt = fun(xi)
        print(cnt)

Submission status: Runtime Error

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


def f(n):
    p = n % (bin(n).count('1'))
    if p == 0:
        return 1
    else:
        return f(p) + 1


def main(input, print):
    N = int(input())
    X = list(input())
    for i in range(N):
        a = X[:]
        a[i] = "1" if a[i] == "0" else "0"
        b = int(''.join(a), 2)
        print(f(b))


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

Submission status: Runtime Error

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


def f(n):
    tmp = n
    count = 0
    while tmp > 0:
        tmp %= popcount(tmp)
        count += 1
    return count


n = int(input())
# f(0)~f(n)までを計算しておく
F = [f(i) for i in range(n + 2)]
x = input()
pcx = x.count("1")
# xをpcx-1,pcx+1で割ったあまりをそれぞれ計算
a, b = 0, 0
if pcx > 0:
    for i in range(n):
        if x[i] == "1":
            a += pow(2, n - i - 1, pcx - 1)
            a %= (pcx - 1)
            b += pow(2, n - i - 1, pcx + 1)
            b %= (pcx + 1)
else:
    for i in range(n):
        print(1)
    exit()
for i in range(n):
    if x[i] == "1":
        print(1 + f((a - pow(2, n - i - 1, pcx - 1)) % (pcx - 1)))
    else:
        print(1 + f((b + pow(2, n - i - 1, pcx + 1)) % (pcx + 1)))

Submission status: Runtime Error

Solution code:
from numba import njit

N = int(input())
X = list( i for i in str(input()))


def nisin(a, I):
  a = a.copy()
  if a[I] == '0':
    a[I] =  '1'
  elif a[I] == '1':
    a[I] = '0'
    
  return int(''.join(a), 2)

def solve(kazu):
  cnt = 0
  
  while True:
    if kazu == 0:
      break
    cnt += 1
    kazu2 = format(kazu,'b')
    c = kazu2.count('1')
    if kazu % c == 0:
      break
    kazu = kazu % c
  return cnt

@njit
for i in range(N):
  print(solve(nisin(X, i)))

Submission status: Runtime Error

Solution code:
import math
n = int(input())
s= input()
t=s.count("1")
bit=0
for i in range(n-1,-1,-1):
    if s[i]=="1":
        bit+=2**(n-1-i)
a=[0 for i in range(t+4)]
a[0]=0
a[1]=1
a[2]=1

for j in range(3,t+1):
    r=bin(j)[2:].count("1")
    a[j]=1+a[j%r]
print(a)
bit1=bit%(t-1)
bit2=bit%(t+1)
for i in range(n):
    if s[i]=="0":
       
        print(1+a[(bit2+2**(n-1-i))%(t+1)])
    else:

        print(1+a[((bit1-2**((n-1-i))%(t-1))%(t-1))])

Submission status: Runtime Error

Solution code:
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


N = int(input())
X = int(input(),2)



def hoge(d):
    # d = int(X, 2) # in dec
    x = 0
    while d > 0:
        c = popcount(d)
        d = d % c
        x = x + 1        
    return(x)


for i in range(N):
    print(hoge(2 ** (N-i-1) ^ X))

Submission status: Runtime Error

Solution code:
# Q4
import sys

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

N = I()
X = S()

def flip(x):
    if x == "0":
        return "1"
    else:
        return "0"

ans = {0: 0}

for i in range(1, 2 ** len("{:0b}".format(N))+1):
    pop_count = sum([1 if c == "1" else 0 for c in "{:0b}".format(i)])
    ans[i] = ans[i % pop_count] + 1

for i in range(N):
    X_i = X[:i] + flip(X[i]) + X[i+1:]
    pop_count = sum([1 if c == "1" else 0 for c in X_i])
    X_i_num = int(X_i, 2)
    print(ans[X_i_num % pop_count] + 1)

Submission status: Runtime Error

Solution code:
def power(x, y, p) : 
    if y==0: return 1%p
    res = 1     # Initialize result 
  
    # Update x if it is more 
    # than or equal to p 
    x = x % p  
      
    if (x == 0) : 
        return 0
  
    while (y > 0) : 
          
        # If y is odd, multiply 
        # x with result 
        if ((y & 1) == 1) : 
            res = (res * x) % p 
  
        # y must be even now 
        y = y >> 1      # y = y/2 
        x = (x * x) % p 
    return res  

F = [0,1,1]
for i in range(3,100001):
	F += [ 1 + F[i%(bin(i).count('1'))]]
	

n=int(input())
s=input()
ones = s.count('1')
a = ones -1
b = ones
c = ones+1
moda = modb = modc = 0
for i in range(n-1,-1,-1):
	pos = n-1-i
	if s[i]=='1':
		if a>0 : moda = (moda + power(2, pos, a) ) %a
		if b>0 : modb = (modb + power(2, pos, b) ) %b
		modc = (modc + power(2, pos, c) ) %c

for i in range(n):
	if s[i] == '0': #ajout
		add = power(2, n-1-i, c)
		ans = (modc + add) % c
		# ~ print("i",i, "add",add,"ans",ans)
		print(F[ans]+1)
	else: # retrait
		if a<=0: print(0)
		else:
			sub = power(2, n-1-i, a)
			ans = (moda - sub) % a
			print(F[ans]+1)