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:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
#from collections import deque

def sum_count(arr):
    mem = arr[:]
    while True:
        if len(mem) == 1:break
        tmp = []
        while True:
            if len(mem) == 1:
                tmp.append(mem[-1])
                mem = tmp[:]
                break
            if len(mem) == 0:
                mem = tmp[:]
                break
            x1, x2 = mem.pop(), mem.pop()
            tmp.append(int(x1) + int(x2))

    return int(mem[0])

def run():
    N = int(input())
    X = list(input())[::-1]
    lis_bf = []
    lis_af = []
    count1 = sum_count(X)
    sum_val_bf, sum_val_af = 0, 0
    for i in range(N):
        tmp_bf, tmp_af = 0,0
        if int(X[i]):
            tmp_bf = pow(2, i , count1-1)
            tmp_af = pow(2, i, count1+1)
        lis_bf.append(tmp_bf)
        lis_af.append(tmp_af)
        sum_val_bf += tmp_bf
        sum_val_bf %= count1-1
        sum_val_af += tmp_af
        sum_val_af %= count1 + 1

    for i in list(range(N))[::-1]:
        ans = 0
        if X[i] == '1':
            next_val = (sum_val_bf - lis_bf[i]) % (count1-1)
        else:
            next_val = (sum_val_af + pow(2, i, count1+1)) % (count1+1)
        #print(next_val)
        ans += 1
        #print(f'i : {i}, next_val : {next_val}')
        while True:
            if next_val == 0:break
            val = next_val
            count_n = sum_count(list(bin(val)[2:]))
            next_val = val % count_n
            ans += 1
            #print(f'next_val : {next_val}')
        print(ans)


if __name__ == "__main__":
    run()

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

n=int(input())
xs=input()
xj=xs.count("1")

x=int(xs,2)
xip=x%(xj+1)
xim=x%(xj-1)

i1=1<<n
for i in range(n-1,-1,-1):
    i1=i1>>1
    xi=x^i1
    if xi==0:
        print(0)
        continue
    if xs[n-1-i]=="0":
        pxi=xj+1
#        xi=(xip+i1%pxi)%pxi
        xi=(xip+i1)%pxi
    else:
        pxi=xj-1
#        xi=(xim-i1%pxi)%pxi
        xi=(xim-i1)%pxi
#    xi=xi%pxi
    if xi==0:
        print(1)
        continue
    icnt=1
    while xi>0:
#        print("i",i,"xi",xi,"icnt",icnt)
        icnt+=1
        xi=xi%(bin(xi).count("1"))
    print(icnt)

Submission status: Runtime Error

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

def f(n):
    cnt = 0
    while n>0:
        n = n%popcnt(n)
        cnt += 1
    return cnt

def solve(X):
    Y = int(X, 2)
    c = X.count("1")
    if c == 0:
        return 0
    m, p = c-1, c+1
    Ym, Yp = Y%m, Y%p
    for i in range(N):
        if X[i] == "1":
            Y = (Ym - pow(2,N-i-1,m))%m
        else:
            Y = (Yp + pow(2,N-i-1,p))%p
        print(f(Y) + 1)

N = int(input())
solve(input())

Submission status: Runtime Error

Solution code:
from sys import stdin

def mpow(n, p, mod):
    if mod == 0:
        return 0
    r = 1
    while p > 0:
        if p & 1 == 1:
            r = r * n % mod
        n = n * n % mod
        p >>= 1
    return r
def popcount(u):
    if u == 0:
        return 0
    a = u % bin(u).count('1')
    return 1 + popcount(a)
def main():
    input = stdin.readline
    n = int(input())
    x = '0b' + input()
    xs = int(x, 0)
    xc = x.count('1')
    xsp = mpow(xs, 1, xc + 1)
    xsm = mpow(xs, 1, xc - 1)
    for i in range(2, n + 2):
        if x[i] == '0':
            y = xsp + mpow(2, n - i + 1, xc + 1)
            y = mpow(y, 1, xc + 1)
        elif xc == 1:
            print(0)
            next
        else:
            y = xsm - mpow(2, n - i + 1, xc - 1)
            y = mpow(y, 1, xc - 1)
        print(popcount(y) + 1)            
main()

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

n=int(input())
xs=input()
xj=xs.count("1")

x=int(xs,2)
xip=x%(xj+1)
xim=x%(xj-1)

