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
sys.setrecursionlimit(10000)
n = int(input())
X = input()
pc = X.count('1')
nx = int(X, 2)

dp = [-1] * ((2*10**5)+1)
pcs = [-1] * ((2*10**5)+1)
pcs[0] = 0
pcs[1] = 1
pcs[2] = 1
dp[0] = 0
def f(n):
    if dp[n] >= 0:
        return dp[n]
    if pcs[n] >= 0:
        pc = pcs[n]
    else:
        pc = bin(n).count('1')
        pcs[n] = pc
    nn = n%pc
    d = f(nn)+1
    dp[n] = d
    return d

tmp = pow(2, n)
for i in range(n-1, -1, -1):
    # ibit目を反転させる # つまりi**2を引く
    tmp //= 2
    if (nx>>i)&1:
        r = (nx-tmp)%(pc-1)
    else:
        r = (nx+tmp)%(pc+1)

    if r > 0:
        print(f(r) + 1)
    else:
        print(1)

Submission status: Runtime Error

Solution code:

def f(n):
  cnt = 0
  while n:
      cnt += 1
      n = n % bin(n).count('1')

  return cnt

def main():
  n = int(input())
  src = input()
  base = int(src, 2)
  base_cnt = src.count('1')

  basep = base % (base_cnt + 1)
  basem = base % (base_cnt - 1)

  for i, s in enumerate(src):
    i = n - 1 - i
    num = None

    if s == '0':
      mod = base_cnt + 1
      num = (basep + pow(2, i, mod)) % mod
    elif base_cnt > 1:
      mod = base_cnt - 1
      num = (basem - pow(2, i, mod)) % mod
    else:
      print(0)
      continue

    print(1 + f(num))


main()

Submission status: Runtime Error

Solution code:


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

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

def solve(X):
    for i in reversed(range(N)):
        if [N-1-i] == 0:
            print(0)
        else:
            K = X ^ (1 << i)
            K2 = K%P[N-1-i]
            print(f(K2) + 1)




N = int(input())
X = input()
X = X.zfill(N)
count_1 = X.count("1")

P = [0]*N
for i in range(N):
    if X[i] == "1":
        P[i] = count_1 - 1
    else:
        P[i] = count_1 + 1
Y = int(X,2)

solve(Y)

Submission status: Runtime Error

Solution code:
import itertools
import decimal
import math
import collections
import sys
#input = sys.stdin.readline
import copy

# S=(input())
# N=int(input())
# N,K=map(int,input().split())
# ListA=list(map(int,input().split()))
# ListA.sort()#reverse=True)

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

def resolve():
    
    N=int(input())
    X=(input())
    #N=200000
    #X="1"*200000

            
    orgpop=X.count("1")
    div1=int(X,2)%orgpop
    divP1=int(X,2)%(orgpop+1)
    divM1=int(X,2)%(orgpop-1)

    cnt=0
    for i in range(N):
        if(X[i]=='1'):
            div1=(divM1- (2**(N-i-1) % (orgpop-1)))%(orgpop-1)
        else:
            div1=(divP1+ (2**(N-i-1) % (orgpop+1)))%(orgpop+1)


            
        Xi=-1
        cnt=0
        first=True
        while True:
            if(Xi==0):
                print(cnt)
                break
            if(first):
                Xi=div1
                first=False
            else:
                pop=popcount(Xi)
                Xi=Xi%pop
            cnt+=1




resolve()

Submission status: Runtime Error

Solution code:
#%%timeit
N = int(input())
X_str = input()

X = int(X_str, 2)

