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: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random,resource

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    s = S()
    t = int(s, 2)

    m = {}
    m[0] = 0
    def f(i):
        if i in m:
            return m[i]

        c = 0
        ii = i
        while ii > 0:
            c += ii % 2
            ii //= 2

        t = i % c
        m[i] = f(t) + 1
        return m[i]

    c = len([_ for _ in s if _ == '1'])
    r = []
    k = 2 ** (n-1)
    for i in range(n):
        if t == k:
            r.append(1)
        elif s[i] == '1':
            r.append(f((t - k) % (c-1)) + 1)
        else:
            r.append(f((t + k) % (c+1)) + 1)
        k //= 2

    return JA(r, "\n")


print(main())

Submission status: Wrong Answer

Solution code:
def resolve():
    N = int(input())
    X = input()
    Xint = int(X,2)
    popX = X.count("1")
    if popX == 1:
        idx = (N-1) - X.find("1")
        for i in range(N):
            if i == idx:
                print(0)
            else: 
                if i != N-1:
                    if X[-1] == "0":
                        print(1)
                    else:
                        print(2)
                else:
                    print(2)
        return

    Xmod_plus =  Xint % (popX+1)
    Xmod_minus = Xint % (popX-1)

    pop_2expi_p = {0:1}
    pop_2expi_m = {0:1}
    for i in range(1,N):
        pop_2expi_p[i] = pop_2expi_p[i-1] * 2 % (popX+1)
        pop_2expi_m[i] = pop_2expi_m[i-1] * 2 % (popX-1)

    for i in range(N):
        count = 1
        if X[i] == "1":
            nX = (Xmod_minus - pop_2expi_m[N-1-i] ) % (popX-1) 
        if X[i] == "0":
            nX = (Xmod_plus + pop_2expi_p[N-1-i] ) % (popX+1) 
        for j in range(N):
            if nX == 0:
                break
            else:
                nX %= bin(nX).count("1")              
                count += 1
        print(count)
resolve()

Submission status: Wrong Answer

Solution code:
def resolve():
    N = int(input())
    X = input()
    Xint = int(X,2)
    popX = X.count("1")
    if popX == 1:
        idx = (N-1) - X.find("1")
        for i in range(N):
            if i == idx:
                print(0)
            elif i != N-1:
                if X[-1] == "0":
                    print(1)
                else:
                    print(2)
            else:
                print(2)
        return

    Xmod_plus =  Xint % (popX+1)
    Xmod_minus = Xint % (popX-1)

    pop_2expi_p = {0:1}
    pop_2expi_m = {0:1}
    for i in range(1,N):
        pop_2expi_p[i] = pop_2expi_p[i-1] * 2 % (popX+1)
        pop_2expi_m[i] = pop_2expi_m[i-1] * 2 % (popX-1)

    for i in range(N):
        count = 1
        if X[i] == "1":
            nX = (Xmod_minus - pop_2expi_m[N-1-i] ) % (popX-1) 
        if X[i] == "0":
            nX = (Xmod_plus + pop_2expi_p[N-1-i] ) % (popX+1) 
        for j in range(N):
            if nX == 0:
                break
            else:
                nX %= bin(nX).count("1")              
                count += 1
        print(count)
resolve()

Submission status: Wrong Answer

Solution code:
def resolve():
    N = int(input())
    X = input()
    Xint = int(X,2)
    popX = X.count("1")
    if popX == 1:
        idx = (N-1) - X.find("1")
        for i in range(N):
            if i == idx:
                print(0)
            else:
                print(2)
        return

    Xmod_plus =  Xint % (popX+1)
    Xmod_minus = Xint % (popX-1)

    pop_2expi_p = {0:1}
    pop_2expi_m = {0:1}
    for i in range(1,N):
        pop_2expi_p[i] = pop_2expi_p[i-1] * 2 % (popX+1)
        pop_2expi_m[i] = pop_2expi_m[i-1] * 2 % (popX-1)

    for i in range(N):
        count = 1
        if X[i] == "1":
            nX = (Xmod_minus - pop_2expi_m[N-1-i] ) % (popX-1) 
        if X[i] == "0":
            nX = (Xmod_plus + pop_2expi_p[N-1-i] ) % (popX+1) 
        for j in range(N):
            if nX == 0:
                break
            else:
                nX %= bin(nX).count("1")              
                count += 1
        print(count)
