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
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N = int(input())
S = list(input())[:-1]
table = [0]*(N+3)
table[1] = 1
for i in range(2,N+3):
    num = i
    cnt = 0
    while num != 0:
        a = num % 2
        num = num // 2
        cnt += a
    p = i % cnt
    table[i] = table[p]+1
c = 0
for s in S:
    if s == "1":
        c += 1
ans = 0
plus = [0]*N
minus = [0]*N
p = 0
q = 0
for i in range(N):
    ss = S[N-1-i]
    p += int(ss)*pow(2,i,c+1)
    if c != 1:
        q += int(ss)*pow(2,i,c-1)
    p %= (c+1)
    q %= (c-1)
for i in range(N):
    ss = S[i]
    if ss == "0":
        ans = (p+pow(2,N-1-i,c+1))%(c+1)
        print(table[ans]+1)
    else:
        if c == 1:
            print(0)
        else:
            ans = (p-pow(2,N-1-i,c-1))%(c-1)
            print(table[ans]+1)

Submission status: Runtime Error

Solution code:
n,x=int(input()),input()
o=x.count("1")
l=[0]*(o+1)
A=int(x,2)
a=A%(o+1)
b=A%(o-1)
for i in range(1,o+1):l[i]=l[i%bin(i).count("1")]+1
mp=[1]*n
mm= [1]*n
for i in range(1,n):
  mp[i]=mp[i-1]*2%(o+1)
  mm[i]=mm[i-1]*2%(o-1)
for i,v in enumerate(x):
  if v=="0":
    print(l[(a+mp[-1-i])%(o+1)]+1)
  else:
    if o==1:print(0)
    else:print(l[(b+mm[-1-i])%(o-1)]+1)

Submission status: Runtime Error

Solution code:

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


def popcount(ni):
    n_b = str(bin(ni))
    return n_b.count("1")


def ans(n,x):
    x_i = int(x, 2)
    x_orig = popcount(x_i)
    solve = 0
    n_i = 2**(n-1)
    for i in range(n):
        x_count = x_orig
        if x[i] == "0":
            solve = x_i+n_i
            x_count += 1
        else:
            solve = x_i-n_i
            x_count -= 1
        n_i = int(n_i / 2)
        count = 0

        if solve != 0 :
            solve = solve % x_count
            count+=1

        while solve > 0:
            solve = solve % popcount(solve)
            count+=1

        print(count)

    
ans(n,x)

Submission status: Runtime Error

Solution code:
import java.util.*;
import java.lang.*;

public class MyTest {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n, pop1, pop2;
        String s;

        n = Integer.valueOf(in.nextLine());
        s = in.nextLine();
        pop1 = popCount(s);
        pop2 = pop1-1;
        pop1++;
        for(int i=0;i<n;i++){
            String x = s.substring(0, i) + (s.charAt(i)=='1'?'0':'1') + s.substring(i+1);
            int count = 0;
            int xi = 0;
            int pop = 1;

            if(s.charAt(i)=='1'){
                pop = pop2;
            }else{
                pop = pop1;
            }

            if(pop>0){
                for(int j=0; j<n; j++){
                    if(x.charAt(j)=='1'){
                        xi += Math.pow(2, n-j-1) % pop;
                    }
                }
                xi = xi % pop;
                count++;
            }

            while(xi > 0){
                xi = xi % popCount(xi);
                count++;
            }
            print(count);
        }

        in.close();
    }

    private static int popCount(String s){
        int count = 0;
        for(int i=0; i<s.length(); i++){
            count += s.charAt(i)=='1' ? 1 : 0;
        }
        return count;
    }

    private static int popCount(long n){
        int count = 0;
        while(n>0){
            count += n%2;
            n /= 2;
        }
        return count;
    }

    private static void print(Object obj){
        System.out.println(obj);
    }
} // javac MyTest.java & java MyTest < input.txt > out

Submission status: Runtime Error

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

ans = [0]*(str(bin(x)).count('1')+1)
for i in range(1,len(ans)):
    ans[i] = 1 + ans[i%str(bin(i)).count('1')]