popcount_cache = [0, 1] + [-1] * 3 * 10 ** 5
for x in range(2, 200000+2):
  popcount_cache[x] =  popcount_cache[x // 2] + x % 2

# def popcount(x):
#   global popcount_cache
#   if popcount_cache[x] < 0:
#     # tmp = x
#     # p = 0
#     # while tmp not in popcount_cache:
#     #   p += tmp % 2
#     #   tmp //= 2
#     popcount_cache[x] = popcount(x // 2) + x % 2
#   return popcount_cache[x]

count_cache = [0, 1] + [-1] * 3 * 10 ** 5
for x in range(2, 200000+2):
  count_cache[x] = 1 + count_cache[x % popcount_cache[x]]


# def count(x):
#   #print('count', x)
#   global count_cache
#   if count_cache[x] < 0:
#     #print('count', x, popcount(x), x % popcount(x))
#     count_cache[x] = 1 + count(x % popcount[x])
#   return count_cache[x]
  
popcount_N = 0
for s in X_str:
  if s == '1':
    popcount_N += 1

Xmodpp = X % (popcount_N + 1)
Xmodpn = X % (popcount_N - 1)

ans = []
for i in range(N):
  if i == 0:
    modpp = 1
    modpn = 1
  else:
    modpp = (modpp * 2) % (popcount_N+1)
    modpn = (modpn * 2) % (popcount_N-1)
  if X_str[N - 1 - i] == '0':
    ans.append(count_cache[  (Xmodpp + modpp) % (popcount_N + 1)] + 1)
  else:
    ans.append(count_cache[  (Xmodpn - modpn) % (popcount_N - 1)] + 1)

ans.reverse()
for a in ans:
  print(a)

Submission status: Runtime Error

Solution code:

def f(n):
  cnt = 0
  while n:
      cnt += 1
      n = n % bin(n).count('1')

  return cnt

def main():
  n = int(input())
  src = input()
  base = int(src, 2)
  base_cnt = src.count('1')

  basep = base % (base_cnt + 1)
  basem = base % (base_cnt - 1)

  for i in range(n - 1, -1, -1):
    num = None

    if src[n - i - 1] == '0':
      mod = base_cnt + 1
      num = (basep + pow(2, i, mod)) % mod
    elif base_cnt > 1:
      mod = base_cnt - 1
      num = (basem - pow(2, i, mod)) % mod
    else:
      print(0)
      continue

    print(1 + f(num))


main()

Submission status: Runtime Error

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    X = SS()

    # 一回の操作でnはN以下になる
    # 2回目以降の操作はメモ化再帰
    # 初回popcountは2種類しかない Xのpopcountから足し引きすればよい

    pc_X = X.count('1')

    next_X_p1 = 0
    next_X_m1 = 0
    pc_p1 = pc_X + 1
    pc_m1 = pc_X - 1
    for i in range(N):
        if X[i] == '1':
            next_X_p1 += pow(2, N - 1 - i, pc_p1)
            next_X_m1 += pow(2, N - 1 - i, pc_m1)

    dp = [-1] * N
    dp[0] = 0

    def dfs(n):
        if dp[n] == -1:
            dp[n] = 1 + dfs(n % bin(n).count('1'))
        return dp[n]

    for i in range(N):
        next = 0
        if X[i] == '0':
            next = next_X_p1 + pow(2, N - 1 - i, pc_p1)
            next %= pc_p1
        else:
            next = next_X_m1 - pow(2, N - 1 - i, pc_m1)
            next %= pc_m1

        if pc_X == 1 and X[i] == '1' and i == N - 1:
            ans = 0
        else:
            ans = dfs(next) + 1
        print(ans)
    # print(dp)

if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

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

def f(x):
    count = 0
    while x != 0:
        count += 1
        x %= popcount(x)
    return count

N = int(input())
X = "0b"+input()
intX = int(X, 2)
popcountX = X.count("1")
X_plus_mod = intX % (popcountX + 1)
X_minus_mod = intX % (popcountX - 1)

f_table = [f(i) for i in range(N)]  # 1 回やれば絶対この中に入る

for i in range(N):
    if X[i+1] == "0":
        diff = pow(2, N-i-1) % (popcountX + 1)
        res = (X_plus_mod + diff) % (popcountX + 1)
    else:
        diff = -pow(2, N-i-1) % (popcountX - 1)
        res = (X_minus_mod + diff) % (popcountX - 1)
    ans = f_table[res]
    print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
 
X = input()
 
pop_X = X.count('1')

X_int = int(X, 2)

X_list = list(X)

for i in range(N):
    
    a = x_list[i]

    pop_X_a = pop_X + int((-2) * int(a) + 1)
    pop_n = pop_X_a
    
    n = X_int + int( ((-2) * int(a) + 1) * (2 ** (N - i -1)) )
    
    count = 0
    
    while n != 0:
        
        n = n %  pop_n
        
        pop_n = bin(n).count('1')
        
        count += 1
    
    print(count)

Submission status: Runtime Error

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
import math
from copy import deepcopy
import queue
#import numpy as np
# sympy as syp(素因数分解とか)
Mod = 1000000007
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1] 
for i in range(2, 10**5 + 1):
    fact.append((fact[-1] * i) % Mod)
    inv.append((-inv[Mod % i] * (Mod // i)) % Mod)
    factinv.append((factinv[-1] * inv[-1]) % Mod)
    
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n - r] % p
    
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[y] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)
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
def main():  #startline-------------------------------------------
    n = int(input())
    x = input()
    xint = int(x, 2)
    popcount = x.count("1")
    def countbin(i,popcount):  #f(x)を求める関数
        cnt = 0
        while i != 0:
            i %= popcount
            cnt += 1
            popcount = bin(i).count("1")
        return cnt
    for i in range(len(x)):
        if x[i] == "0":
            print(countbin(xint + int(math.pow(2,n - i - 1)),popcount+1))
        else:
            print(countbin(xint - int(math.pow(2,n - i - 1)),popcount-1))
if __name__ == "__main__":
    main() #endline===============================================

Submission status: Runtime Error

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

def f(x):
    count = 0
    while x != 0:
        count += 1
        x %= popcount(x)
    return count

N = int(input())
X = "0b"+input()
intX = int(X, 2)
popcountX = X.count("1")
X_plus_mod = intX % (popcountX + 1)
X_minus_mod = intX % (popcountX - 1)

f_table = [f(i+1) for i in range(N)]  # 1 回やれば絶対この中に入る

for i in range(N):
    if X[i+1] == "0":
        diff = pow(2, N-i-1) % (popcountX + 1)
        res = (X_plus_mod + diff) % (popcountX + 1)
    else:
        diff = -pow(2, N-i-1) % (popcountX - 1)
        res = (X_minus_mod + diff) % (popcountX - 1)
    ans = f_table[res]
    print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
X = input()
x = int(X, 2)
cnt = X.count("1")
tmp = cnt
ans = 0
for i in reversed(range(N)):
    ans = 0
    if X[N-i-1]=="1":
        tmp -= 1
        target = x-np.power(2, i)
    if X[N-i-1]=="0":
        tmp += 1
        target = x+np.power(2, i)
    while target>0:
        target = target%tmp
        tmp = bin(target).count("1")
        ans += 1
    print(ans)
    tmp = cnt

Submission status: Runtime Error

Solution code:
def popcount(x):
    bitx = bin(x)
    cnt = bitx.count('1')
    return cnt

n = int(input())
x = list(input())
original_cnt = x.count('1')
stock = [1] * n

for i in range(1, n):
    stock[i] = stock[i - 1] * 2
stock.reverse()
original_num = 0
for i in range(n):
    original_num += int(x[i]) * stock[i]
cnt_one = original_cnt + 1
cnt_zero = original_cnt - 1

for i in range(n):
    tmp = original_num
    tmp2 = popcount
    if x[i] == '1':
        tmp -= stock[i]
        tmp2 = cnt_zero
    else:
        tmp += stock[i]
        tmp2 =cnt_one
    ans = 1
    num = tmp % tmp2
    while num != 0:
        ans += 1
        num %= popcount(num)
    print(ans)

Submission status: Runtime Error

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def main():
    N = int(readline())
    X = readline().rstrip().decode('utf-8')
    nx = int(X, 2)

    ans = [0] * N

    oc = X.count('1')

    if oc - 1 != 0:
        mx = nx % (oc - 1)
        f = True
    else:
        f = False

    px = nx % (oc + 1)

    for i in range(N):

        if X[i] == '0':
            a = (px + pow(2, N - i - 1, oc + 1)) % (oc + 1)
        elif f:
            a = (mx - pow(2, N - i - 1, oc - 1)) % (oc - 1)
        else:
            ans[i] = 0

        count = 1
        while a:
            a = a % bin(a).count('1')
            count += 1

        ans[i] = count

    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
def main():
    n = int(input())
    s = input()
    x = int(s, 2)
    pcx = s.count("1")
    pc1 = x % (pcx - 1) if pcx > 1 else 0
    pc2 = x % (pcx + 1)

    def f(j):
        cnt = 0
        while j:
            j %= bin(j).count("1")
            cnt += 1
        return cnt

    for i, y in enumerate(s):
        k = n - 1 - i
        if y == "0":
            print(f((pc2 + pow(2, k, pcx + 1)) % (pcx + 1)) + 1)
        elif pcx > 1:
            print(f((pc1 - pow(2, k, pcx - 1)) % (pcx - 1)) + 1)
        else:
            print(0)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n=int(input())
s=input()
b=int(s,2)
#n=200000
#b=2**200001-1
#s=format(b,"b")
ls=[0]*n
bi=1
xf=s.count("1")
kp=b%(xf+1)
km=b%(xf-1)
for i in range(n):
  if s[n-1-i]=="1":
    k=(km-bi)%(xf-1)
  else:
    k=(kp+bi)%(xf+1)
  ans=1
  while k>0:
    x=format(k, 'b').count("1")
    k=k%x
    ans+=1
  ls[n-1-i]=ans
  bi*=2
for i in ls:
  print(i)

Submission status: Runtime Error

Solution code:


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

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

def solve(X):
    for i in reversed(range(N)):
        K = X ^ (1 << i)
        K2 = K%P[N-1-i]
        print(f(K2) + 1)




N = int(input())
X = input()
X = X.zfill(N)
count_1 = X.count("1")

P = [0]*N
for i in range(N):
    if X[i] == "1":
        P[i] = count_1 - 1
    else:
        P[i] = count_1 + 1
Y = int(X,2)

solve(Y)

Submission status: Runtime Error

Solution code:
import copy

N=int(input())
X=input()

nbits=sum([int(X[i]) for i in range(N)])


# print(nbits)

MAXBIT=60
def strmod(bitstr,m):
    if len(bitstr)>MAXBIT:
        l = eval("0b"+bitstr[:MAXBIT])
        l_bitstr="{:b}".format(l % m)
        ans=strmod(l_bitstr+bitstr[MAXBIT:], m)
    else:
        ans="{:b}".format(eval("0b"+bitstr) % m)
    return ans

for i in range(N):

    if X[i]=='0':
        c='1'
        n = nbits + 1
    else:
        c='0'
        n = nbits - 1
    Y=X[:i]+c+X[i+1:]

    # print("Y=",Y)
    ans = 0
    while True:
        if n == 0:
            break
        ans += 1
        mstr = strmod(Y,n)
        n=sum([int(mstr[i]) for i in range(len(mstr))])
        # print(mstr, n)
        Y = mstr
    print(ans)

Submission status: Runtime Error

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

X_10 = int("0b" + X, 0)
X_bit = X.count("1")
for i in range(N):
    num = X_10
    if X[i] == "0":
        num += int(2**(N-i-1))
        num_bit = X_bit+1
    else:
        num -= int(2**(N-i-1))
        num_bit = X_bit-1
    num_2 = bin(num)
    num_2 = bin(int(num_2, 0) % num_bit)
    count = 1
    while True:
        count_2 = 0
        """
        for j in range(len(num_2)):
            if num_2[j] == "1":
                count_2 += 1
        """
        count_2 = num_2.count("1")
        if count_2 == 0:
            break
        else:
            count += 1
        num_2 = bin(int(num_2, 0) % count_2)
    print(count)

Submission status: Runtime Error

Solution code:
# D Anything Goes to Zero

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

ori_cnt = x.count("1")
for i in range(n):
  xi = int(x, 2)
  if x[i] == "1":
    new_cnt = ori_cnt - 1
  elif x[i] == "0":
    new_cnt = ori_cnt + 1
  xi = xi ^ (1 << n-i-1)
  if xi != 0:
    xi = xi % new_cnt
    ans = 1
  else:
    print(0)

  while xi != 0:
    xi = xi % bin(xi).count("1")
    ans += 1
  print(ans)

Submission status: Runtime Error

Solution code:
def input_int():
    return map(int, input().split())

def one_int():
    return int(input())

def one_str():
    return input()

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

N=one_int()
S=one_str()

def ran(S, N):
    bit_count = S.count("1")

    #bit数
    calc_dict = {i:-1 for i in range(22000)}
    res_dict =  {i:-1 for i in range(2*(10**5))}

    res_dict = {i:-1 for i in range(1001)}
    res_dict[0]=0

    for i in range(1, 1001):
        if calc_dict[i]==-1:
            calc_dict[i] = bin(i).count("1")

        res_dict[i] = i%calc_dict[i]+1


    bit_count = S.count("1")
    for i in range(len(S)):
        if S[i]=="0":

            bit_count+=1
            num = int(S,2) + 2**(N-i-1)
            if num<=0:
                print(0)
            else:
                print(res_dict[num%bit_count]+1)
            bit_count-=1
        else:

            bit_count-=1
            num = int(S,2) - 2**(N-i-1)
            if num<=0:
                print(0)
            else:
                print(res_dict[num%bit_count]+1)
            bit_count+=1

ran(S,N)

Submission status: Runtime Error

Solution code:
n = int(input())
# n = 2 * 10**5

s = input()
# s = ''.join(['1' for i in range(n)])


bin = int(s, 2)
originalPopCount = s.count('1')
memo = dict()

def popCount(value):

    count = 1
    current = value

    while current != 0:
        if current in memo:
            return count + memo[current]
        pop = format(current, 'b').count('1')
        m = current % pop
        current = m
        count += 1
    return count

result = []
p1 = bin % (originalPopCount + 1)
m1 = bin % (originalPopCount - 1)

for i in range(n):

    if s[i] == '1':
        rep = '0'
        currentPop = originalPopCount - 1
        m_base = m1
    else:
        rep = '1'
        currentPop = originalPopCount + 1
        m_base = p1

    pop2 = 2 ** (n - 1 - i) % currentPop

    m = (m_base + pop2) % currentPop

    if m == 0:
        result.append(1)
        continue

    val = m

    result.append(popCount(val))

print(*result, sep='\n')

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

from collections import defaultdict
PCmemo = defaultdict(lambda: -1)
fnmemo = defaultdict(lambda: -1)
fnmemo[0]=0

from functools import lru_cache
@lru_cache(None)
def dfs(X):
    if fnmemo[X]==-1:
        if PCmemo[X]==-1:
            popcount = bin(X).count("1")
            PCmemo[X]=popcount
        else:
            popcount = PCmemo[X]

        if popcount == 1:
            fnmemo[X]=1
            return 1

        fnmemo[X] = dfs(X%popcount)+1

    return fnmemo[X]

Xpopcount = bin(X).count("1")

for i in reversed(range(n)):
    neX = X^(1<<i)

    if X & (1 << i):
        PCmemo[neX] = Xpopcount-1
    else:
        PCmemo[neX] = Xpopcount+1

    if PCmemo[neX]==1:
        ans=1
    else:
        ans=dfs(neX%PCmemo[neX])+1
    fnmemo[neX]=ans
    print(ans)

Submission status: Runtime Error

Solution code:
def popcount(i):
    assert 0 <= i < 0x100000000
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24
memo = [None] * 300000
def do2(x):
    if memo[x] is not None:
        return memo[x]
    cnt = 0
    while x != 0:
        x = x % popcount(x)
        cnt += 1
    memo[x] = cnt
    return cnt

def do():
    ll = int(input())
    s = input()
    n = int(s, 2)

    x = n
    cnt = 0
    ss = bin(x)[2:]
    cnt += 1
    num1 = ss.count("1")
    num1m = num1 - 1
    num1p = num1 + 1
    rs = ss[::-1]
    res1m = 0
    res1p = 0
    for j in range(len(rs)):
        if rs[j] == "1":
            res1m += pow(2, j, num1m)
            res1m %= num1m
            res1p += pow(2, j, num1p)
            res1p %= num1p

    #print(res1m, res1p, num1m, num1p)
    for i in range(len(s)):
        #print("i", i)
        if s[i] == "1": # 0になるから
            #print("down")
            #print(res1m, pow(2, ll - i -1, num1m))
            if num1m == 0 or num1m == -1:
                print(0)
                continue
            x = res1m - pow(2, ll - i -1, num1m)
            x %= num1m
        elif s[i] == "0": # 1になるから
            #print("up")
            #print(res1p, pow(2, ll - i -1, num1p))
            x = res1p + pow(2, ll - i-1, num1p)
            x %= num1p

        if x == 0:
            print(1)
            continue
        print(do2(x) + 1)
do()

Submission status: Runtime Error

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():
    N = in_n()
    X = in_s()
    nx = int(X, 2)

    ans = [0] * N

    oc = X.count('1')
    mx = nx % (oc - 1)
    px = nx % (oc + 1)

    for i in range(N):

        if X[i] == '0':
            a = (px + pow(2, N - i - 1, oc + 1)) % (oc + 1)
        elif oc - 1 != 0:
            a = (mx - pow(2, N - i - 1, oc - 1)) % (oc - 1)
        else:
            ans[i] = 0
            continue

        count = 1
        while a:
            a = a % bin(a).count('1')
            count += 1

        ans[i] = count

    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def popcount(i):
    assert 0 <= i < 0x100000000
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24
memo = [None] * 300000
def do2(x):
    if memo[x] is not None:
        return memo[x]
    cnt = 0
    while x != 0:
        x = x % popcount(x)
        cnt += 1
    memo[x] = cnt
    return cnt

def do():
    ll = int(input())
    s = input()
    n = int(s, 2)

    x = n
    cnt = 0
    ss = bin(x)[2:]
    cnt += 1
    num1 = ss.count("1")
    num1m = num1 - 1
    num1p = num1 + 1
    rs = ss[::-1]
    res1m = 0
    res1p = 0
    for j in range(len(rs)):
        if rs[j] == "1":
            res1m += pow(2, j, num1m)
            res1m %= num1m
            res1p += pow(2, j, num1p)
            res1p %= num1p

    #print(res1m, res1p, num1m, num1p)
    for i in range(len(s)):
        #print("i", i)
        if s[i] == "1": # 0になるから
            #print("down")
            #print(res1m, pow(2, ll - i -1, num1m))
            x = res1m - pow(2, ll - i -1, num1m)
            x %= num1m
        elif s[i] == "0": # 1になるから
            #print("up")
            #print(res1p, pow(2, ll - i -1, num1p))
            x = res1p + pow(2, ll - i-1, num1p)
            x %= num1p

        if x == 0:
            print(1)
            continue
        print(do2(x) + 1)
do()

Submission status: Runtime Error

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

def input():
    return sys.stdin.readline().rstrip()

@lru_cache(maxsize =None)
def tc(n):
    if n ==0:
        return 0

    y =n
    count =0
    while y:
     if y%2==1:
         count +=1
     y=y//2
    ans =n % count
    if ans ==0:
     return 1
    else:
     return tc(ans) +1



def main():
    N = int(input())
    x = input()
    X = int(x,2)

    const = 0
    for i in range(N):
        if x[i] =="1":
            const +=1
    if const ==0:
        for i in range(N):
            print(1)
        exit()
    if const ==1:
        if x[-1] =="0":
            for i in range(N-1):
                if x[i] =="1":
                    print(0)
                else:
                    print(1)
            print(2)
        else:
            for i in range(n-1):
                print(2)
            print(0)
        exit()

    xm = X % (const - 1)
    xp = X % (const +1)

    for i in range(N-1, -1, -1):
        if x[N-i-1] =="0":
            t = xp + pow(2,i,const +1)
            t %= const +1
        else:
            t = xm - pow(2,i,const -1)
            t %= const -1






        print(tc(t)+1)









if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def func(Y):
    m = 0
    while True:
        m += 1
        Y = Y % format(Y, 'b').count('1')
        if Y == 0:
            break
    return m
N = int(input())
X = int(input(), 2)
for i in reversed(range(N)):
    Y = (~X & 2 ** i) | (X & ~(2 ** i))
    print(func(Y))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

from collections import defaultdict
PCmemo = defaultdict(lambda: -1)
fnmemo = defaultdict(lambda: -1)
fnmemo[0]=0

from functools import lru_cache
@lru_cache(None)
def dfs(X):
    if fnmemo[X]==-1:
        if PCmemo[X]==-1:
            popcount = bin(X).count("1")
            PCmemo[X]=popcount
        else:
            popcount = PCmemo[X]

        if popcount == 1:
            fnmemo[X]=1
            return 1

        fnmemo[X] = dfs(X%popcount)+1

    return fnmemo[X]

ans = [0]*n

Xpopcount = bin(X).count("1")

for i in reversed(range(n)):
    neX = X^(1<<i)

    if X & (1 << i):
        PCmemo[neX] = Xpopcount-1
    else:
        PCmemo[neX] = Xpopcount+1
    ans=dfs(neX%PCmemo[neX])+1
    fnmemo[neX]=ans
    print(ans)

Submission status: Runtime Error

Solution code:

def f(n):
  cnt = 0
  while n:
      cnt += 1
      n = n % bin(n).count('1')

  return cnt

def main():
  n = int(input())
  src = input()
  base = int(src, 2)
  base_cnt = src.count('1')

  basep = base % (base_cnt + 1)
  basem = base % (base_cnt - 1)

  for i in range(n - 1, -1, -1):
    num = None

    if src[n - i - 1] == '0':
      mod = base_cnt + 1
      num = (basep + pow(2, i, mod)) % mod
    else:
      mod = base_cnt - 1
      num = (basem - pow(2, i, mod)) % mod

    print(1 + f(num))


main()

Submission status: Runtime Error

Solution code:
n=int(input())
x_=input()
px=x_.count("1")
if not px:
    print(0)
    for i in range(n-1):
        print(1)
    exit()
if px==1:
    for i in range(n):
        if int(x_[-i-1]):
            print(0)
        else:
            if not i:
                print(2)
            else:
                print(1)
x=int(x_,2)

pow2=[1]

for i in range(n):
    tmp=pow2[-1]
    tmp*=2
    tmp%=px+1
    pow2.append(tmp)
pow22=[1]
for i in range(n):
    tmp=pow22[-1]
    tmp*=2
    tmp%=px-1
    pow22.append(tmp)
x1=x%(px+1)
x2=x%(px-1)
ans=[]
for i in range(n):
    tmp=0;dv=0
    if int(x_[-i-1]):
        tmp=x2-pow22[i]
        dv=px-1
    else:
        tmp=x1+pow2[i]
        dv=px+1
    if dv==0:
        ans.append(0)
        continue
    cnt=1
    while tmp:
        if not dv:
            break
        tmp%=dv
        dv=bin(tmp).count("1")
        if not tmp:
            break
        cnt+=1
    ans.append(cnt)
for i in ans[::-1]:
    print(i)

Submission status: Runtime Error

Solution code:
def input_int():
    return map(int, input().split())

def one_int():
    return int(input())

def one_str():
    return input()

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

N=one_int()
S=one_str()

def ran(S, N):
    bit_count = S.count("1")

    #bit数
    calc_dict = {i:-1 for i in range(22000)}
    res_dict =  {i:-1 for i in range(2*(10**5))}

    res_dict = {i:-1 for i in range(1001)}
    res_dict[0]=0

    for i in range(1, 1001):
        if calc_dict[i]==-1:
            calc_dict[i] = bin(i).count("1")

        res_dict[i] = i%calc_dict[i]+1


    bit_count = S.count("1")
    for i in range(len(S)):
        if S[i]=="0":

            bit_count+=1
            num = int(S,2) + 2**(N-i-1)
            if num==0:
                print(0)
            else:
                print(res_dict[num%bit_count]+1)
            bit_count-=1
        else:

            bit_count-=1
            num = int(S,2) - 2**(N-i-1)
            if num==0:
                print(0)
            else:
                print(res_dict[num%bit_count]+1)
            bit_count+=1

ran(S,N)

Submission status: Runtime Error

Solution code:
from collections import deque

def getInts():
    return [ int(x) for x in input().split() ]

def complement(c):
    if c=='1':
        return '0'
    else:
        return '1'

H = {}

def pop(n):
    return "{0:b}".format(n).count('1')
def toZero(n):
    if n==0:
        return 0
    if n==1:
        return 1
    if n in H:
        return H[n]
    r = 1 + toZero(n%pop(n))
    H[n] = r
    return r

[N] = getInts()
X = input()
Xi = int(X, 2)
X = list(X)

i=0
p = pop(Xi)
if Xi > 1:
    while 2**i < Xi:
        toZero(2**i%(p+1))
        toZero(2**i%(p-1))
        i+=1
for i in range(N):
    X[i] = complement(X[i])
    n = int("".join(X),2)
    print(toZero(n))
    X[i] = complement(X[i])