resolve()

Submission status: Wrong Answer

Solution code:
def resolve():
    N = int(input())
    X = input()
    Xint = int(X,2)
    popX = X.count("1")
    if popX == 1:
        idx = (N-1) - X.find("1")
        for i in range(N):
            if i == idx:
                print(0)
            else:
                print(min(i+2, idx+2))
        return

    Xmod_plus =  Xint % (popX+1)
    Xmod_minus = Xint % (popX-1)

    for i in range(N):
        count = 1
        if X[i] == "1":
            nX = (Xmod_minus - 2 ** (N-1-i) % (popX-1) ) % (popX-1) 
        if X[i] == "0":
            nX = (Xmod_plus + 2 ** (N-1-i) % (popX+1) ) % (popX+1) 
        for j in range(N):
            if nX == 0:
                break
            else:
                nX %= bin(nX).count("1")              
                count += 1
        print(count)
resolve()

Submission status: Wrong Answer

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

memo = {}


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


def f(n):
    if n == 0:
        return 0
    if n in memo:
        return memo[n]
    memo[n] = 1 + f(n % popcount(n))
    return memo[n]


Xint = int(X, 2)
p = popcount(Xint)
if 1 < p:
    x1 = Xint % (p - 1)
x2 = Xint % (p + 1)
ans = []
b = 1
if 1 < p:
    bmod1 = b % (p - 1)
bmod2 = b % (p + 1)
for i in range(N):
    if X[-1 - i] == '1':
        if 1 < p:
            ans.append(1 + f((x1 - bmod1) % (p - 1)))
        else:
            ans.append(1)
    else:
        ans.append(1 + f((x2 + bmod2) % (p + 1)))
    b <<= 1
    if 1 < p:
        bmod1 = bmod1 * 2 % (p - 1)
    bmod2 = bmod2 * 2 % (p + 1)
for a in reversed(ans):
    print(a)

Submission status: Wrong Answer

Solution code:
import sys
import math
import collections
import heapq
import queue
import itertools
import functools
import operator
import time

readline = sys.stdin.readline
 
IPS = lambda: readline().rstrip()
IP = lambda: int(readline().rstrip())
MP = lambda: map(int, readline().split())
LS = lambda: list(map(int, readline().split()))

def solve():
    for _ in range(1):
        n = IP()
        x = IPS()
        ln = len(x)-1
        
        for i in range(ln,-1,-1):
            nw,ans = n ^ (1<<i), 0
        
            while nw!=0:
                cnt = bin(nw)[2:].count('1')
                nw = nw%cnt
                ans += 1
                
            print(ans)
       
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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

memo1 = {}
memo2 = {}


def popcount(n):
    if n in memo2:
        return memo2[n]
    memo2[n] = bin(n).count('1')
    return memo2[n]


def f(n):
    if n in memo1:
        return memo1[n]
    res = 0
    while 0 < n:
        n = n % popcount(n)
        res += 1
    memo1[n] = res
    return res


for i in range(N):
    b = 1 << (N - 1 - i)
    x = X ^ b
    print(f(x))

Submission status: Wrong Answer

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


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


memo = {}


def f(n):
    if n in memo:
        return memo[n]
    res = 0
    while 0 < n:
        n = n % popcount(n)
        res += 1
    memo[n] = res
    return res


for i in range(N):
    b = 1 << (N - 1 - i)
    x = X ^ b
    print(f(x))

Submission status: Wrong Answer

Solution code:
from sys import stdin,stdout
def INPUT():return list(int(i) for i in stdin.readline().split())
def inp():return stdin.readline()
def out(x):return stdout.write(x)
import math
###############################################################################\
def power(a,p,m):
    if m==0:
        return 0
    res=1
    while(p>0):
        if p&1:
            res=(res*a)%m
        a=(a*a)%m
        p//=2
    return res%m
n=int(input())
s=input()
A=list(int(i) for i in s)
R=[]
for i in range(n-1,-1,-1):
    R.append(A[i])