#print(ans)
for i in range(n):
    y = x^(1<<(n-i-1))
    t = y % str(bin(y)).count('1')
    print(1+ans[t])

Submission status: Runtime Error

Solution code:
N = int(input())
x = list(input())[::-1]
print(x)
num = 0
nump = 0
numm = 0
pop_num = 0
for i in range(N):
        if x[i] == "1":
            pop_num += 1
for i in range(N):
    if x[i] == "1":
        num += pow(2,i,pop_num)
        num %= pop_num 
        nump += pow(2,i,pop_num+1)
        nump %= pop_num  + 1
        if pop_num-1 != 0:
            numm += pow(2,i,pop_num - 1)
            numm %= pop_num - 1



def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

x = x[::-1]
def calc(i,depth,n):
    if depth == 0:
        if x[i] == "1":
            tmp = numm
            tmp -= pow(2,N-i-1,pop_num-1)
            tmp %= (pop_num - 1)
            return calc(i,depth+1,tmp)
        else:
            tmp = nump
            tmp += pow(2,N-i-1,pop_num+1)
            tmp %= (pop_num + 1)
            return calc(i,depth+1,tmp)
    else:
        if n == 0: return depth
        return calc(i,depth+1, n % popcnt(n))
        

for i in range(N):
    print(calc(i,0,0))

Submission status: Runtime Error

Solution code:
n = int(input())
x = str(input())
X = 0
one = 0
for i in range(n):
    X+=int(x[i])*2**(n-i-1)
    if x[i]=="1":
        one+=1


if one>0:
    l = [0, 1]
    for i in range(2,n):
        if i%2==0:
            l.append(1)
        else:
            l.append(l[i%bin(i).count("1")]+1)

    for i in range(n):
        if x[i]=="0":
            print(l[(X+2**(n-i-1))%(one+1)]+1)
        else:
            print(l[(X-2**(n-i-1))%(one-1)]+1)
else:
    for i in range(n):
        if i==n-1:
            print(2)
        else:
            print(1)

Submission status: Runtime Error

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

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

def f(n, c=1):
    cnt = c
    r = n % popcount(n)
    if r != 0:
        cnt += 1
        return f(r, cnt)
    else:
        return cnt


for i in range(len(X)):
    if X[i] == "0":
        s = X[:i] + "1" + X[i+1:]
        n = int(s, 2)
        print(f(n))
    else:
        s = X[:i] + "0" + X[i+1:]
        n = int(s, 2)
        print(f(n))

Submission status: Runtime Error

Solution code:
N = int(input())
x = list(input())[::-1]
print(x)
num = 0
nump = 0
numm = 0
pop_num = 0
for i in range(N):
        if x[i] == "1":
            pop_num += 1
for i in range(N):
    if x[i] == "1":
        num += pow(2,i,pop_num)
        num %= pop_num 
        nump += pow(2,i,pop_num+1)
        nump %= pop_num  + 1
        if pop_num != 0:
            numm += pow(2,i,pop_num - 1)
            numm %= pop_num - 1



def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

x = x[::-1]
def calc(i,depth,n):
    if depth == 0:
        if x[i] == "1":
            tmp = numm
            tmp -= pow(2,N-i-1,pop_num-1)
            tmp %= (pop_num - 1)
            return calc(i,depth+1,tmp)
        else:
            tmp = nump
            tmp += pow(2,N-i-1,pop_num+1)
            tmp %= (pop_num + 1)
            return calc(i,depth+1,tmp)
    else:
        if n == 0: return depth
        return calc(i,depth+1, n % popcnt(n))
        

for i in range(N):
    exit()
    print(calc(i,0,0))

Submission status: Runtime Error

Solution code:
def pcmod(n):
    if n==0:
        return 1
    return 1+pcmod(n%bin(n).count('1'))

