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(100000000)
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 main():
    N = int(input())
    X = input()
    d = {}
    dd = {}
    x1 = X.count('1')
    xn = int(X, 2)
    def hoge(i):
        if i in dd:
            return dd[i]
        if i not in d:
            j = popcount(i)
            d[i] = i % j
            if d[i] == 0:
                dd[i] = 1
            else:
                dd[i] = 1 + hoge(d[i])
        return dd[i]
    xn1 = xn % (x1-1)
    xn2 = xn % (x1 + 1)
    for i in range(N):
        if X[i] == '1':
            t = xn1
            t -= pow(2, N-1-i, x1-1)
            t %= (x1-1)
        else:
            t = xn2
            t += pow(2, N-1-i, x1+1)
            t %= (x1 + 1)
        if t == 0:
            print(1)
        else:
            print(1 + hoge(t))
main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2 * 10**5)

N = int(input())
X = [i for i in input()]
sum_X = X.count("1")


def division_binary_shift(a, b):
    """
    a // b

    :param a: dividend
    :param b: divisor
    :return: quotient
    """
    if a < b:
        return 0
    if b == 0:
        raise ZeroDivisionError

    q = 0
    sq = 1
    ori_b = b
    while a >= b:
        b <<= 1
        if a >= b:
            sq <<= 1
        else:
            b >>= 1
            a -= b
            q += sq
            sq = 1
            b = ori_b

    return a


def f(n, p):
    res = division_binary_shift(int(n, 2), p)
    if res != 0:
        temp2 = format(res, "b")
        return f(temp2, temp2.count("1")) + 1
    return 1


for i in range(0, N):
    tempX = ""
    count = sum_X
    if X[i] == "0":
        count += 1
        X[i] = "1"
        tempX = "".join(X)
        X[i] = "0"
    else:
        count -= 1
        X[i] = "0"
        tempX = "".join(X)
        X[i] = "1"

    print(f(tempX, count))

Submission status: Runtime Error

Solution code:
import sys
input = lambda:sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**9)

def solve(k, cnt, Ans):
    S = str(bin(k)).count("1") 
    L = k % S
    if L < len(Ans)+1:
        return Ans[L]
    elif L == 0:
        return 1
    cnt += solve(L,cnt, Ans)
    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, Ans)+1)
#print(Ans)

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

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

Submission status: Runtime Error

Solution code:
n=int(input())
x=input()
t=int(x,2)
c=x.count('1')
m=[0]*n
k=1
while k<n: m[k]=1; k*=2
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
def f(x):
  if x==0: return 0
  if m[x]: return m[x]
  return f(x%popcount(x))+1
for i in range(n):
  if int(x[i]):
    d=c-1
    if c<1: print(0)
    print(f((t-pow(2,n-i-1,d))%d)+1)
  else:
    d=c+1
    print(f((t+pow(2,n-i-1,d))%d)+1)

Submission status: Runtime Error

Solution code:
import collections

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

x_list = list(x)

num_dict = dict(collections.Counter(x_list))

num_of_1 = num_dict["1"]

for i in range(n):
    temp = x_list.copy()
    temp_num_of_1 = num_of_1 + 1 if temp[i] == "0" else num_of_1 - 1

    temp[i] = "1" if temp[i] == "0" else "0"

    ans = 0

    if temp_num_of_1 != 0:
        a = int("".join(temp), 2)

        a = a % temp_num_of_1

        temp = list(bin(a)[2:])

        ans += 1
    
        while temp.count("1") != 0:
            a = int("".join(temp), 2)

            a = a % temp.count("1")

            temp = list(bin(a)[2:])

            ans += 1

    print(ans)

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)
##########
b = {0:1}
def f(x):
    ans = 0
    x_ = x%a[x-1]
    if x_ in b:
        ans += b[x_]
    else:
        ans += f(x_) + 1
        b[x_] = ans
    return ans
##########
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 math
from copy import copy
di = {}
di[0] = 0
for i in range(1, 2*(10**5)+1):
    di[i] = 0