one=0
for e in A:
    if e==1:
        one+=1
max=one+1
min=one-1
ansmax=0
ansmin=0
#print(one)
for i in range(n):
    ansmax=(ansmax+power(2,i,max)*(R[i]))%max
    if min!=0:
        ansmin=(ansmin+power(2,i,min)*R[i])%min
def popcount(z):
    ans=0
    while(z!=0):
        if z%2==1:
            ans+=1
        z//=2
    return ans
#print(ansmax,ansmin)
B=[]
for i in range(n):
    if R[i]==1:
        if min!=0:
            r=(ansmin-power(2,i,min))%min
            count=1
            while(r!=0):
                count+=1
                r=r%popcount(r)
        else:
            count=1
        B.append(count)
    else:
        r=(ansmax+power(2,i,max))%max
        count=1
        while(r!=0):
            count+=1
            r=r%popcount(r)
        B.append(count)
B.reverse()
for ele in B:
    print(ele)

Submission status: Wrong Answer

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

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

def popcount(n):
    cnt = 0
    while n > 0:
        cnt += n & 1
        n //= 2
    return cnt
def f(n):
    cnt = 0
    while n != 0:
        n = n % popcount(n)
        cnt += 1
    return cnt

ones = X.count('1')
MOD1 = ones + 1
MOD2 = ones - 1
pow1 = [0] * (len(X) + 1)
pow2 = [0] * (len(X) + 1)
if MOD2 != 0:
    pow1[0] = 1
    pow2[0] = 1
    for i in range(1, len(X) + 1):
        pow1[i] = (pow1[i - 1] * 2) % MOD1
        pow2[i] = (pow2[i - 1] * 2) % MOD2
else:
    for i in range(1, len(X) + 1):
        pow1[i] = (pow1[i - 1] * 2) % MOD1

X1 = 0
X2 = 0
for i in range(N):
    if X[i] == '1':
        X1 += pow1[N - i - 1]
        X2 += pow2[N - i - 1]
X1 %= MOD1
if MOD2 != 0:
    X2 %= MOD2

for i in range(N):
    d = N - i - 1
    if X[i] == '0':
        x = (X1 + pow1[d]) % MOD1
        print(f(x) + 1)
    else:
        if MOD2 != 0:
            x = (X2 - pow2[d]) % MOD2
            print(f(x) + 1)
        else:
            print(0)

Submission status: Wrong Answer

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

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

def popcount(n):
    cnt = 0
    while n > 0:
        cnt += n & 1
        n //= 2
    return cnt
def f(n):
    cnt = 0
    while n != 0:
        n = n % popcount(n)
        cnt += 1
    return cnt

ones = X.count('1')
MOD1 = ones + 1
MOD2 = ones - 1
pow1 = [0] * (len(X) + 1)
pow2 = [0] * (len(X) + 1)
if MOD2 != 0:
    pow1[0] = 1
    pow2[0] = 1
    for i in range(1, len(X) + 1):
        pow1[i] = (pow1[i - 1] * 2) % MOD1
        pow2[i] = (pow2[i - 1] * 2) % MOD2

X1 = 0
X2 = 0
for i in range(N):
    if X[i] == '1':
        X1 += pow1[N - i - 1]
        X2 += pow2[N - i - 1]
X1 %= MOD1
if MOD2 != 0:
    X2 %= MOD2

for i in range(N):
    d = N - i - 1
    x = 0
    if X[i] == '0':
        x = (X1 + pow1[d]) % MOD1
        print(f(x) + 1)
    else:
        if MOD2 != 0:
            x = (X2 - pow2[d]) % MOD2
            print(f(x) + 1)
        else:
            print(0)

Submission status: Wrong Answer

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

X_int = int(X,2)
popcount = X.count('1')

co = [0] * (N + 1)
for i in range(1,N+1):
    a = bin(i)[2:]
    cnt = a.count('1')
    nex = i % cnt
    if nex != 0:
        co[i] = nex + 1
    else:
        co[i] = 1