def main():
    n = int(input())
    x = list(map(int,list(input())))

    m_1 = x.count(1)-1
    m_0 = x.count(1)+1 
    baser_1 = 0
    baser_0 = 0
    if m_1!=0:
        for i in range(n):
            baser_1 += x[i] * pow(2,(n-1-i),m_1)
            baser_1 %= m_1
        
    for i in range(n):
        baser_0 += x[i] * pow(2,(n-1-i),m_0)
        baser_0 %= m_0

    ans = [0]*n

    for i in range(n):
        a = 0
        if x[i]==1:
            t = (baser_1 - pow(2,(n-1-i),m_1))%m_1
            a = pcmod(t)

        if x[i]==0:
            if m_0 ==0:
                ans[i] = 0
                continue
            t = (baser_0 + pow(2,(n-1-i),m_0))%m_0
            a = pcmod(t)
        ans[i] = a

    for a in ans:
        print(a)
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:

def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f

n = int(input())
x = input()
cnt = x.count("1")
int_x = int(x, 2)
int_x_mod_plus = int_x % (cnt + 1)
int_x_mod_minus = int_x % (cnt - 1)

for i in range(n):
    if x[i] == "0":
        y = (int_x_mod_plus + pow(2, n - i - 1) % (cnt + 1)) % (cnt + 1)
    else:
        y = (int_x_mod_minus - pow(2, n - i - 1) % (cnt - 1)) % (cnt - 1)
    if y == 0:
        print(1)
    else:
        ans = 1
        while y > 0:
            y %= popcount(y)
            ans += 1
        print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
x = list(input())[::-1]
print(x)
num = 0
nump = 0
numm = 0
pop_num = 0
for i in range(N):
        if x[i] == "1":
            pop_num += 1
for i in range(N):
    if x[i] == "1":
        num += pow(2,i,pop_num)
        num %= pop_num 
        nump += pow(2,i,pop_num+1)
        nump %= pop_num  + 1
        numm += pow(2,i,pop_num - 1)
        if pop_num != 0:
            numm %= pop_num - 1



def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

x = x[::-1]
def calc(i,depth,n):
    if depth == 0:
        if x[i] == "1":
            tmp = numm
            tmp -= pow(2,N-i-1,pop_num-1)
            tmp %= (pop_num - 1)
            return calc(i,depth+1,tmp)
        else:
            tmp = nump
            tmp += pow(2,N-i-1,pop_num+1)
            tmp %= (pop_num + 1)
            return calc(i,depth+1,tmp)
    else:
        if n == 0: return depth
        return calc(i,depth+1, n % popcnt(n))
        

for i in range(N):
    exit()
    print(calc(i,0,0))

Submission status: Runtime Error

Solution code:
from collections import deque
LIM=200004
L=[0]*LIM

def bin_sum(Y):
    S=bin(Y)[2:]
    count=0
    for i in range(len(S)):
        count+=int(S[i])
    return count

def bin_sum2(Y):
    count=0
    for i in range(len(Y)):
        count+=int(Y[i])
    return count

for i in range(1,LIM):
    L[i]+=bin_sum(i)

def pop_num(N,b,L):
    if N==0:
        return 0
    v=N%b
    return pop_num(v,L[v],L)+1
    
M=[0]*200005
for i in range(1,200004):
    M[i]+=pop_num(i,L[i],L)
X=int(input())
Y=input()
zero=deque()
for i in range(X):
    if Y[i]=="1":
        zero.append(i)
d=bin_sum2(Y)
e=int(Y,2)%(d+1)
f=int(Y,2)%max(1,(d-1))
for i in range(X):
    if i==zero[0]:
        b=max(d-1,1)
        flag=max(0,d-1)
        g=(f-2**(X-1-i)%b+b)%b
        zero.popleft()
    else:
        b=d+1
        flag=1
        g=(e+2**(X-1-i))%b

    if flag==0:
        print(0)
    elif g==0:
        print(1)
    else:
        print(M[g]+1)

Submission status: Runtime Error

Solution code:
def pcmod(n):
    if n==0:
        return 1
    return 1+pcmod(n%bin(n).count('1'))