for i in range(1, 2*(10**5)+1):
    count = 0
    for j in range(int(math.log2(i))+2):
        if (i>>j)&1:
            count += 1
    di[i] = di[i%count] + 1
n = int(input())
x = list(input())
x.reverse()
count = 0
for i in x:
    if i =='1':
        count += 1
mod_p = count + 1
mod_m = count - 1
di_p = {}
di_m = {}
for i in range(n):
    di_p[i] = pow(2, i, mod_p)
    di_m[i] = pow(2, i, mod_m)
s_p = 0
s_m = 0
for i in range(n):
    if x[i] == '1':
        s_p += di_p[i]
        s_m += di_m[i]
for i in range(n-1, -1, -1):
    sm = copy(s_m)
    sp = copy(s_p)
    if x[i] == '1':
        sm -= di_m[i]
        sm %= mod_m 
        print(di[sm]+1)
    else:
        sp += di_p[i]
        sp %= mod_p
        print(di[sp]+1)

Submission status: Runtime Error

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


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

cache = [-1] * (2 * 10 ** 5 + 1)


def f(n):
    if cache[n] != -1:
        return cache[n]
    return f(n % popcount(n)) + 1

def g(n, m):
    if n < 60:
        return (1 << n) % m
    else:
        t = n // 2
        return g(t, m) * g(n - t, m) % m


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

c = X.count('1')
t1 = [0] * N
t2 = [0] * N
for i in range(N):
    n = N - 1 - i
    t1[i] = g(n, c - 1)
    t2[i] = g(n, c + 1)

x1, x2 = 0, 0
for i in range(N):
    if X[i] == '1':
        x1 += t1[i]
        x2 += t2[i]

result = []
for i in range(N):
    if X[i] == '1':
        n = x1 - t1[i]
        n %= c - 1
    elif X[i] == '0':
        n = x2 + t2[i]
        n %= c + 1
    result.append(f(n) + 1)
print(*result, sep='\n')

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


if(1<num_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)
else:
    for i in range(1,N):
        mlist_num_1up[i]=(mlist_num_1up[i-1]*2)%(num_1+1)

    upmod_ori=0
    for i in range(N):
        if(X[i]=='1'):
            upmod_ori+=mlist_num_1up[i]
    mlist_num_1up.reverse()
    for i in range(N):
        if(X[i]=='1'):
            a=0
            print(a)
        else:
            mod=upmod_ori+mlist_num_1up[i]
            mod%=(num_1+1)
        print(1 if mod==0 else 2)



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]*31
fans[0]=0
fans[1]=1
for i in range(2,31):
    mod=0
    for p in range(7):
        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(31):
        if((mod>>p) & 1):
            mod1+=1
    print(fans[mod1]+1)

Submission status: Runtime Error