for i in range(N):
    if X[i] == '0':
        x = X_int + pow(2, N - i - 1)
        p_cnt = popcount + 1
        print(co[x % p_cnt] + 1)
    else:
        x = X_int - pow(2, N - i - 1)
        p_cnt = popcount - 1
        if p_cnt != 0:
            print(co[x % p_cnt] + 1)
        else:
            print(0)

Submission status: Wrong Answer

Solution code:
n=int(input())

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

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

one_cnt=popcount(X)

modp=X%(one_cnt+1)
modm=X%(one_cnt-1) if one_cnt-1!=0 else 0

for i in range(n):
    if s[i]==1:
        if cnt==1:
            print(0)
            continue
        else:
            num=(modm-pow(2,n-i-1,one_cnt-1))%(one_cnt-1)
    else:
        num=(modp+pow(2,n-i-1,one_cnt+1))%(one_cnt+1)


    cnt=1
    while num!=0:
        num=num%popcount(num)
        cnt+=1
    print(cnt)

Submission status: Wrong Answer

Solution code:
n=int(input())

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

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

one_cnt=popcount(X)

modp=X%(one_cnt+1)
modm=X%(one_cnt-1) if one_cnt-1!=0 else 0

for i in range(n):
    if s[i]==1:
        if cnt==1:
            print(0)
            continue
        else:
            num=(modm-pow(2,n-i-1,one_cnt-1))%(one_cnt-1)
    else:
        num=(modp+pow(2,n-i-1,one_cnt+1))%(one_cnt+1)

    if num==0:
        print(1)
    else:
        cnt=1
        while 1:
            num=num%popcount(num)
            cnt+=1
            if num==0:
                print(cnt)
                break

Submission status: Wrong Answer

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

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

def f(x):
    cnt = 0
    while x > 0:
        x %= popcount(x)
        cnt += 1
    return cnt

for i in range(0, len(xl)):
    t = (x - (1 << n - i)) if xl[i] == '1' else x + (1 << n - i)
    print(f(t))

Submission status: Wrong Answer

Solution code:
n=int(input())
x=input()
p=x.count('1')

#愚直に解く関数を定義
def solve(n):
    count=0
    while n:
        popcount=bin(n).count('1')
        n%=popcount
        count+=1
    return count+1

#popcount(x)が0,1だった場合に対応
if p==0:
    for i in range(n):
        print(1)
    exit()
elif p==1:
    z=x.index('1')
    for i in range(n):
        if i==z:
            print(0)
        else:
            tmp=(pow(2,z,p+1)+pow(2,i,p+1))%(p+1)
            print(solve(tmp))
    exit()


#2^i mod(p+1),2^i mod(p-1)のリストを作成
a,b=[],[]
for i in range(n):
    a.append(pow(2,i,p+1))
    b.append(pow(2,i,p-1))

#x mod(p+1),x mod(p-1)を計算
a1,b1=0,0
for i in range(n):
    if x[-1-i]=='1':
        a1+=a[i]
        b1+=b[i]

#本計算
for i in range(n):
    if x[i]=='1':
        tmp=(b1-b[-1-i])%(p-1)
    else:
        tmp=(a1+a[-1-i])%(p+1)
    print(solve(tmp))

Submission status: Wrong Answer

Solution code:

import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce
from itertools import groupby
from heapq import heapify, heappush, heappop

# sys.setrecursionlimit(5000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return map(lambda x: x + d, A)
def ldec(A, d=1): return map(lambda x: x - d, A)

N = n1()
X = int(s1(), 2)

def flip(n, i):
    return n ^ (1 << i)

popcount = lambda x: bin(x).count("1")
bits = lambda x, n = 0: bin(x)[2:].zfill(n)

dp = {}

def search(n):
    if n == 0:
        return 0

    if n in dp:
        return dp[n]

    m = n % popcount(n)
    t = search(m) + 1
    dp[n] = t
    return t

#for i in range(N-1, -1, -1):
#    print(search(flip(X, i)))

p = popcount(X)
r1 = X % (p + 1)
r2 = X % (p - 1) if p > 1 else 0