def main():
    n = int(input())
    x = list(map(int,list(input())))

    m_1 = x.count(1)-1
    m_0 = x.count(1)+1 
    baser_1 = 0
    baser_0 = 0
    for i in range(n):
        baser_1 += x[i] * pow(2,(n-1-i),m_1)
        baser_0 += x[i] * pow(2,(n-1-i),m_0)
        baser_1 %= m_1
        baser_0 %= m_0

    ans = [0]*n

    for i in range(n):
        a = 0
        if x[i]==1:
            t = (baser_1 - pow(2,(n-1-i),m_1))%m_1
            a = pcmod(t)

        if x[i]==0:
            if m_0 ==0:
                ans[i] = 0
                continue
            t = (baser_0 + pow(2,(n-1-i),m_0))%m_0
            a = pcmod(t)
        ans[i] = a

    for a in ans:
        print(a)
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
x = list(input())[::-1]
print(x)
num = 0
nump = 0
numm = 0
pop_num = 0
for i in range(N):
    try:
        if x[i] == "1":
            pop_num += 1
    except:
        while True:
            print("a",end='')
for i in range(N):
    if x[i] == "1":
        num += pow(2,i,pop_num)
        num %= pop_num 
        nump += pow(2,i,pop_num+1)
        nump %= pop_num  + 1
        numm += pow(2,i,pop_num - 1)
        numm %= pop_num - 1



def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

x = x[::-1]
def calc(i,depth,n):
    if depth == 0:
        if x[i] == "1":
            tmp = numm
            tmp -= pow(2,N-i-1,pop_num-1)
            tmp %= (pop_num - 1)
            return calc(i,depth+1,tmp)
        else:
            tmp = nump
            tmp += pow(2,N-i-1,pop_num+1)
            tmp %= (pop_num + 1)
            return calc(i,depth+1,tmp)
    else:
        if n == 0: return depth
        return calc(i,depth+1, n % popcnt(n))
        

for i in range(N):
    exit()
    print(calc(i,0,0))

Submission status: Runtime Error

Solution code:
def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f

n = int(input())
x = input()
cnt = x.count("1")
int_x = int(x, 2)
int_x_mod_plus = int_x % (cnt + 1)
int_x_mod_minus = int_x % (cnt - 1)

for i in range(n):
    if x[i] == "0":
        y = (int_x_mod_plus + (1 << (n - (i + 1))) % (cnt + 1)) % (cnt + 1)
    else:
        y = (int_x_mod_minus - (1 << (n - (i + 1))) % (cnt - 1)) % (cnt - 1)
    if y == 0:
        print(1)
    else:
        ans = 1
        while y > 0:
            y %= popcount(y)
            ans += 1
        print(ans)

Submission status: Runtime Error

Solution code:
LIM=200004
L=[0]*LIM

def bin_sum(Y):
    S=bin(Y)[2:]
    count=0
    for i in range(len(S)):
        count+=int(S[i])
    return count

def bin_sum2(Y):
    count=0
    for i in range(len(Y)):
        count+=int(Y[i])
    return count

for i in range(1,LIM):
    L[i]+=bin_sum(i)

def pop_num(N,b,L):
    if N==0:
        return 0
    v=N%b
    return pop_num(v,L[v],L)+1
    
M=[0]*200005
for i in range(1,200004):
    M[i]+=pop_num(i,L[i],L)
X=int(input())
Y=input()
zero=[]
for i in range(X):
    if Y[i]=="1":
        zero.append(i)
d=bin_sum2(Y)
e=int(Y,2)%(d+1)
f=int(Y,2)%max(1,(d-1))
for i in range(X):
    if i==zero[0]:
        b=max(d-1,1)
        flag=max(0,d-1)
        g=(f-2**(X-1-i)%b+b)%b
        zero.popleft()
    else:
        b=d+1
        flag=1
        g=(e+2**(X-1-i))%b

    if flag==0:
        print(0)
    elif g==0:
        print(1)
    else:
        print(M[g]+1)

Submission status: Runtime Error