i1=1<<n
for i in range(n-1,-1,-1):
    i1=i1>>1
    xi=x^i1
    if xi==0:
        print(0)
        continue
    if xs[n-1-i]=="0":
        pxi=xj+1
        xi=(xip+i1%pxi)%pxi
    else:
        pxi=xj-1
        xi=(xim-i1%pxi)%pxi
#    xi=xi%pxi
    if xi==0:
        print(1)
        continue
    icnt=1
    while xi>0:
#        print("i",i,"xi",xi,"icnt",icnt)
        icnt+=1
        xi=xi%bin(xi).count("1")
    print(icnt)

Submission status: Runtime Error

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

POPCOUNT_TABLE16 = [0] * 2**16
for index in range(len(POPCOUNT_TABLE16)):
  POPCOUNT_TABLE16[index] = (index & 1) + POPCOUNT_TABLE16[index >> 1]

def popcnt5(v):
  return (POPCOUNT_TABLE16[ v        & 0xffff] +
          POPCOUNT_TABLE16[(v >> 16) & 0xffff] +
          POPCOUNT_TABLE16[(v >> 32) & 0xffff] +
          POPCOUNT_TABLE16[(v >> 48)         ])
def f(n):
  ans = 0
  while n:
    popcount = popcnt5(n)
    n = n % popcount
    ans += 1
  return ans

z = int(x, 2)
for i in range(n):
  y = z ^ (1 << (n - i - 1))
  print(f(y))

Submission status: Runtime Error

Solution code:
import math


def f(n):
    pop = 0
    ntemp = n
    for i in range(int(math.log2(n)) + 1):
        pop += ntemp % 2
        ntemp //= 2
    return n % pop


n = int(input())
S = input()
popcount = 0
for i in range(n):
    popcount += int(S[i])
Sint = int(S, 2)
remminus = Sint % (popcount - 1)
remplus = Sint % (popcount + 1)

# 1,2,4,...の余りのリストを準備
remlistminus = []
remlistplus = []
temp = 1
for i in range(n):
    remlistminus.append(temp)
    temp = (temp * 2) % (popcount - 1)
temp = 1
for i in range(n):
    remlistplus.append(temp)
    temp = (temp * 2) % (popcount + 1)
remlistminus.reverse()
remlistplus.reverse()

ans = []
for i in range(n):
    count = 1
    if S[i] == '0':
        rem = (remplus + remlistplus[i]) % (popcount + 1)
        while rem > 0:
            rem = f(rem)
            count += 1
    else:
        rem = (remminus - remlistminus[i]) % (popcount - 1)
        while rem > 0:
            rem = f(rem)
            count += 1
    ans.append(count)
for i in range(n):
    print(ans[i])

Submission status: Runtime Error

Solution code:
import math


def f(n):
    pop = 0
    ntemp = n
    for i in range(int(math.log2(n)) + 1):
        pop += ntemp % 2
        ntemp //= 2
    return n % pop


n = int(input())
S = input()
popcount = 0
for i in range(n):
    popcount += int(S[i])
Sint = int(S, 2)
remminus = Sint % (popcount - 1)
remplus = Sint % (popcount + 1)

# 1,2,4,...の余りのリストを準備
remlistminus = []
remlistplus = []
temp = 1
for i in range(n):
    remlistminus.append(temp)
    temp = (temp * 2) % (popcount - 1)
temp = 1
for i in range(n):
    remlistplus.append(temp)
    temp = (temp * 2) % (popcount + 1)
remlistminus.reverse()
remlistplus.reverse()
print(remlistminus)
print(remlistplus)

ans = []
for i in range(n):
    count = 1
    if S[i] == '0':
        rem = (remplus + remlistplus[i]) % (popcount + 1)
        while rem > 0:
            rem = f(rem)
            count += 1
    else:
        rem = (remminus - remlistminus[i]) % (popcount - 1)
        while rem > 0:
            rem = f(rem)
            count += 1
    ans.append(count)
for i in range(n):
    print(ans[i])

Submission status: Runtime Error

Solution code:
N=int(input())
X=input()
c=X.count('1')
r1=int(X,2)%(c-1)
r2=int(X,2)%(c+1)
d=[0]*(N+1)
for i in range(N):
    d[i+1]=d[(i+1)%bin(i+1).count('1')]+1
for i in range(N):
    if X[i]=='0':
        n=(r2+pow(2,N-i-1,c+1))%(c+1)
    else:
        if c==1:
            print(0)
            continue
        n=(r1-pow(2,N-i-1,c-1))%(c-1)
    print(d[n]+1)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(3000)
N = int(input())
X = input()
zero_pop = X.count('1') + 1
one_pop = X.count('1') - 1
one_mod, zero_mod = 0, 0