for i in range(N-1, -1, -1):
    Y = flip(X, i)

    if Y == 0:
        print(0)
        continue

    b = bits(X, N)[i]
    if b == 0:
        t = (r1 + 1 << i) % (p + 1)
    else:
        if p == 1:
            print(1)
            continue
        else:
            t = (r2 - 1 << i) % (p - 1)

    print(search(Y))

Submission status: Wrong Answer

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

pop_X = sum(map(int,list(X)))
X_10 = int('0b'+X,2)
r_0 = X_10%(pop_X+1)
zero_flag = False
if pop_X == 1:
    zero_flag = True
else:
    r_1 = X_10%(pop_X-1)

answer = []
diff = 1
for i in range(N)[::-1]:
    if X[i]=='0':
        r = (r_0+diff%(pop_X+1))%(pop_X+1)
    else:
        if zero_flag:
            answer.append(0)
            break
        else:
            r = (r_1-diff%(pop_X-1))%(pop_X-1)
    count = 1
    while True:
        if r == 0:
            break
        pop = sum(map(int,list(bin(r)[2:])))
        r = r % pop
        count += 1
        
    answer.append(count)
    diff *= 2

for i in answer[::-1]:
    print(i)

Submission status: Wrong Answer

Solution code:
def p(x):
  a = list(bin(x))
  return a.count('1')

def f(x):
  if x == 0:
    return 0
  return f(x%p(x)) + 1

N = int(input())
X = input()
##最初の操作だけこっちでやっちゃう
cnt = X.count('1')
x = int(X,2)
a = x % (cnt + 1)
if cnt != 1:
  b = x % (cnt - 1)

for i in range(N):
  if X[i] == '0':
    k = (a + 2**(N-i-1) % (cnt + 1)) % (cnt + 1)
  if X[i] == '1':
    if cnt == 1:
      k = 0
      continue
    k = (b - 2**(N-i-1) % (cnt - 1)) % (cnt - 1)  
  print(f(k)+1)

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

Solution code:
n=int(input())
bn=input()
ans=[]
moto=bn.count('1')
for i in range(-1,-n-1,-1):
  mm=moto
  a=n
  t=abs(i)-1
  if bn[i]=='0':
    a+=2**t
    mm+=1
  else:
    if mm==1:
      ans.append(0)
      continue
    a-=2**t
    mm-=1
  cnt=0
  while a>0:
    a%=mm
    mm=str(format(a,'b')).count('1')
    cnt+=1
  ans.append(cnt)
ans.reverse()
if len(ans)==0:
  print(0)
  exit()
for aa in ans:
  print(aa)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_str():
    return readline().strip()


def slv(N, X):
    C = X.count('1')
    cmr = 0
    cpr = 0
    for b in X:
        b = int(b)
        cpr = ((cpr * 2) + b) % (C+1)
        if C-1 != 0:
            cmr = ((cmr * 2) + b) % (C-1)

    ans = []
    for i in range(N):
        t = 1
        if X[i] == '0':
            x = (cpr + pow(2, N-i-1, C+1)) % (C+1)
        elif X[i] == '1' and C-1 != 0:
            x = (cmr - pow(2, N-i-1, C-1)) % (C-1)
        else:
            x = 0

        while x != 0:
            x %= bin(x).count('1')
            t += 1

        ans.append(t)

    return ans


def main():
    N = read_int()
    X = read_str()
    print(*slv(N, X), sep='\n')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

count = x.count('1')
number = int(''.join(x), 2)

def f(num, cnt):
    if num == 0:
        return cnt
    popcount = format(num, 'b').count('1')
    return f(num % popcount, cnt+1)

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

Submission status: Wrong Answer

Solution code:
n=int(input())
bn=input()
ans=[]
moto=bn.count('1')
for i in range(-1,-n-1,-1):
  mm=moto
  a=n
  t=abs(i)-1
  if bn[i]=='0':
    a+=2**t
    mm+=1
  else:
    a-=2**t
    mm-=1
  cnt=0
  while a>0:
    a%=mm
    mm=str(format(a,'b')).count('1')
    cnt+=1
  ans.append(cnt)
ans.reverse()
if len(ans)==0:
  print(0)
  exit()
for aa in ans:
  print(aa)

Submission status: Wrong Answer