Solution code:
N = int(input())
x = list(input())[::-1]
print(x)
num = 0
nump = 0
numm = 0
pop_num = 0
for i in range(N):
    if x[i] == "1":
        pop_num += 1
for i in range(N):
    if x[i] == "1":
        num += pow(2,i,pop_num)
        num %= pop_num 
        nump += pow(2,i,pop_num+1)
        nump %= pop_num  + 1
        numm += pow(2,i,pop_num - 1)
        numm %= pop_num - 1



def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

x = x[::-1]
def calc(i,depth,n):
    if depth == 0:
        if x[i] == "1":
            tmp = numm
            tmp -= pow(2,N-i-1,pop_num-1)
            tmp %= (pop_num - 1)
            return calc(i,depth+1,tmp)
        else:
            tmp = nump
            tmp += pow(2,N-i-1,pop_num+1)
            tmp %= (pop_num + 1)
            return calc(i,depth+1,tmp)
    else:
        if n == 0: return depth
        return calc(i,depth+1, n % popcnt(n))
        

for i in range(N):
    exit()
    print(calc(i,0,0))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    X = int(input(),2)
    LIST = []
    ANS = [0]*N
    TEMP = [0]*N
    CHAIND = [0]*N
    bit = 1

    cnt = count_ones_by_bitmask(X)
    if cnt !=0:
        p = X % (cnt+1)
        m = X % (cnt-1)
    for i in range(N):
        LIST.append(X^bit)
        if LIST[i]!=0:
            ANS[i] = 1
            if (X & bit == 0):
                TEMP[i] = (p + bit % (cnt+1) ) % (cnt+1)
            else:
                TEMP[i] = (m - bit % (cnt-1) ) % (cnt-1)            
        bit = bit<<1


    CHA = list(set(TEMP))

    for i in range(len(CHA)):
        an = 0
        cha = CHA[i]
        cnt = count_ones_by_bitmask(CHA[i])
        while cnt>0:
            an += 1
            cha = cha%cnt
            cnt = count_ones_by_bitmask(cha)
        CHAIND[CHA[i]] = an

    for i in reversed(range(N)):
        print(ANS[i]+CHAIND[TEMP[i]])




def count_ones_by_bitmask(num):
    count = 0
    while num:
        count += num & 1
        num >>= 1
    return count

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def pcmod(n):
    if n==0:
        return 1
    return 1+pcmod(n%bin(n).count('1'))

def main():
    n = int(input())
    x = list(map(int,list(input())))

    m_1 = x.count(1)-1
    m_0 = x.count(1)+1 
    baser_1 = 0
    baser_0 = 0
    for i in range(n):
        baser_1 += x[i] * pow(2,(n-1-i),m_1)
        baser_0 += x[i] * pow(2,(n-1-i),m_0)
        baser_1 %= m_1
        baser_0 %= m_0

    ans = [0]*n

    for i in range(n):
        a = 0
        if x[i]==1:
            t = (baser_1 - pow(2,(n-1-i),m_1))%m_1
            a = pcmod(t)

        if x[i]==0:
            t = (baser_0 + pow(2,(n-1-i),m_0))%m_0
            a = pcmod(t)
        ans[i] = a

    for a in ans:
        print(a)
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def bitcount(N):  # 立ってるbitの数
    bitcnt = [0]
    for _ in range(N):
        bitcnt += [i + 1 for i in bitcnt]
    return bitcnt


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

num, cnt = int(x, 2), x.count('1')
num0, num1 = num % (cnt + 1), num % max(cnt - 1, 1)
lbit = bitcount(18)
for i in range(n):
    ans = 1
    if x[i] == '0':
        tmp = num0 + pow(2, n - (i + 1), cnt + 1)
    elif x[i] == '1':
        if cnt == 1:
            print(0)
            continue
        tmp = num1 - pow(2, n - (i + 1), cnt - 1)
    tmp %= ctmp
    ctmp = lbit[tmp]
    while tmp > 0:
        ans += 1
        tmp %= ctmp
        ctmp = lbit[tmp]
    print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