Solution code:
def popcnt(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 = input()
first_bit_cnt = [X.count('1')]*N
for i in range(N):
    if X[i] == '1':
        first_bit_cnt[i] -= 1
    else:
        first_bit_cnt[i] += 1
X = int('0b'+X,0)
target = [0]*N
bit = 1
for i in range(N):
    target[N-1-i] = X^bit
    bit = bit<<1
popcount = [0]*(N+1)
for i in range(1,N+1):
    popcount[i] = popcnt(i)
ans = [0]*N
for i in range(N):
    tmp = target[i]%first_bit_cnt[i]
    cnt = 1
    if tmp == 0:
        ans[i] = cnt
        continue
    while True:
        tmp = tmp%popcount[tmp]
        cnt += 1
        if tmp == 0:
            break
    ans[i] = cnt
for i in ans:
    print(i)

Submission status: Runtime Error

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

popc = [0] * ((1 << 18) + 1)
for bit in range(1, 1 << 18):
    opt = bin(bit).count('1')
    popc[bit] = bit % opt

f_list = [0] * ((1 << 18) + 1)
for i in range(1, 1 << 18):
    now = popc[i]
    cnt = 1
    while True:
        if now == 0:
            f_list[i] = cnt
            break
        now = popc[now]
        cnt += 1

N = getN()
X = input()
NX = len(X)
time = X.count('1')
t1 = time + 1
t2 = time - 1

lis_left_1 = [0] * NX

now = 1 % t1
lis_left_1[0] = now
for i in range(1, NX):
    now = (2 * now) % t1
    lis_left_1[i] = now

now = 1 % t2
lis_left_2 = [0] * NX

now = 1 % t2
lis_left_2[0] = now
for i in range(1, NX):
    now = (2 * now) % t2
    lis_left_2[i] = now

left_mother_1 = 0
for i in range(NX):
    if int(X[i]) == 1:
        left_mother_1 += lis_left_1[NX - i - 1]

left_mother_2 = 0
for i in range(NX):
    if int(X[i]) == 1:
        left_mother_2 += lis_left_2[NX - i - 1]

for i in range(N):
    # 1が0に left_mother_2, t2
    if int(X[i]) == 1:
        opt_mom = left_mother_2
        opt_mom -= lis_left_2[NX - i - 1]
        opt_mom %= t2
        print(f_list[opt_mom] + 1)
    # 0が1に left_mother_1, t1
    else:
        opt_mom = left_mother_1
        opt_mom += lis_left_1[NX - i - 1]
        opt_mom %= t1
        print(f_list[opt_mom] + 1)

Submission status: Runtime Error

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

V = [1]*200000
for i in range (2, 200001):
    a = i
    b = str(bin(i))
    c = b.count('1')
    d = a%c
    if d ==0:
        V[i-1] = 1
    else:
        V[i-1] = V[d-1]+1

length = len(X)

binaryA = []
for i in range (0, length):
    binaryA.append(2**i)

c = X.count('1')

for i in range (0, length):
    e = c
    if X[i] == '0':
        e+=1
    else:
        e-=1
    a = int(X, base = 2)^binaryA[length-1-i]
    if a == 0:
        print(0)
    d = a%e
    if d ==0:
        print(1)
    else:
        print(V[d-1]+1)

Submission status: Runtime Error

Solution code:
def main():
    n = int(input())
    x = input()
    x = '0b'+x

    x = int(x,0)
    m = bin(x).count('1')

    a = x%(m-1)
    b = x%(m+1)
    tmp_a = 1
    tmp_b = 1
    xx = []

    for i in range(n):
        if (x >> i) &1:
            y = (a - tmp_a)%(m-1)
        else:
            y = (b + tmp_b)%(m+1)
        tmp_a *= 2
        tmp_a %= (m-1)
        tmp_b *= 2
        tmp_b %= (m+1)
        # print(tmp_a,tmp_b)

        # z = x ^ (1<<i) 
        # t = z
        # z %= bin(z).count('1')
        # # y = z
        # # print(t,z,y)

        cnt = 1
        # c = y
        while y != 0:
            cnt += 1
            y = solve(y)
        xx.append(cnt)
    
    for i in range(n-1,-1,-1):
        print(xx[i])

def solve(n):
    m = bin(n).count('1')
    return n%m

main()

Submission status: Runtime Error

Solution code:
import copy
n = int(input())
x = list(map(str,input()))
fun =0


for j in range(n):
    ans =0
    xi = copy.copy(x)
    if xi[j] =='0':
        xi[j] ='1'
    else:
        xi[j] ='0'
    fun = int("".join(xi), 2)
    popcount = xi.count('1')

    for i in range(n):
        fun = fun % popcount
        popcount = str(format(fun,'b')).count('1')
        if fun == 0:
            ans = i+1
            break
    print(ans)

Submission status: Runtime Error

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

outf = {}
res = []

def get_dec(bin):
  s = 0
  seed = 2 ** (len(bin)-1)
  for el in bin:
    if el == '1':
      s += seed
    seed = seed // 2
  return s

def get_bin(dec):
  s = ''
  while dec > 0:
    if dec % 2 == 1:
      s = s + '1'
    else:
      s = s + '0'
    dec = dec // 2
  return s

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


for i in range(n):
  if x[i] == '0':
    x = x[:i] + '1' + x[i+1:]
  else:
    x = x[:i] + '0' + x[i+1:]
  x_dec = get_dec(x)
  res.append(x_dec)

  # calc f
  kp = []
  f = 0
  while x_dec > 0:
    st = get_bin(x_dec)
    if st in outf.items():
      f += outf[st]
      break
    kp.append(x_dec)
    f += 1
    pc = popcount(x_dec)
    x_dec = x_dec % pc

  # keep
  lf = f
  for k in kp:
    st = get_bin(k)
    outf[st] = lf
    lf -= 1

  if x[i] == '0':
    x = x[:i] + '1' + x[i+1:]
  else:
    x = x[:i] + '0' + x[i+1:]


for i in res:
  st = get_bin(i)
  print(outf[st])

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define mci map<char, int>
#define msi map<string, int>
#define pii pair<int, int>
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
//#define mod 1000000007 //998244353
#define mii map<int, int>
#define rep(i,x,y) for(int i=x; i<y; i++)
#define fill(a,b) memset(a, b, sizeof(a))
#define vi vector<int>

//clear adj and visited vector declared globally after each test case
//check for long long overflow
//while adding and subs check if mod becomes -ve
//while using an integer directly in a builtin function add ll
//Mod wale question mein last mein if dalo ie. Ans<0 then ans+=mod;
//Dont keep array name as size or any other key word



const long long N = 200005, INF = 2000000000000000000;
//lld pi = 3.1415926535897932;
int lcm(int a, int b)
{
  int g = __gcd(a, b);
  return a / g * b;
}
int power(int a, int b, int p)
{
  if (a == 0)
    return 0;
  int res = 1;
  a %= p;
  while (b > 0)
  { if (b & 1)
      res = (res * a) % p;
    b >>= 1;
    a = (a * a) % p;
  }
  return res;
}

int testcaseva;

int sq(int x) { return 1ll * x * x; }

void rec(int n) {
  int p = n;
  if (n == 0)
    return ;
  cout << p - n << " ";
  return rec(n - 1);


}
ll n,c;
ll ar[100005];
bool valid(int m,int c,int n){
    int cnt =0;
    int pr = INT_MIN;
    for(int i=0;i<n;i++)
    {
        if(ar[i]-pr >= m)
            cnt++ , pr = ar[i];
    }
    if(cnt >= c)
    return true;
    else return false;

}
int num_to_bits[16] = { 0, 1, 1, 2, 1, 2, 2, 3,
                        1, 2, 2, 3, 2, 3, 3, 4 };

unsigned int countSetBitsRec(unsigned int num)
{
    int nibble = 0;
    if (0 == num)
        return num_to_bits[0];

    nibble = num & 0xf;

    return num_to_bits[nibble] + countSetBitsRec(num >> 4);
}
int binaryToDecimal(string n)
{
    string num = n;
    int dec_value = 0;

    int base = 1;

    int len = num.length();
    for (int i = len - 1; i >= 0; i--) {
        if (num[i] == '1')
            dec_value += base;
        base = base * 2;
    }

    return dec_value;
}
int toggleKthBit(int n, int k)
{
    return (n ^ (1 << (k-1)));
}
ll pw(ll n,ll mod){
    ll ans=1;

    ll x=2,y=n;
    while(y!=0){
        if(y%2)
            ans=((ans%mod)*(x%mod))%mod;
        x=((x%mod)*(x%mod))%mod;
        y/=2;
    }
    return ans;
}

ll cunt(ll n){
    ll cnt=0;
    while(n!=0){
        if(n%2)
            cnt++;
        n/=2;
    }
    return cnt;
}

void func(ll n){
    ll cnt=1;
    while(n>0){
        ll temp=cunt(n);
        cnt++;
        n=n%temp;
    }
    cout<<cnt<<endl;
}



int main() {
//#ifndef ONLINE_JUDGE
//  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
//#endif
  // int t;
  // cin >> t;
  // while (t--)
//  int t=1;
//  //cin >> t;
//  while(t--){
        ll n;
    cin>>n;
    string s;
    cin>>s;
    ll mn=0,mx=0;
    for(ll i=0;i<n;i++){
        if(s[i]=='1')
            mn++;
    }
    if(mn<n){
        mx=mn+1;
        mn--;
    }
    else{
        mn--;
        mx=mn;
    }
     if(mn==0 || mx==0){ for(ll i=0;i<n;i++){ if(s[i]=='1') cout<<0<<endl; else{ if(i==n-1) cout<<2<<endl; else cout<<1<<endl; } } return 0; }
    ll fwefwef=0,efefwf=0;

    reverse(s.begin(),s.end());
    ll temp1=1,temp2=1;
    for(ll i=0;i<n;i++){
        if(s[i]=='1'){
        fwefwef=((fwefwef%mn)+(temp1%mn))%mn;
        efefwf=((efefwf%mx)+(temp2%mx))%mx;
        }
        temp1=((temp1%mn)*2)%mn;
        temp2=((temp2%mx)*2)%mx;
    }
    vector<ll> ans;
    for(ll i=n-1;i>=0;i--){
        if(s[i]=='1'){
            ll temp=fwefwef - pw(i,mn);
            temp+=mn;
            temp=temp%mn;
            func(temp);
        }
        else{
            ll temp=efefwf + pw(i,mx);
            temp=temp%mx;
            func(temp);
        }
    }
    for(int i=0;i<ans.size();i++)
        cout << ans[i] << endl;

  return 0;
}

Submission status: Runtime Error

Solution code:
n=int(input())
s=input()
tmp = []

c = s.count('1')
num = int(s,2)
ans=0

for i in range(n):
    if s[i] == '0':
        tmp.append(num + 2**(n-i-1))
    else:
        tmp.append(num - 2**(n-i-1))

for i in range(n):
    if tmp[i] > num:
        a = tmp[i] % (c+1)
        ans += 1
        while a!=0:
            a = a % str(bin(a)).count('1')
            ans += 1
        print(ans)
        ans =0
    else:
        a = tmp[i] % (c-1)
        ans += 1
        while a!=0:
            a = a % str(bin(a)).count('1')
            ans += 1
        print(ans)
        ans =0

Submission status: Runtime Error

Solution code:
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
# from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
# import numpy as np
# sys.setrecursionlimit(int(pow(10,6)))

mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]