Solution code:
n=int(input())
bn=input()
ans=[]
moto=bn.count('1')
for i in range(-1,-n-1,-1):
  mm=moto
  a=n
  t=abs(i)-1
  if bn[i]=='0':
    a+=2**t
    mm+=1
  else:
    a-=2**t
    mm-=1
  cnt=0
  while a>0:
    a%=mm
    mm=str(format(a,'b')).count('1')
    cnt+=1
  ans.append(cnt)
ans.reverse()
for aa in ans:
  print(aa)

Submission status: Wrong Answer

Solution code:
def f(n):
    ret = 1
    while True:
        if n == 0:
            break
        n %= bin(n).count('1')
        ret += 1
    return ret

if __name__ == "__main__":
    n = int(input())
    x = input()
    cnt = x.count('1')

    if cnt == 1:
        for k in x[:-1]:
            if k == '0':
                print(1)
            else:
                print(0)
        if x[-1] == '1':
            print(0)
        else:
            print(2)
        exit()

    xNum = 0
    for k in x:
        xNum <<= 1
        if k == '1':
            xNum += 1

    p = xNum % (cnt + 1)
    m = xNum % (cnt - 1)

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

Submission status: Wrong Answer

Solution code:
def f(n):
    ret = 1
    while True:
        if n == 0:
            break
        n %= bin(n).count('1')
        ret += 1
    return ret

if __name__ == "__main__":
    n = int(input())
    x = input()
    cnt = x.count('1')

    if cnt == 1:
        for k in x[:len(x)]:
            if x == '0':
                if x[-1] == '1':
                    print(2)
                else:
                    print(1)
            else:
                print(0)
        exit()

    xNum = 0
    for k in x:
        xNum <<= 1
        if k == '1':
            xNum += 1

    p = xNum % (cnt + 1)
    m = xNum % (cnt - 1)

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

Submission status: Wrong Answer

Solution code:
#%%
import sys
N = int(input())
X = input()

#%%

def popcount(n):
    temp = bin(n)[2:]
    return temp.count("1")

pop_memo = [0] * 220000
for i in range(220000):
    pop_memo[i] = popcount(i)

pop_origin = X.count("1")
pop_one = pop_origin - 1
pop_zero = pop_origin + 1

if pop_one == 0:
    print(0)
    sys.exit()

f_cnt = [0] * 220000
for i in range(1, 220000):
    f_cnt[i] = f_cnt[i % pop_memo[i]] + 1

#pow_cnt = [0] * N
#for i in range(N):
#    pow_cnt[i] = pow(2, i)
#pow_cnt.reverse()