x = str(input())
X = 0
one = 0
for i in range(n):
    X+=int(x[i])*2**(n-i-1)
    if x[i]=="1":
        one+=1

u = X % one

l = [0, 1]
for i in range(2,n):
    if i%2==0:
        l.append(1)
    else:
        l.append(l[i%bin(i).count("1")]+1)

for i in range(n):
    if x[i]=="0":
        print(l[(X+2**(n-i-1))%(one+1)]+1)
    else:
        print(l[(X-2**(n-i-1))%(one-1)]+1)

Submission status: Runtime Error

Solution code:
N = int(input())
x = list(input())[::-1]
num = 0
nump = 0
numm = 0
pop_num = 0
for i in range(N):
    if x[i] == "1":
        pop_num += 1
for i in range(N):
    if x[i] == "1":
        num += pow(2,i,pop_num)
        num %= pop_num 
        nump += pow(2,i,pop_num+1)
        nump %= pop_num  + 1
        numm += pow(2,i,pop_num - 1)
        numm %= pop_num - 1



def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

x = x[::-1]
def calc(i,depth,n):
    if depth == 0:
        try: 
            if x[i] != "hoge":
                exit()
        except:
            while True:
                print("d")
        if x[i] == "1":
            tmp = numm
            tmp -= pow(2,N-i-1,pop_num-1)
            tmp %= (pop_num - 1)
            return calc(i,depth+1,tmp)
        else:
            tmp = nump
            tmp += pow(2,N-i-1,pop_num+1)
            tmp %= (pop_num + 1)
            return calc(i,depth+1,tmp)
    else:
        if n == 0: return depth
        return calc(i,depth+1, n % popcnt(n))
        

for i in range(N):
    print(calc(i,0,0))

Submission status: Runtime Error

Solution code:
N = int(input())
x = list(input())[::-1]
num = 0
nump = 0
numm = 0
pop_num = 0
for i in range(N):
    if x[i] == "1":
        pop_num += 1
for i in range(N):
    if x[i] == "1":
        num += pow(2,i,pop_num)
        num %= pop_num 
        nump += pow(2,i,pop_num+1)
        nump %= pop_num  + 1
        numm += pow(2,i,pop_num - 1)
        numm %= pop_num - 1



def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

x = x[::-1]
def calc(i,depth,n):
    if depth == 0:
        try x[i] != "hoge":
            exit()
        except:
            while True:
                print("d")
        if x[i] == "1":
            tmp = numm
            tmp -= pow(2,N-i-1,pop_num-1)
            tmp %= (pop_num - 1)
            return calc(i,depth+1,tmp)
        else:
            tmp = nump
            tmp += pow(2,N-i-1,pop_num+1)
            tmp %= (pop_num + 1)
            return calc(i,depth+1,tmp)
    else:
        if n == 0: return depth
        return calc(i,depth+1, n % popcnt(n))
        

for i in range(N):
    print(calc(i,0,0))

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

import numpy as np


#N = 2 * 10 ** 5
#X = np.random.randint(0, 2, N)
#Y = int('0b' + ''.join(X.astype(str).tolist()), 0)

N = int(input())
X = input()
Y = int('0b' + X, 0)
X = np.array(list(X), int)
p = int(X.sum())
m1 = Y % (p + 1)
m2 = Y % max(1, p - 1)


count = np.zeros((N, ))
for n in range(1, N):
    i = np.array(list(bin(n))[2:], int).sum()
    count[n] = 1 + count[n % i]

ans = [0] * N
for n in range(1, N + 1):
    if X[n - 1]:
        p -= 1
        z = m2 - pow(2, N - n, max(1, p))
    else:
        p += 1
        z = pow(2, N - n, p) + m1

    ans[n - 1] = int(count[z] + 1)

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

Submission status: Runtime Error

Solution code:
N = int(input())
x = list(input())[::-1]
num = 0
nump = 0
numm = 0
pop_num = 0
for i in range(N):
    if x[i] == "1":
        pop_num += 1