try:
    sys.stdin = open("input.txt", "r")
    sys.stdout = open("out.txt", "w")
except:
    pass


# @lru_cache(None)

n=L()[0]
X=input()
if X="0"*n:
    for i in range(n):
        print(1)
    exit()
if X=="1":
    print(0)
    exit()
curr=curr2=1
nao=mnao=0
bit=X.count("1")+1
bit2=X.count("1")-1
for i in range(n-1,-1,-1):
    if X[i]=="1":
        nao+=curr%bit
        nao%=bit
        mnao+=curr2%bit2
        mnao%=bit2
    curr*=2
    curr%=bit
    curr2*=2
    curr2%=bit2
for  i in range(n):
    FN=0
    if X[i]=="0":
        FN=nao
        ex=pow(2,n-i-1,bit)
        FN+=ex
        FN%=bit
    else:
        FN=mnao
        ex=pow(2,n-i-1,bit2)
        FN-=ex
        FN%=bit2
        if FN<0:
            FN+=bit2
    step=1
    while(FN):
        bitcnt=bin(FN).count("1")
        FN%=bitcnt
        step+=1
    print(step)

Submission status: Runtime Error

Solution code:
import sys
from collections import Counter
N = int(input())
X = list(input())
revX = reversed(X)
count01 = Counter(X)
if count01['1'] == 0:
    for i in range(N):
        print(1)
    sys.exit()