X_int = int(X, 2)
for i in range(N):
    if X[i] == "1"and pop_one != 0:
        temp = X_int - pow(2, N - i - 1)
        n = temp % pop_one
        print(f_cnt[n] + 1)
    
    elif X[i] == "0":
        temp = X_int + pow(2, N - i - 1)
        n = temp % pop_zero
        print(f_cnt[n] + 1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys
from functools import lru_cache

sys.setrecursionlimit(4100000)

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

def main():
    N = int(input())
    X = input()
    O = int(X, 2)
    pc = X.count('1')
    Y = list(X)
    ans = [0] * N
    pre = 1
    for i in range(N):
        if Y[i] == '1' and (pc - 1) > 0:
            tmp = (O - pow(2, N - i - 1, pc - 1)) % (pc - 1)
            ans[i] = f(tmp) + 1
        else:
            tmp = (O + pow(2, N - i - 1, pc + 1)) % (pc + 1)
            ans[i] = f(tmp) + 1
        print(ans[i])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
x=input()
import sys
sys.setrecursionlimit(10**7)
if n==1:
  print(1 if x=='1' else 0)
  exit()
def pc(x):
  a=bin(x)[2:]
  return a.count('1')
def func(x):
  if x==0:
    return 0
  else:
    return func(x%pc(x))+1
pcx=x.count('1')
if pcx==0:
  for _ in range(n):
    print(1)
else:
  x0,x1=0,0
  for i in range(n):
    if x[i]=='1':
      if pcx!=1:
        x0+=pow(2,n-1-i,pcx-1)
        x0%=pcx-1
      x1+=pow(2,n-1-i,pcx+1)
      x1%=pcx+1
  for i in range(n):
    ans=0
    if x[i]=='1':
      if pcx==1:
        print(0)
      else:
        xx=x0-pow(2,n-1-i,pcx-1)
        xx%=pcx-1
        print(func(xx)+1)
    else:
      xx=x1+pow(2,n-1-i,pcx+1)
      xx%=pcx+1
      print(func(xx)+1)

Submission status: Wrong Answer

Solution code:
n=int(input())
x=input()
import sys
sys.setrecursionlimit(10**7)
if n==1:
  print(1 if x=='1' else 0)
  exit()
def pc(x):
  a=bin(x)[2:]
  return a.count('1')
def func(x):
  if x==0:
    return 0
  else:
    return func(x%pc(x))+1
pcx=x.count('1')
if pcx==1:
  print(0)
  for _ in range(n-2):
    print(1)
  print(2)
else:
  x0,x1=0,0
  for i in range(n):
    if x[i]=='1':
      x0+=pow(2,n-1-i,pcx-1)
      x0%=pcx-1
      x1+=pow(2,n-1-i,pcx+1)
      x1%=pcx+1
  for i in range(n):
    ans=0
    if x[i]=='1':
      xx=x0-pow(2,n-1-i,pcx-1)
      xx%=pcx-1
      print(func(xx)+1)
    else:
      xx=x1+pow(2,n-1-i,pcx+1)
      xx%=pcx+1
      print(func(xx)+1)

Submission status: Wrong Answer

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

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

memo = {}
def f(n):
  if n in memo: return memo[n]
  popcount = bin(n).count("1")
  if popcount==0:
    d = 0
  else:
    d = n%popcount

  if d == 0:
    memo[n] = 1
    return 1
  else:
    memo[n] = 1 + f(d)
    return memo[n]

X = X[::-1]
P = 0
for i in range(N):
  if X[i]=="1":
    P += 1<<i

for i in range(N-1, -1, -1):
  if (P>>i)&1:
    p = P - (1<<i)
  else:
    p = P + (1<<i)

  if p in memo:
    print(memo[p])
  else:
    f(p)
    print(memo[p])

Submission status: Wrong Answer

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


n=int(input())
x=input()
num=int(x,2)
cnt=popcount(num)

A=[]
for i in range(n):
    if x[i]=="1" and cnt==1:A.append(-1)
    elif x[i]=="1":
        num %=cnt-1
        A.append((num-pow(2,n-i-1,cnt-1))%(cnt-1))
    else:
        num %=cnt+1
        A.append((num+pow(2,n-i-1,cnt+1))%(cnt+1))

B=[]
for i in A:
    if i==-1:B.append(0)
    else:
        point=1
        while i!=0:
            i %=popcount(i)
            point +=1
        B.append(point)

for i in B:
    print(i)

Submission status: Wrong Answer

Solution code:
def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f


n=int(input())
x=input()
num=int(x,2)
cnt=popcount(num)

mod1=num%(cnt+1)
mod2=num%(cnt-1) if cnt-1!=0 else 0

for i in range(n):
    if x[i]=="0":
        ans=(mod1+pow(2,n-i-1,cnt+1))%(cnt+1)
    else:
        if cnt-1==0:
            print(0)
            continue
        else:
            ans=(mod2-pow(2,n-i-1,cnt-1))%(cnt-1)
    point=1
    while ans!=0:
        ans %=popcount(ans)
        point +=1
    print(point)

Submission status: Wrong Answer

Solution code:
def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f


n=int(input())
x=input()
num=int(x,2)
cnt=popcount(num)
mod1,mod2=num%(cnt+1),num%(cnt-1) if cnt-1!=0 else 0

for i in range(n):
    if x[i]=="0":
        ans=(mod1+pow(2,n-i-1,cnt+1))%(cnt+1)
    elif x[i]=="1" and cnt<=1:
        print(0)
        continue
    else:
        ans=(mod2-pow(2,n-i-1,cnt-1))%(cnt-1)
    point=1
    while ans!=0:
        ans %=popcount(ans)
        point +=1
    print(point)