for i in range(N):
    if x[i] == "1":
        num += pow(2,i,pop_num)
        num %= pop_num 
        nump += pow(2,i,pop_num+1)
        nump %= pop_num  + 1
        numm += pow(2,i,pop_num - 1)
        numm %= pop_num - 1



def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

x = x[::-1]
def calc(i,depth,n):
    if depth == 0:
        if x[i] == "1":
            tmp = numm
            tmp -= pow(2,N-i-1,pop_num-1)
            tmp %= (pop_num - 1)
            return calc(i,depth+1,tmp)
        else:
            tmp = nump
            tmp += pow(2,N-i-1,pop_num+1)
            tmp %= (pop_num + 1)
            return calc(i,depth+1,tmp)
    else:
        if n == 0: return depth
        return calc(i,depth+1, n % popcnt(n))
        

for i in range(N):
    print(calc(i,0,0))

Submission status: Runtime Error

Solution code:
N = int(input())
x = list(input())[::-1]
num = 0
nump = 0
numm = 0
pop_num = 0
for i in range(N):
    if x[i] == "1":
        pop_num += 1
for i in range(N):
    if x[i] == "1":
        num += pow(2,i,pop_num)
        num %= pop_num 
        nump += pow(2,i,pop_num+1)
        nump %= pop_num  + 1
        numm += pow(2,i,pop_num - 1)
        numm %= pop_num - 1



def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

x = x[::-1]
def calc(i,depth,n):
    if depth == 0:
        if x[i] == "1":
            tmp = numm
            tmp -= pow(2,N-i-1,pop_num-1)
            tmp %= (pop_num - 1)
            return calc(i,depth+1,tmp)
        else:
            tmp = nump
            tmp += pow(2,N-i-1,pop_num+1)
            tmp %= (pop_num + 1)
            return calc(i,depth+1,tmp)
    else:
        if n == 0: return depth
        if popcnt(n) == 0:
        return calc(i,depth+1, n % popcnt(n))
        

for i in range(N):
    print(calc(i,0,0))

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

import numpy as np


#N = 2 * 10 ** 5
#X = np.random.randint(0, 2, N)
#Y = int('0b' + ''.join(X.astype(str).tolist()), 0)

N = int(input())
X = input()
Y = int('0b' + X, 0)
X = np.array(list(X), int)
p = int(X.sum())
m1 = Y % (p + 1)
m2 = Y % (p - 1)


count = np.zeros((N, ))
for n in range(1, N):
    i = np.array(list(bin(n))[2:], int).sum()
    count[n] = 1 + count[n % i]

ans = [0] * N
for n in range(1, N + 1):
    if X[n - 1]:
        p -= 1
        z = m2 - pow(2, N - n, p)
    else:
        p += 1
        z = pow(2, N - n, p) + m1

    ans[n - 1] = int(count[z] + 1)

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

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    X = int(input(),2)
    LIST = []
    ANS = [0]*N
    TEMP = [0]*N
    CHAIND = [0]*N
    bit = 1

    cnt = count_ones_by_bitmask(X)
    p = X % (cnt+1)
    m = X % (cnt-1)
    for i in range(N):
        LIST.append(X^bit)
        if LIST[i]!=0:
            ANS[i] = 1
            if (X & bit == 0):
                TEMP[i] = (p + pow(2, i, cnt+1) ) % (cnt+1)
            else:
                TEMP[i] = (m - pow(2, i, cnt-1) ) % (cnt-1)            
        bit = bit<<1


    CHA = list(set(TEMP))

    for i in range(len(CHA)):
        an = 0
        cha = CHA[i]
        cnt = count_ones_by_bitmask(CHA[i])
        while cnt>0:
            an += 1
            cha = cha%cnt
            cnt = count_ones_by_bitmask(cha)
        CHAIND[CHA[i]] = an

    for i in reversed(range(N)):
        print(ANS[i]+CHAIND[TEMP[i]])




def count_ones_by_bitmask(num):
    count = 0
    while num:
        count += num & 1
        num >>= 1
    return count

if __name__ == '__main__':
    main()