m1 = count01['1']-1
p1 = count01['1']+1
powrem = []
m1rem = 0
p1rem = 0
basem1 = 1
basep1 = 1

for i, xi in enumerate(revX):
    # print(basep1)
    if xi == '0':
        powrem += [basep1 % p1]
    else:
        powrem += [basem1 % m1]
        m1rem = (m1rem + basem1) % m1
        p1rem = (p1rem + basep1) % p1
    basem1 = (basem1 * 2) % m1
    basep1 = (basep1 * 2) % p1
revpowrem = reversed(powrem)
# print(list(revpowrem))
for xi, rem in zip(X, revpowrem):
    c = 1
    if xi == '0':
        r = (p1rem+rem)%p1
    else:
        if m1 == 0:
            print(0)
            continue
        r = (m1rem-rem)%m1
    # print(r, xi, rem)
    while r != 0:
        p = bin(r).count('1')
        r = r % p
        c += 1
    print(c)

Submission status: Runtime Error

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

def popcount(n):
    bin_str = bin(n)
    return bin_str.count('1')
# print(popcount(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)         ])


cnt = 0
def func(n):
    global cnt
    if n == 0:
        return cnt
    n = n % popcnt5(n)
    cnt += 1
    return func(n)
# print(func(7))

def toggle_nth_bit(num: int, n: int):
    return num ^ (1 << n)