for b in X:
    if one_pop != 0:
        one_mod = (one_mod * 2 + int(b)) % one_pop
    zero_mod = (zero_mod * 2 + int(b)) % zero_pop

pop = {0:0}
def popcount(n):
    if n in pop:
        return pop[n]
    pop[n] = popcount(n // 2) + n % 2
    return pop[n]
memo = {0:0}
def f_count(n):
    if n in memo:
        return memo[n]
    memo[n] = f_count(n % popcount(n)) + 1
    return memo[n]
one_p = {0:1}
def one_pow(n):
    if n in one_p:
        return one_p[n]
    one_p[n] = one_pow(n - 1) * 2 % one_pop
    return one_p[n]
zero_p = {0:1}
def zero_pow(n):
    if n in zero_p:
        return zero_p[n]
    zero_p[n] = zero_pow(n - 1) * 2 % zero_pop
    return zero_p[n]
for i in range(N):
    if X[i] == '1' and one_pop == 0:
        print(0)
        continue
    if X[i] == '1':
        x = one_mod
        x -= one_pow(N-1-i)
        x %= one_pop
    elif X[i] == '0':
        x = zero_mod
        x += zero_pow(N-1-i)
        x %= zero_pop
    
    print(f_count(x) + 1)

Submission status: Runtime Error

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

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

x = int(X, 2)
pcx = X.count("1")
pc1 = x % (pcx - 1) if pcx > 1 else 0
pc2 = x % (pcx + 1)


for i in range(N):
    if X[i] == '0':
        X_next = pc2 + pow(2,N-1-i,pcx+1)
        X_pop_next = pcx + 1
    else:
        X_next = pc1 - pow(2,N-1-i,pcx-1)
        X_pop_next = pcx - 1
        
    if X_pop_next == 0:
        print(0)
        continue
        
    X_next = X_next % X_pop_next
    ans = 1
    
    while X_next != 0:
        X_next = X_next % popcount(X_next)
        ans += 1
    
    print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

def popcount(n):
  count = 0
  while n != 0:
    if n%2 == 1:
      count += 1
    n = n >> 1
  return count


N = int(input())
X = int(input(),2)
XX = np.zeros(N,dtype = int)
Pop = np.zeros(2**N,dtype = int)
ans = np.zeros(N,dtype = int)
for i in range(1,N+1):
  a = (X >> (i-1))%2
  if a == 0:
    XX[N-i] = X + 2**(i-1)
  else:
    XX[N-i] = X - 2**(i-1)

for i in reversed(range(N)):
  count_XX = 0
  while XX[i] > 0:
    if Pop[XX[i]] == 0:
      Pop[XX[i]] = popcount(XX[i])
    XX[i] = XX[i] % Pop[XX[i]]
    #print(XX)
    count_XX += 1
  ans[i] = count_XX

for i in range(N):
  print(ans[i])

Submission status: Runtime Error

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

original_pop_count = x.count('1')
one_pop_count = original_pop_count - 1
zero_pop_count = original_pop_count + 1

one_mod = 0
zero_mod = 0
for b in x:
    if one_pop_count != 0:
        one_mod = (one_mod *2 + int(b))%one_pop_count
        zero_mod = (zero_mod *2 + int(b))%zero_pop_count

f = [0]*220001
pop_count = [0]*220000
for i in range(1, 220000):
    pop_count[i] = pop_count[i//2] + i%2
    f[i] = f[i%pop_count[i]] + 1

one_pow2 = [1]*220000
zero_pow2 = [1]*220000
for i in range(1, 220001):
    if one_pop_count != 0:
        one_pow2[i] = one_pow2[i-1] *2 % one_pop_count
        zero_pow2[i] = zero_pow2[i-1] *2 % zero_pop_count

for i in range(n-1, -1, -1):
    if x[n-1-i] == '1':
        if one_pop_count != 0:
            nxt = one_mod
            nxt -= one_pow2[i]
            nxt %= one_pop_count
            print(f[nxt]+1)
        else:
            print(0)

    if x[n-1-i] == '0':
        nxt = zero_mod
        nxt += zero_pow2[i]
        nxt %= zero_pop_count
        print(f[nxt]+1)

Submission status: Runtime Error

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

original_pop_count = x.count('1')
one_pop_count = original_pop_count - 1
zero_pop_count = original_pop_count + 1

one_mod = 0
zero_mod = 0
for b in x:
    if one_pop_count != 0
        one_mod = (one_mod *2 + int(b))%one_pop_count
        zero_mod = (zero_mod *2 + int(b))%zero_pop_count

f = [0]*220001
pop_count = [0]*220000
for i in range(1, 220000):
    pop_count[i] = pop_count[i//2] + i%2
    f[i] = f[i%pop_count[i]] + 1

one_pow2 = [1]*220000
zero_pow2 = [1]*220000
for i in range(1, 220001):
    if one_pop_count != 0
        one_pow2[i] = one_pow2[i-1] *2 % one_pop_count
        zero_pow2[i] = zero_pow2[i-1] *2 % zero_pop_count

for i in range(n-1, -1, -1):
    if x[n-1-i] == '1':
        if one_pop_count != 0
            nxt = one_mod
            nxt -= one_pow2[i]
            nxt %= one_pop_count
            print(f[nxt]+1)
        else:
            print(0)

    if x[n-1-i] == '0':
        nxt = zero_mod
        nxt += zero_pow2[i]
        nxt %= zero_pop_count
        print(f[nxt]+1)

Submission status: Runtime Error

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

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

tmp_pop_X = X.count('1')
X_tmp = int(X,2)
pc1 = X_tmp % (tmp_pop_X - 1) if tmp_pop_X > 1 else 0
pc2 = X_tmp % (tmp_pop_X + 1)

for i in range(N):
    if X[i] == '0':
        X_next = pc2 + pow(2,N-1-i,tmp_pop_X + 1)
        X_pop_next = tmp_pop_X + 1
    else:
        X_next = pc1 - pow(2,N-1-i,tmp_pop_X - 1)
        X_pop_next = tmp_pop_X - 1
        
    if X_pop_next == 0:
        print(0)
        continue
        
    X_next = X_next % X_pop_next
    ans = 1
    
    while X_next != 0:
        X_next = X_next % popcount(X_next)
        ans += 1
    
    print(ans)

Submission status: Runtime Error

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

original_pop_count = x.count('1')
one_pop_count = original_pop_count - 1
zero_pop_count = original_pop_count + 1

one_mod = 0
zero_mod = 0
for b in x:
    one_mod = (one_mod *2 + int(b))%one_pop_count
    zero_mod = (zero_mod *2 + int(b))%zero_pop_count

f = [0]*220001
pop_count = [0]*220001
for i in range(1, 220001):
    pop_count[i] = pop_count[i//2] + i%2
    f[i] = f[i%pop_count[i]] + 1

one_pow2 = [1]*220001
zero_pow2 = [1]*220001
for i in range(1, 220001):
    one_pow2[i] = one_pow2[i-1] *2 % one_pop_count
    zero_pow2[i] = zero_pow2[i-1] *2 % zero_pop_count

for i in range(n-1, -1, -1):
    if x[n-1-i] == '1':
        nxt = one_mod
        nxt -= one_pow2[i]
        nxt %= one_pop_count
        print(f[nxt]+1)

    if x[n-1-i] == '0':
        nxt = zero_mod
        nxt += zero_pow2[i]
        nxt %= zero_pop_count
        print(f[nxt]+1)

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
zero_pop = X.count('1') + 1
one_pop = X.count('1') - 1
one_mod, zero_mod = 0, 0

for b in X:
    if one_pop != 0:
        one_mod = (one_mod * 2 + int(b)) % one_pop
    zero_mod = (zero_mod * 2 + int(b)) % zero_pop

pop = {0:0}
def popcount(n):
    if n in pop:
        return pop[n]
    pop[n] = popcount(n // 2) + n % 2
    return pop[n]
memo = {0:0}
def f_count(n):
    if n in memo:
        return memo[n]
    memo[n] = f_count(n % popcount(n)) + 1
    return memo[n]
one_p = {0:1}
def one_pow(n):
    if n in one_p:
        return one_p[n]
    one_p[n] = one_pow(n - 1) * 2 % one_pop
    return one_p[n]
zero_p = {0:1}
def zero_pow(n):
    if n in zero_p:
        return zero_p[n]
    zero_p[n] = zero_pow(n - 1) * 2 % zero_pop
    return zero_p[n]
for i in range(N):
    if X[i] == '1' and one_pop == 0:
        print(0)
        continue
    if X[i] == '1':
        x = one_mod
        x -= one_pow(N-1-i)
        x %= one_pop
    elif X[i] == '0':
        x = zero_mod
        x += zero_pow(N-1-i)
        x %= zero_pop
    
    print(f_count(x) + 1)

Submission status: Runtime Error

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

original_pop_count = x.count('1')
one_pop_count = original_pop_count - 1
zero_pop_count = original_pop_count + 1

one_mod = 0
zero_mod = 0
for b in x:
    one_mod = (one_mod *2 + int(b))%one_pop_count
    zero_mod = (zero_mod *2 + int(b))%zero_pop_count

f = [0]*220000
pop_count = [0]*220000
for i in range(1, 220000):
    pop_count[i] = pop_count[i//2] + i%2
    f[i] = f[i%pop_count[i]] + 1

one_pow2 = [1]*220000
zero_pow2 = [1]*220000
for i in range(1, 220000):
    one_pow2[i] = one_pow2[i-1] *2 % one_pop_count
    zero_pow2[i] = zero_pow2[i-1] *2 % zero_pop_count

for i in range(n-1, -1, -1):
    if x[n-1-i] == '1':
        nxt = one_mod
        nxt -= one_pow2[i]
        nxt %= one_pop_count
        print(f[nxt]+1)

    if x[n-1-i] == '0':
        nxt = zero_mod
        nxt += zero_pow2[i]
        nxt %= zero_pop_count
        print(f[nxt]+1)

Submission status: Runtime Error

Solution code:
# 2125
# 方針．f(n)を求めるのがlog(N)で終わりそうだから普通に素直に実装すればいいのでは？
# ただし最初だけは別に実装する必要がある
N = int(input())
X = list(input())

# i番目のビットを反転させて,
# やってることは似てるはずなのになんかうまく行かない
dic={}
bn00 = X.count('1')
x00 = int(''.join(X),2)
aa = x00 % (bn00+1)
bb = x00 % (bn00-1)
for i in range(N):
    # ちゃんともとに戻してね，ということで本のビット
    b = int(X[i]) & 1
    bn = b ^ 1
    if bn:
        bn0 = bn00 + 1
        x0 = aa
    else:
        bn0 = bn00 - 1
        x0 = bb
    if bn0==0: # ビットが全く立っていないつまり0の時，0%0はエラーを起こすので，n%0もエラーを起こす
        print(0)
        continue
    if b: # もとのビットが立っている場合は減らす，ここの計算量が一番重いので計算量を削減してみる
        xi = x0 - b * pow(2,N-1-i,bn0)
    if bn:
        xi = x0 + bn * pow(2, N - 1 - i, bn0)
    xi %= bn0
    num = xi
    count = 1
    while num > 0:
        p = format(num,'b').count('1') # 10進数を２進数にかえるなら，これがいいのかも,int(str(i),2)を使うっていう手もあるけど周りくどい
        num = num % p
        count += 1
    print(count)

Submission status: Runtime Error

Solution code:
import numpy as np

def popcount(n):
  count = 0
  while n != 0:
    if n%2 == 1:
      count += 1
    n = n >> 1
  return count


N = int(input())
X = int(input(),2)
XX = np.zeros(N,dtype = int)
Pop = np.zeros(2**N,dtype = int)
ans = np.zeros(N,dtype = int)
for i in range(1,N+1):
  a = (X >> (i-1))%2
  if a == 0:
    XX[N-i] = X + 2**(i-1)
  else:
    XX[N-i] = X - 2**(i-1)

for i in range(N):
  count_XX = 0
  while XX[i] > 0:
    if ans[i] > 0:
      count_XX += ans[i]
      XX[i] = 0
      #print("処理")
    else:
      if Pop[XX[i]] == 0:
        Pop[XX[i]] = popcount(XX[i])
      XX[i] = XX[i] % Pop[XX[i]]
      #print(XX)
      count_XX += 1
  ans[i] = count_XX
  print(ans[i])

Submission status: Runtime Error

Solution code:
import numpy as np

def popcount(n):
  count = 0
  while n != 0:
    if n%2 == 1:
      count += 1
    n = n >> 1
  return count


N = int(input())
X = int(input(),2)
XX = np.zeros(N,dtype = int)
ans = np.zeros(N,dtype = int)
for i in range(1,N+1):
  a = (X >> (i-1))%2
  if a == 0:
    XX[N-i] = X + 2**(i-1)
  else:
    XX[N-i] = X - 2**(i-1)

for i in range(N):
  count_XX = 0
  a = N-1
  while a>0:
    if ans[a] > 0:
      count_XX += ans[a]
      a = 0
      #print("処理")
    else:
      a = XX[i] % popcount(XX[i])
      XX[i] = a
      count_XX += 1
  ans[i] = count_XX
  print(ans[i])

Submission status: Runtime Error

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

c = S.count('1')
m = int('0B'+S, 0)
memo = [0]*(N+1)

def calc(a):
    global ans, memo
    if a == 0: return ans
    ans += 1
    if memo[a] != 0:
        b = memo[a]
    else:
        b = bin(a).count('1')
        memo[a] = b
    return calc(a%b)
    
for i in range(N):
    if S[i] == '1': b = c - 1
    else: b = c + 1
    if S[i] == '1':
        a = m - 2**(N - 1 - i)
    else: a = m + 2**(N - 1 - i)
    
    ans = 1
    print(calc(a%b))

Submission status: Runtime Error

Solution code:
import numpy as np

def popcount(n):
  count = 0
  while n != 0:
    if n%2 == 1:
      count += 1
    n = n >> 1
  return count


N = int(input())
X = int(input(),2)
XX = np.zeros(N,dtype = int)
ans = np.zeros(N,dtype = int)
for i in range(1,N+1):
  a = (X >> (i-1))%2
  if a == 0:
    XX[N-i] = X + 2**(i-1)
  else:
    XX[N-i] = X - 2**(i-1)

for i in range(N):
  count_XX = 0
  a = 1
  while a>0:
    if ans[i] > 0:
      count_XX += ans[i]
      a = 0
    else:
      a = XX[i] % popcount(XX[i])
      XX[i] = a
      count_XX += 1
  ans[i] = count_XX
  print(ans[i])

Submission status: Runtime Error

Solution code:
import numpy as np

def popcount(n):
  count = 0
  while n != 0:
    if n%2 == 1:
      count += 1
    n = n >> 1
  return count


N = int(input())
X = int(input(),2)
XX = np.zeros(N,dtype = int)
ans = np.zeros(N,dtype = int)
for i in range(1,N+1):
  a = (X >> (i-1))%2
  if a == 0:
    XX[N-i] = X + 2**(i-1)
  else:
    XX[N-i] = X - 2**(i-1)

for i in range(N):
  count_XX = 0
  a = 1
  while a>0:
    if ans[i] > 0:
      count_XX += ans[i]
    else:
      a = XX[i] % popcount(XX[i])
      XX[i] = a
      count_XX += 1
  ans[i] = count_XX
  print(ans[i])

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

n=int(input())
xs=input()
#xk=list(map(int,list(xs)))
xj=xs.count("1")

x=int(xs,2)

xip=x%(xj+1)
xim=x%(xj-1)

nmax=2*10**5
xmem=[0]*(nmax+1)
for i in range(n-1,-1,-1):
#    xi=x^(1<<i)
    pxi=xj
    if xs[n-1-i]=="0":
        pxi=pxi+1
#        xi=xi%pxi
#        print("i",i,"xip",xip,"pxi",pxi)
        xi=(xip+(1<<i)%pxi)%pxi
    else:
        pxi=pxi-1
#        print("i",i,"xip",xip,"pxi",pxi)
        xi=(xim-(1<<i)%pxi)%pxi
#    if xi==0:
    if xi==(1<<i):
        print(0)
    else:
#        xi=xi%pxi
        if xi==0:
            print(1)
        else:
            if xi<nmax and xmem[xi]>0:
                print(xmem[xi])
            else:
                xii=xi
                icnt=1
                while xi>0:
                    icnt+=1
                    xi=xi%(bin(xi).count("1"))
                xmem[xii]=icnt
                print(icnt)

Submission status: Runtime Error

Solution code:
import numpy as np

def popcount(n):
  count = 0
  while n != 0:
    if n%2 == 1:
      count += 1
    n = n >> 1
  return count


N = int(input())
X = int(input(),2)
XX = np.zeros(N,dtype = int)
ans = np.zeros(N,dtype = int)
for i in range(1,N+1):
  a = (X >> (i-1))%2
  if a == 0:
    XX[N-i] = X + 2**(i-1)
  else:
    XX[N-i] = X - 2**(i-1)

for i in range(N):
  count_XX = 0
  a = 1
  while a>0:
    a = XX[i] % popcount(XX[i])
    XX[i] = a
    count_XX += 1
  ans[i] = count_XX
  print(ans[i])

Submission status: Runtime Error

Solution code:
import numpy as np

def popcount(n):
  count = 0
  while n != 0:
    if n%2 == 1:
      count += 1
    n = n >> 1
  return count


N = int(input())
X = int(input(),2)
XX = np.zeros(N,dtype = int)
ans = np.zeros(N,dtype = int)
for i in range(1,N+1):
  a = (X >> (i-1))%2
  if a == 0:
    XX[N-i] = X + 2**(i-1)
  else:
    XX[N-i] = X - 2**(i-1)

for i in range(N):
  count_XX = 0
  a = 1
  while a:
    a = XX[i] % popcount(XX[i])
    XX[i] = a
    count_XX += 1
  ans[i] = count_XX
  print(ans[i])

Submission status: Runtime Error

Solution code:
n=int(input())
x=list(input())
def str2int(z):
  flag=1
  a=0
  for i in reversed(x):
    if i=='1':a+=flag
    flag*=2
  return a
 
popc=x.count('1')
x=str2int(x)
fl_1=x%(popc-1)
fl_0=x%(popc+1)
cc=[]
for i in range(n):
  if ((x>>i)&1):
    mod=(fl_1-(2**i)%(popc-1))%(popc-1)
  else:mod=(fl_0+(2**i)%(popc+1))%(popc+1)
  #print('mod : %s'%mod)
  cnt=1
  while mod!=0:
    pp=bin(mod).count("1")
    mod%=pp
    cnt+=1
  cc.append(cnt)
  
for c in reversed(cc):
  print(c)

Submission status: Runtime Error

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

for i in range(N):
  X_list = list(X)
  a = 1
  count = 0
  if X_list[i]=='0':
    X_list[i] = '1'
  else:
    X_list[i] = '0'
  while a!=0:
    s = ''.join(X_list)
    num_1 = s.count('1')
    s_10 = int(s,2)
    a = s_10 % num_1
    a_2 = bin(a)
    a_str = format(a, 'b')
    X_list = list(a_str)
    count += 1
  print(count)

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
x_popcnt = x.count('1')
one_popcnt = x_popcnt - 1
zero_popcnt = x_popcnt + 1

one_mod = 0
zero_mod = 0
for b in x:
    if one_popcnt != 0:
        one_mod = (one_mod*2 + int(b)) % one_popcnt
    zero_mod = (zero_mod*2 + int(b)) % zero_popcnt

f = [0]*220000
popcnt = [0]*220000
for i in range(1, 220000):
    popcnt[i] = popcnt[i//2] + i % 2
    f[i] = f[i % popcnt[i]] + 1

onepow2 = [1]*220000
for i in range(1, 220000):
    onepow2[i] = 2*onepow2[i-1] % one_popcnt
zeropow2 = [1]*220000
for i in range(1, 220000):
    zeropow2[i] = 2*zeropow2[i-1] % zero_popcnt
for i in range(n-1, -1, -1):
    if x[n-1-i] == '1':
        if one_popcnt != 0:
            nxt = one_mod
            nxt -= onepow2[i]
            nxt %= one_popcnt
            print(f[nxt]+1)
        else:
            print(0)
    if x[n-1-i] == '0':
        nxt = zero_mod
        nxt += zeropow2[i]
        nxt %= zero_popcnt
        print(f[nxt]+1)

Submission status: Runtime Error

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

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

x_pop = popcount(x)
for i in reversed(range(0,n)):
    bit = x&(1<<i)
    if bit:
        tmp_pop = x_pop - 1
    else:
        tmp_pop = x_pop + 1
    tmp = bit % tmp_pop
    if tmp == 0:
        print(0)
        continue
    if tmp < 0:
        print(1)
        continue
    cnt = 2
    tmp = tmp % popcount(tmp)
    while tmp > 0:
        cnt += 1
        tmp %= popcount(tmp)
    print(cnt)

Submission status: Runtime Error

Solution code:
import os
import sys
from collections import defaultdict, Counter
from itertools import product, permutations,combinations, accumulate
from operator import itemgetter
from bisect import bisect_left,bisect
from heapq import heappop,heappush,heapify
from math import ceil, floor, sqrt
from copy import deepcopy

def Count_num(list_j):
    count = list_j.count("1")
    str_j = ''.join(list_j)
    num = int(str(str_j),2)
    return count, num

def main():
    n = int(input())
    x = input()
    ans_list = [1]*(2*(10**5))
    

    for i in range(n):
        j = list(x)
        
        if x[i] == "1":
            j[i] = '0'
        else:
            j[i] = '1'

        count_num = 0
        count,num = Count_num(j)
        
        while (num%count != 0):
            count, num = Count_num(list(bin(num%count)[2:]))
            count_num += 1

        ans_list[i] += count_num
        
    for i in range(n):
        print(ans_list[i])

if __name__ == '__main__':
	main()

Submission status: Runtime Error

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

# 元のpopcount
original_pop_count = x.count('1')
# 反転して-1count
one_pop_count = original_pop_count - 1
# 反転して+1count
zero_pop_count = original_pop_count + 1
 
# ±1それぞれにおける余り
one_mod = int(x, 2) % one_pop_count
zero_mod = int(x, 2) % zero_pop_count
 
#f の前計算
f = [0] * 220000
pop_count = [0] * 220000
for i in range(1, 220000):
    pop_count[i] = pop_count[i//2] + i % 2
    f[i] = f[i % pop_count[i]] + 1
 
# pow2 の前計算
one_pow2 = [1] * 220000
zero_pow2 = [1] * 220000
for i in range(1, 220000):
    if one_pop_count != 0:
        one_pow2[i] = one_pow2[i-1] * 2 % one_pop_count
    zero_pow2[i] = zero_pow2[i-1] * 2 % zero_pop_count
    
# n-1, n-2, ,, 0
for i in range(n-1, -1, -1):
    if x[n-1-i] == '1':
        if one_pop_count != 0:
            nxt = one_mod
            nxt -= one_pow2[i] #2^n-i-iを引く
            nxt %= one_pop_count
            print(f[nxt] + 1)
        else:
            print(0)
    if x[n-1-i] == '0':
        nxt = zero_mod
        nxt += zero_pow2[i]　#2^n-i-iを引く
        nxt %= zero_pop_count
        print(f[nxt] + 1)

Submission status: Runtime Error

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

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

tmp_pop_X = X.count('1')

for i in range(N):
    if X[i] == '0':
        X_next = int(X,2) + 2**(N-1-i)
        X_pop_next = tmp_pop_X + 1
    else:
        X_next = int(X,2) - 2**(N-1-i)
        X_pop_next = tmp_pop_X - 1
        
    X_next = X_next % X_pop_next
    ans = 1
    
    while X_next != 0:
        X_next = X_next % popcount(X_next)
        ans += 1
        
    print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
x_popcnt = x.count('1')
one_popcnt = x_popcnt - 1
zero_popcnt = x_popcnt + 1

one_mod = 0
zero_mod = 0
for b in x:
    one_mod = (one_mod*2 + int(b)) % one_popcnt
    zero_mod = (zero_mod*2 + int(b)) % zero_popcnt

f = [0]*220000
popcnt = [0]*220000
for i in range(1, 220000):
    popcnt[i] = popcnt[i//2] + i % 2
    f[i] = f[i % popcnt[i]] + 1

for i in range(n-1, -1, -1):
    if x[n-1-i] == '1':
        nxt = one_mod
        nxt -= pow(2, i, one_popcnt)
        nxt %= one_popcnt
        print(f[nxt]+1)
    if x[n-1-i] == '0':
        nxt = zero_mod
        nxt += pow(2, i, zero_popcnt)
        nxt %= zero_popcnt
        print(f[nxt]+1)

Submission status: Runtime Error

Solution code:
def readinput():
    n=int(input())
    x=input()
    return n,x

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

def f(x):
    #print('f(x), x: {}'.format(x))
    if x==0:
        return 0
    else:
        ans=f(x%popcount(x))+1
        #print(ans)
        return ans    

def main(n,x):
    m=x.count('1')
    #print('m: {}'.format(m))
    xint=int(x,2)
    #print('xint: {}'.format(xint))
    xmodm1=xint%(m-1)
    xmodp1=xint%(m+1)
    ans=[]
    b=2**(n-1)
    for i in range(n):
        if x[i]=='1':
            if m==1:
                ans.append(0)
            else:
                xx=( xmodm1 + (m-1) -b%(m-1) )%(m-1)
                ans.append(f(xx)+1)
        else:
            xx=( xmodp1 + b%(m+1) )%(m+1)
            ans.append(f(xx)+1)
        b=b//2
    return ans

if __name__=='__main__':
    n,x=readinput()
    ans=main(n,x)
    for a in ans:
        print(a)

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
n = sum([(2 ** i) * int(x) for i,x in enumerate(reversed(X))])

from functools import lru_cache

@lru_cache(maxsize=None)
def popcount(x):
    return bin(x)[2:].count('1')
    
@lru_cache(maxsize=None)
def f(x):
    cnt = 1
    while x%popcount(x):
        cnt += 1
        x %= popcount(x)
    return cnt

for i in reversed(range(N)):
    x = n ^ (1<<i)
    print(f(x))