for i in range(N-1, -1,-1):
    n = toggle_nth_bit(int(X, 2), i)
    ans = func(n)
    print(ans)
    cnt -= ans

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(2000000)

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()

bit_count = S.count("1")

bit_count

#bit数
calc_dict = {i:-1 for i in range(22)}

def mods(N, m, count):
    temp = N%m
    if temp==0:
        return count+1
    
    if calc_dict[temp]==-1:
        calc_dict[temp] = bin(temp).count("1")

    return mods(temp, calc_dict[temp], count+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)
        print(mods(num, bit_count, 0))
        bit_count-=1
    else:

        bit_count-=1
        num = int(S,2) - 2**(N-i-1)
        print(mods(num, bit_count, 0))
        bit_count+=1

Submission status: Runtime Error

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
x = input()
b = []
c = [0, 1, 1]
for i in range(n+1):
    cnt = 0
    for j in range(7):
        if i >> j & 1:
            cnt += 1
    b.append(cnt)

for i in range(3, n+1):
    c.append(c[i % b[i]]+1)

ans = []
tmp1 = 0
tmp2 = 0
cnt = x.count("1")
for i in range(n):
    if x[i] == "1":
        tmp1 += pow(2, n-(i+1), cnt+1)
        tmp2 += pow(2, n-(i+1), cnt-1)
for i in range(n):
    if x[i] == "1":
        ans.append(c[(tmp2-pow(2, n-(i+1), cnt-1)) % (cnt-1)]+1)
    else:
        ans.append(c[(tmp1+pow(2, n-(i+1), cnt+1)) % (cnt+1)]+1)

for i in ans:
    print(i)

Submission status: Runtime Error

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

r = S.count("1") + 1
l = r if r == 1 else r - 2

lcnt = [0] * (l + 1)
rcnt = [0] * (r + 1)
for i in range(1, l + 1):
    lcnt[i] = lcnt[i % bin(i).count("1")] + 1

for i in range(1, r + 1):
    rcnt[i] = rcnt[i % bin(i).count("1")] + 1

for i in range(N):
    NX = 0
    if S[i] == "0":
        NX = X + (2 ** (N - i - 1))
        print(rcnt[NX % r] + 1)
    else:
        NX = X - (2 ** (N - i - 1))
        print(lcnt[NX % l] + 1)

Submission status: Runtime Error

Solution code:
def popcount(n):
    bin_n = format(n, "b")
    ans = 0
    for e in bin_n:
        if e=="1":
            ans += 1
    return ans

N = int(input())
bin_X = input()

max_pop = 200000
pop_list = [0] * (max_pop+1)
for i in range(1, max_pop+1):
    pop_list[i] = popcount(i)

ans_list = [0] * (max_pop+1)
for i in range(1, max_pop+1):
    new = i
    ans = 0
    while True:
        if new == 0:
            break
        ans += 1
        new = new % pop_list[new]
    ans_list[i] = ans

pop = 0
X = 0
X_p = 0
X_m = 0
for i in range(N):
    if bin_X[i]=="1":
        pop += 1
        X += 2**(N-i-1)

pop_p = pop + 1
pop_m = pop - 1

for i in range(N):
    if bin_X[i]=="1":
        X_p += 2**(N-i-1)%pop_p
        X_m += 2**(N-i-1)%pop_m


for i in range(N):
    if bin_X[i] == "0":
        new = X_p + 2**(N-i-1)
        pop_new = pop_p
    else:
        new = X_m - 2**(N-i-1)
        pop_new = pop_m
    #print(new)
    if new == 0:
        ans = 0
    else:
        new = new % pop_new
        ans = ans_list[new] + 1
        
    print(ans)

Submission status: Runtime Error

Solution code:
def main():

    n = int(input())
    table = [0]*(n+1)
    x = input()
    k = x.count("1")
    for i in range(1,n+1):
        tmp=str(bin(i)).count("1")
        table[i]=i%tmp
    tmp = 0
    j=n
    for i in range(n):
        if(x[i]=="1"):
            tmp += 2**(j-1)
        j-=1
    j=n
    res = [0]*n
    for i in range(n):
        tmp2=k#1の数
        tmp3 = tmp#１０進数表記
        if(x[i]=="1"):
            tmp2-=1
            tmp3 -= (2**(j-i-1))
        else:
            tmp2+=1
            tmp3 += 2**(j-i-1)
        next = tmp3%tmp2

        if(next==0):
            res[i]=1
        else:
            res[i]+=1
            while(next!=0):
                res[i]+=1
                next = table[next]

    for i in range(n):
        print(res[i])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
def calc_ones(n):
    ones = np.array(list(map(int, list(bin(n)[2:])))).sum()
    return ones

def calc_i(n, i):
    i += 1
    div = n % calc_ones(n)
    if div == 0:
        return i
    else:
        return calc_i(div, i)

n = int(input())
x = str(input())
x_int = np.array(list(map(int, x)))[::-1].dot(np.power(np.ones(n)*2, np.arange(n)))
for i in range(n):
    z_int = int(x_int + 2**(n-1-i)) if x[i] == "0" else int(x_int - 2**(n-1-i))
    print(calc_i(z_int, 0))

Submission status: Runtime Error

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

d = [0 for _ in range(N)]
for i in range(1, N):
    v = i % bin(i)[2:].count("1")
    d[i] = d[v] + 1
   
for i in range(N):
    if X[i] == "0":
        x = X[:i] + "1" + X[i+1:]
    else:
        x = X[:i] + "0" + X[i+1:]
    val = int(x, 2) % x.count("1")
    print(d[val] + 1)

Submission status: Runtime Error

Solution code:
import numpy as np

N = int(input())
a = list(map(int, input()))


def aaa(num_str,count):
    num = int(num_str,2)
    numd = num_str.count("1")
#     print(numd)
    amari = num % numd
#     print(amari)
    count += 1
    if amari != 0:
        return aaa(bin(amari)[2:], count)
    else:
        return count

for i in range(N):
    b = a.copy()
    b[i] = 1 - a[i]
    num_str = ''.join(map(str, b))
    value = aaa(num_str, 0)
    
    print(value)

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

N = int(input())
X = int(input(),2)
counts = []

for i in range(1,N+1,1):
    count = 0
    Xi = X ^ 2**(N-i)
    while Xi!=0:
        count+=1
        #popcount
        #Xi = Xi%bin(Xi).count("1")
        Xi = Xi % popcount(Xi)
    counts.append(count)

for k in counts:
    print(k)