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:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()


N=int(input())
X=input()
C=X.count("1")

lst=[]
lstcount=[]
for x in [C-1,C+1]:
    flg=0
    if x<=0:
        lst.append(0)
        lstcount.append(0)
    else:
        Z=0
        p=1
        for i in range(N):
            if X[-i-1]=="1":
                Z+=p
            p*=2
            if Z>=x:
                Z%=x
                flg=1
            if flg:
                p%=x
        lst.append(Z)
        lstcount.append(flg)
exit()
#print(lst)
fac1=[1]
fac2=[1]
C1=C-1
C2=C+1
for i in range(N):
    fac1.append(fac1[-1]*2%C1)
    fac2.append(fac2[-1]*2%C2)

for i in range(N):

    _C=C+(1 if X[i]=="0"  else -1 )
    if _C==0:
        print(0)
        continue
    if  X[i]=="0":
        lstidx=1
    else:
        lstidx=0

    idx=(N-1-i)

    value=lst[lstidx]+(fac2[idx] if  X[i]=="0" else fac1[idx])
    bit=value
    count=0
    while value:
        count+=1
        value%=_C
        _C=0
        bit=value
        while bit:
            _C+=bit&1
            bit>>=1
    print(max(count,1))

Submission status: Wrong Answer

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()
d=bin_sum2(Y)
e=int(Y,2)%(d+1)
f=int(Y,2)%max(1,(d-1))
for i in range(X):
    if Y[i]=="0":
        b=d+1
        g=(e+2**(X-1-i))%b
    else:
        b=max(d-1,1)
        g=(f-2**(X-1-i)%b+b)%b
    if d==1:
        print(0)
    elif g==0:
        print(1)
    else:
        print(M[g]+1)

Submission status: Wrong Answer

Solution code:
from functools import lru_cache


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


@lru_cache(maxsize=None)
def rec(n):
    if n == 0:
        return 0
    else:
        return rec(n % popcnt(n)) + 1


n = int(input())
arr = input()

cnt = popcnt(int(arr, 2))
init_big = int(arr, 2) % (cnt + 1)
if cnt == 1:
    init_small = 0
else:
    init_small = int(arr, 2) % (cnt - 1)

li = [0] * n
for i in range(n):
    if arr[i] == "0":
        li[i] = (init_big + (1 << (n - i - 1))) % (cnt + 1)
    elif int(arr[:i] + str(1 ^ int(arr[i])) + arr[i + 1:], 2) == 0 or cnt - 1 == 0:
        continue
    else:
        li[i] = (init_small - (1 << (n - i - 1))) % (cnt - 1)


ans = []

for x in li:
    ans.append(rec(x) + 1)

print(*ans, sep="\n")

Submission status: Wrong Answer

Solution code:
n=int(input())
m=input()
x=int(m,2)
li=list(m)
def popcount(x):
  return bin(x).count("1")
def check(a):
  co=1
  while a!=0:
    co+=1
    a%=popcount(a)
  return co
def yojo(n,a):
  lis=[]
  for i in range(n+1):
    jo=2**i%a
    if jo in lis:
      return lis[n%len(lis)]
    lis.append(jo)
  return(2**n%a)
jpop=popcount(x)
if jpop==0:
  flag=True
jppp=jpop+1
jppm=jpop-1
jop=x%jppp
if jppm<=0:
  jom=-1
else:
  jom=x%jppm

for i in range(n):
  if li[i]=="0":
    a=jop+yojo(n-i-1,jppp)
    if a>=jppp:
      a-=jppp
  else:
    if jom==-1:
      print(0)
      continue
    a=jom-yojo(n-1-i,jppm)
    if a<0:
      a+=jppm
  if a==0:
    print(1)
    continue
  print(check(a))

Submission status: Wrong Answer

Solution code:
def fun(n):
    ops = 0
    while n:
        pc = format(n, 'b').count('1')
        n %= pc
        ops += 1
    return ops

n = int(input())
xs = input()

sm = int(xs, 2)
pc = xs.count('1')

mp = sm % (pc + 1)
mm = sm % (pc - 1) if pc > 1 else 0

for i, x in enumerate(xs, 1):
    df = 1 if x == '1' else -1
    pci = pc + df
    if pci == 0:
        print(0)
        continue

    rest = pow(2, n - i, pci)

    if x == '0':
        smi = (mp + rest) % pci
        print(1 + fun(smi))
    else:
        smi = (mm - rest) % pci
        print(1 + fun(smi))

Submission status: Wrong Answer

Solution code:
n=int(input())
m=input()
x=int(m,2)
li=list(m)
def popcount(x):
  return bin(x).count("1")
def check(a):
  co=1
  while a!=0:
    co+=1
    a%=popcount(a)
  return co
def yojo(n,a):
  lis=[]
  for i in range(n+1):
    jo=2**i%a
    if jo in lis:
      return lis[n%len(lis)]
    lis.append(jo)
  return(2**n%a)
jpop=popcount(x)
if jpop==0:
  flag=True
jppp=jpop+1
jppm=jpop-1
jop=x%jppp
if jppm<=0:
  jom=-1
else:
  jom=x%jppm

for i in range(n):
  if li[i]=="0":
    a=jop+yojo(i,jppp)
    if a>=jppp:
      a-=jppp
  else:
    if jom==-1:
      print(0)
      continue
    a=jom-yojo(i,jppm)
    if a<0:
      a+=jppm
  if a==0:
    print(1)
    continue
  print(check(a))

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

def main():
    N = int(input())
    X = input()

    X_int = int(X, 2)
    pcount_X = popcount(X_int)

    for i,bit in enumerate(X):
        mask = 1 << (N-i-1)
        Xi = X_int ^ mask

        pcount_Xi = pcount_X + (-1)**int(bit)

        n = Xi
        pcount_n = pcount_Xi
        ans = 0
        while n > 0:
            ans += 1
            n %= pcount_n
            pcount_n = popcount(n)
        print(ans)

main()

Submission status: Wrong Answer

Solution code:
n=int(input())
x=str(input())
pop=[0]

for i in range(1,n):
    ni=0
    a=i
    while a:
        a&=(a-1)
        ni+=1
    nii=i%ni
    pop.append(pop[nii]+1)

x1=int(x,2)    

x2=x.count('1')

for i in range(n):
    if x[i]=='1':
        x3=x2-1
        xi=x1-2**(n-1-i)
    else:
        x3=x2+1
        xi=x1+2**(n-1-i)

Submission status: Wrong Answer

Solution code:
n=int(input())
x=str(input())
pop=[0]

for i in range(1,n):
    ni=0
    a=i
    while a:
        a&=(a-1)
        ni+=1
    nii=i%ni
    pop.append(pop[nii]+1)

x1=int(x,2)    

x2=x.count('1')

for i in range(n):
  print(1)

Submission status: Wrong Answer

Solution code:
N = int(input())
x = input()
#print(int(x,2))

#anslist=[0]*N

def popcount(X,ones,count): 

    if ones==0:
        return count
    else:
      #X=X%ones
      return 1
        #X=X%ones
        
        #count+=1

        #ones=str(bin(X)).count("1")
        
        #return popcount(X,ones,count)

GroundOnes=x.count("1")
GroundX=int(x,2)

for i in range(N):
    if x[i]=="1":
        #x_ith="0"
        ones=GroundOnes-1
        X=GroundX-2**(N-i-1)
    else:
        #x_ith="1"
        ones=GroundOnes+1
        X=GroundX+2**(N-i-1)
            

    # print("for loop",i)
    # print("ones",ones)
    # print("new2bit",new2bit)
    # print(" ------ return --- ",popcount(X,ones,0))
    print(popcount(X,ones,0))

Submission status: Wrong Answer

Solution code:
N = int(input())
x = input()
print(int(x,2))

#anslist=[0]*N

def popcount(X,ones,count): 

    if ones==0:
        return count
    else:
        X=X%ones
        
        count+=1

        ones=str(bin(X)).count("1")
        
        return popcount(X,ones,count)

GroundOnes=x.count("1")
GroundX=int(x,2)

for i in range(N):
    if x[i]=="1":
        #x_ith="0"
        ones=GroundOnes-1
        X=GroundX-2**(N-i-1)
    else:
        #x_ith="1"
        ones=GroundOnes+1
        X=GroundX+2**(N-i-1)
            

    # print("for loop",i)
    # print("ones",ones)
    # print("new2bit",new2bit)
    # print(" ------ return --- ",popcount(X,ones,0))
    print(popcount(X,ones,0))

Submission status: Wrong Answer

Solution code:
N = int(input())
x = input()
print(int(x,2))

#anslist=[0]*N

def popcount(X,ones,count): 

    if ones==0:
        return count
    else:
      #X=X%ones
      return 1
        #X=X%ones
        
        #count+=1

        #ones=str(bin(X)).count("1")
        
        #return popcount(X,ones,count)

GroundOnes=x.count("1")
GroundX=int(x,2)

for i in range(N):
    if x[i]=="1":
        #x_ith="0"
        ones=GroundOnes-1
        X=GroundX-2**(N-i-1)
    else:
        #x_ith="1"
        ones=GroundOnes+1
        X=GroundX+2**(N-i-1)
            

    # print("for loop",i)
    # print("ones",ones)
    # print("new2bit",new2bit)
    # print(" ------ return --- ",popcount(X,ones,0))
    print(popcount(X,ones,0))

Submission status: Wrong Answer

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')
lbit = bitcount(18)
for i in range(n):
    tmp = pow(2, n - (i + 1))
    print(tmp)

Submission status: Wrong Answer

Solution code:
n=int(input())
x_str=input()
x_popcount=x_str.count('1')
dp=[0]*(x_popcount+1)
for i in range(1,x_popcount+1):
    popcount=format(i,'b').count('1')
    dp[i]=dp[i%popcount]+1
# print(dp)
x=int(x_str,2)
if x_popcount>1:
    pows_minus=[(2**i)%(x_popcount-1) for i in range(n)]
    # x_minus=x%(x_popcount-1)
    x_minus=0
    for i in range(n):
        if x_str[i]=='1':
            x_minus+=pows_minus[n-1-i]
pows_plus=[(2**i)%(x_popcount+1) for i in range(n)]
# x_plus=x%(x_popcount+1)
x_plus=0
for i in range(n):
    if x_str[i]=='1':
        x_plus+=pows_plus[n-1-i]

for i in range(len(x_str)):
    ## xi=xi mod popcount(x)+-1
    xi=0
    if x_str[i]=='1':
        if x_popcount>1: ## else: xi=0
            xi=(x_minus-pows_minus[n-1-i])%(x_popcount-1)
    else:
        xi=(x_plus+pows_plus[n-1-i])%(x_popcount+1)
    print(dp[xi]+1)

Submission status: Wrong Answer

Solution code:
from functools import lru_cache
from collections import defaultdict

N = int(input())
X = input().strip()

D = defaultdict(int)
D[0] = 0


@lru_cache(maxsize=200005)
def f(x, ans):
    ans += 1
    b = str(bin(x)[2:])
    c = b.count('1')
    m = x % c
    if m == 0:
        return ans
    return f(m, ans)


for i in range(1, 10):
    D[i] = f(i, 0)


cnt1 = X.count('1')
base = int(X, 2)

for i in reversed(range(N)):
    k = 1 << i
    if X[N - i - 1] == '1':
        n = base - k
        cnt = cnt1 - 1
    else:
        n = base + k
        cnt = cnt1 + 1
    if n == 0:
        print(0)
    else:
        m = n % cnt
        if m == 0:
            print(1)
        else:
            print(D[m]+1)

Submission status: Wrong Answer

Solution code:
def popcount(u):
    t = bin(u)
    h = t.count("1")
    return u % h 

n = int(input())
x = list(input())
c = x.count("1") + 1
d = c - 2
if d == -1:
    for i in range(n):
        print(1)
    exit()
elif d == 0:
    p = x.index("1")
    if p == n-1:
        for i in range(n-1):
            print(2)
        print(0)
        exit()
    elif p != n-1:
        for i in range(n):
            if i != p:
                print(1)
            elif i == p:
                print(0)
        exit()

amaric = [1 % c]
amarid = [1 % d]
for i in range(n-1):
    amaric.append((amaric[-1]*2)%c)
    amarid.append((amarid[-1]*2)%d)

motoc = 0
motod = 0
for i in range(n):
    if x[i] == "1":
        motoc += amaric[n-1-i]
        motod += amarid[n-1-i]

for i in range(n):
    if x[i] == "0":
        op = motoc
        op += amaric[n-1-i]
        op %= c
    elif x[i] == "1":
        op = motod
        op -= amarid[n-1-i]
        op %= d
    cou = 1
    while True:
        if op == 0:
            break
        op = popcount(op)
        cou += 1
    print(cou)

Submission status: Wrong Answer

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

x1=int(x,2)    


for i in range(n):
    xi=(2**(n-1)>>i)^x1

Submission status: Wrong Answer

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')
lbit = bitcount(18)
for i in range(n):
    ans = 1
    if x[i] == '0':
        ctmp = cnt + 1
        tmp = num % ctmp + pow(2, n - (i + 1), ctmp)
    elif x[i] == '1':
        ctmp = cnt - 1
        if ctmp == 0:
            print(0)
            continue
        tmp = num % ctmp - pow(2, n - (i + 1), ctmp)
    ctmp = lbit[tmp]
    while tmp > 0:
        ans += 1
        tmp %= ctmp
        ctmp = lbit[tmp]
    print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
x_str=input()
x=int(x_str,2)
x_popcount=x_str.count('1')
dp=[0]*(x_popcount+1)
for i in range(1,x_popcount+1):
    popcount=format(i,'b').count('1')
    dp[i]=dp[i%popcount]+1
# print(dp)
if x_popcount>1:
    x_minus=x%(x_popcount-1)
    pows_minus=[(2**i)%(x_popcount-1) for i in range(n)]
x_plus=x%(x_popcount+1)
pows_plus=[(2**i)%(x_popcount+1) for i in range(n)]

for i in range(len(x_str)):
    ## xi=xi mod popcount(x)+-1
    xi=0
    if x_str[i]=='1':
        if x_popcount>1:
            xi=(x_minus-pows_minus[n-1-i])%(x_popcount-1)
        else:
            xi=0
    else:
        xi=(x_plus+pows_plus[n-1-i])%(x_popcount+1)
    print(dp[xi]+1)

Submission status: Wrong Answer

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

cnt = X.count("1")
div = [0] * (cnt + 10)
for i in range(1, cnt + 10):
    for n in range(20):
        div[i] += i >> n & 1

memo = [-1] * (cnt + 10)
memo[0] = 0
for i in range(1, cnt + 10):
    memo[i] = memo[i % div[i]] + 1

res0 = 0
res1 = 0
for i in range(N):
    if X[i] == "1":
        res0 = (res0 + pow(2, N - i - 1, cnt + 1)) % (cnt + 1)
        
        if cnt - 1 > 0:
            res1 = (res1 + pow(2, N - i - 1, cnt - 1)) % (cnt - 1)

for i in range(N):
    if X[i] == "0":
        div = cnt + 1
        tmp = (res0 + pow(2, N - i - 1, div)) % div
    else:
        if cnt - 1 > 0:
            div = cnt - 1
            tmp = (res1 + div - pow(2, N - i - 1, div)) % div
        else:
            tmp = 0
    print(memo[tmp] + int(cnt > 1))

Submission status: Wrong Answer

Solution code:
N = int(input())
X = input()
memo = {}
X_int = int("0b"+X, 2)


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


pcf = popcount(int("0b"+X, 2))
pcm = pcf - 1
pcp = pcf + 1


def f(n: int, pc: int, ops: int):

    if n == 0:
        return ops
    else:
        if memo.get(n) is None:
            n %= pc
            ops += 1
            pc = popcount(n)
            return f(n, pc, ops)
        else:
            return memo[n]


def rev(x: str, i: int):
    x = list(x)
    if x[i] == "1":
        n = X_int - 2**(N-i-1)
        pc = pcm
    else:
        n = X_int + 2**(N-i-1)
        pc = pcp
    return (n, pc)


if __name__ == "__main__":
    for i in range(N):
        # print(f(*rev(X, i), 0))
        f(*rev(X, i), 0)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = ["0"] + list(input())


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


def count(x):
    c = 0
    while x > 0:
        p = popcount(x)
        x %= p
        c += 1
    return c


p0 = X.count("1")
Xp, Xm = 0, 0  # X mod p0+1, X mod p0-1
for i in range(1, N + 1):
    if X[i] == "1":
        Xp += pow(2, N - i, p0 + 1)
Xp %= p0 + 1
if p0 > 1:
    for i in range(1, N + 1):
        if X[i] == "1":
            Xm += pow(2, N - i, p0 - 1)
    Xm %= p0 - 1
else:
    Xm = 0

for i in range(1, N+1):
    if X[i] == "1":
        p1 = p0 - 1
        if p1 == 0:
            print(0)
        else:
            x = (pow(2, N-i, p1) + p1 - Xm) % p1
            print(count(x)+1)
    else:
        p1 = p0 + 1
        x = (pow(2, N-i, p1) + Xp) % p1
        print(count(x)+1)

Submission status: Wrong Answer

Solution code:
n=int(input())
x=str(input())
pop=[0]



x1=int(x,2)    

a=x1
popi=0
while a:
    a&=(a-1)
    popi+=1
x2=popi

for i in range(n):
    xi=(2**(n-1)>>i)^x1

Submission status: Wrong Answer

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

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

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

    pc_X = X.count('1')

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

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

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

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

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

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

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

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

    r = X.count("1")
    r0 = r-1
    r1 = r+1
    ans = []
    for i in range(N):
        if r == 0:
            ans.append(0)
        
        if X[i] == '0':
            ans.append(f((X_10 % r1 + pow(2, N-1-i)) % r1))
        else:
            if r == 1:
                ans.append(0)
            else:
                ans.append(f((X_10 % r0 - pow(2, N-1-i)) % r0))
    
    print(*ans, sep='\n')

def f(N):
    cnt = 1
    while N != 0:
        N = N % popcount(N)
        cnt += 1
    
    return cnt

def popcount(N):
    b = bin(N)
    cnt = 0
    for i in range(2,len(b)):
        if b[i] == '1':
            cnt += 1

    return cnt

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
N = int(input())
X = ["0"] + list(input())


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


def count(x):
    c = 0
    while x > 0:
        p = popcount(x)
        x %= p
        c += 1
    return c


p0 = X.count("1")
Xp, Xm = 0, 0  # X mod p0+1, X mod p0-1
for i in range(1, N + 1):
    if X[i] == "1":
        Xp += pow(2, N - i, p0 + 1)
Xp %= p0 + 1
if p0 > 1:
    for i in range(1, N + 1):
        if X[i] == "1":
            Xm += pow(2, N - i, p0 - 1)
    Xm %= p0 - 1
else:
    Xm = 0

for i in range(1, N+1):
    if X[i] == "1":
        p1 = p0 - 1
        if p1 == 0:
            print(0)
        else:
            x = (pow(2, N-i, p1) - Xm) % p1
            print(count(x)+1)
    else:
        p1 = p0 + 1
        x = (pow(2, N-i, p1) + Xp) % p1
        print(count(x)+1)

Submission status: Wrong Answer

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

maxbit = x.count("1")
xc0 = x10 % (maxbit + 1)
xc1 = x10 % (maxbit - 1) if maxbit > 1 else 0

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

for i in range(lenx):
  if x[i] == "0":
    t = xc0 + pow(2, (lenx - 1 - i), maxbit + 1)
    ans = f(t % (maxbit + 1)) + 1
  else:
    if maxbit - 1 == 0:
      ans = 0
    else:
      t = xc1 - pow(2, (lenx - 1 - i), maxbit - 1)
      ans = f(t % (maxbit + 1)) + 1
  print(ans)

Submission status: Wrong Answer

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

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

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

    pc_X = X.count('1')

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

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

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

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

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

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

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
from collections import deque

hitCount = 0
H = {}

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

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

def pop(n):
    return "{0:b}".format(n).count('1')

def toZero(n):
    global hitCount
    global H
    if n==0:
        return 0
    if n==1:
        return 1
    if n in H:
        hitCount += 1
        return H[n]
    r = 1 + toZero(n%pop(n))
    H[n] = r
    return r

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

for i in range(N):
    X[i] = complement(X[i])
    n = int("".join(X),2)
    print(toZero(n))
    X[i] = complement(X[i])
print("hitCount", hitCount)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

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

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

pc = X.count("1")

# X == 0 の時
if pc == 0:
    for i in range(N):
        print(1)
    exit()

sml = pc - 1
big = pc + 1

b = 0
mod_s = 0
mod_b = 0
for x in X[::-1]:
    if x == "1":
        if sml:
            mod_s += pow(2, b, sml)
            mod_s %= sml

        mod_b += pow(2, b, big)
        mod_b %= big

    b += 1

# print(mod_s, mod_b, sml, big)


ELE = []

b = 0
for x in X[::-1]:
    if x == "0":
        t = (mod_b + pow(2, b, big)) % big
        ELE.append((t, 1))
    else:
        t = (mod_s - pow(2, b, sml)) % sml if sml else 0
        if t < 0:
            t += sml
        ELE.append((t, 1))
    b += 1


def solve(x, c):
    if x == 0:
        return c

    b = 0
    nx = x
    while nx > 0:
        b += nx & 1
        nx >>= 1

    ret = solve(x % b, c + 1)
    return ret


ANS = []
for x, pc in ELE:
    ANS.append(solve(x, pc))

print("\n".join(map(str, ANS[::-1])))

Submission status: Wrong Answer

Solution code:
N = int(input())
X = input()
tmp = bin(int(X, 2)).count("1")
big = int(X, 2) % (tmp + 1)
small = int(X, 2) % (tmp - 1) if tmp - 1 else 0

for i in range(N):
    ans = 0
    if X[i] == '1':
        if not tmp - 1:
            print(ans)
            exit()

        c = small - pow(2, (N - i - 1), tmp - 1)
        c = c % (tmp - 1)
    else:
        c = big + pow(2, (N - i - 1), tmp + 1)
        c = c % (tmp + 1)
    ans += 1
    while c:
        MOD = bin(int(c)).count("1")
        c %= MOD
        ans += 1
    print(ans)

Submission status: Wrong Answer

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

num_of_1 = x.count("1")

first = int(x, 2)

def f(x):
    if x == 0:
        return 0
    return 1 + f(x % bin(x).count('1'))

if num_of_1 == 1:
    for i in range(n):
        if x[i] == '1':
            print(0)
        elif i == n-1:
            print(2)
        else:
            print(1)
    exit()

first_one, first_zero = first % (num_of_1 - 1), first % (num_of_1 + 1)

for i in range(n):
    ans = 0

    if x[i] == "0":
        a = first_zero + pow(2, n-i-1, num_of_1 + 1)
    else:
        a = first_one - pow(2, n-i-1, num_of_1 - 1)

    ans += 1 + f(a)

    print(ans)

Submission status: Wrong Answer

Solution code:
mem = {}
def popcount(n):
    tn = n
    count = 0
    while True:
        if n in mem:
            return n
        if n == 0:
            break
        n %= bin(n).count('1')
        count += 1
    mem[tn] = count
    return count

N = int(input())
X = int(input(),2)
for i in range(N-1,-1,-1):
    print(popcount(X^(1<<i)))

Submission status: Wrong Answer

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

num_of_1 = x.count("1")

first = int(x, 2)

def f(x):
    if x == 0:
        return 0
    return 1 + f(x % bin(x).count('1'))

if num_of_1 == 1:
    for i in range(n):
        if x[i] == '1':
            print(0)
        elif i == n-1:
            print(2)
        else:
            print(1)
    exit()

first_one, first_zero = first % (num_of_1 + 1), first % (num_of_1 - 1)

for i in range(n):
    ans = 0

    if x[i] == "0":
        a = first_one + pow(2, n-i-1, num_of_1 + 1)
    else:
        a = first_zero - pow(2, n-i-1, num_of_1 - 1)

    ans += 1 + f(a)

    print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
from sys import flags
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
x=list(input())
cnt=Counter(x)
x2=int("".join(x),2)
one=cnt["1"]
# print(x)
# print(math.log2(2*10**5))
# print(cnt)
print(x2,one)
lst=[0]*(2*10**5+10)
# lst[0]=-1
flaglst=[0,0]
if one-1!=0:
    flaglst[0]=x2%(one-1)
flaglst[1]=x2%(one+1)
print(flaglst)

for i in range(2*10**5):
    now=i+1
    ans=0
    while now:
        cnt2=0
        m=0
        while now>=pow(2,m):
            if now&1<<m:
                cnt2+=1
            m+=1
        now%=cnt2
        ans+=1
    lst[i+1]=ans
# # print(lst[:100])

for i in range(n):
    tmp=0
    if x[i]=="1":
        tmp=flaglst[0]
        if one-1!=0:
            tmp-=pow(2,n-1-i,one-1)
            tmp%=one-1
        else:
            print(0)
            continue
    else:
        tmp=flaglst[1]
        tmp+=pow(2,n-1-i,one+1)
        tmp%=one+1
    # print(tmp,pow(2,n-1-i),one)

    print(lst[tmp]+1)

Submission status: Wrong Answer

Solution code:
# D Anything Goes to Zero

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

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

Submission status: Wrong Answer

Solution code:
n=int(input())
x=str(input())
pop=[0]
a=1
b=0
for i in range(1,n):
    ni=0
    a=i
    while a:
        a&=(a-1)
        ni+=1
    nii=i%ni
    pop.append(pop[nii]+1)

Submission status: Wrong Answer

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')
lbit = bitcount(18)
for i in range(n):
    ans = 1
    if x[i] == '0':
        ctmp = cnt + 1
        tmp = num % ctmp + pow(2, n - (i + 1), ctmp) % ctmp
    elif x[i] == '1':
        ctmp = cnt - 1
        if ctmp == 0:
            ans, tmp = 0, 0
        else:
            tmp = num % ctmp - pow(2, n - (i + 1), ctmp) % ctmp
    ctmp = lbit[tmp]
    while tmp > 0:
        ans += 1
        tmp %= ctmp
        ctmp = lbit[tmp]
    print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
x=str(input())
pop=[0]
a=1
b=0
for i in range(1,n):
    ni=0
    a=i
    while a:
        a&=(a-1)
        ni+=1
    nii=i%ni
    pop.append(pop[nii]+1)

x1=int(x,2)    

a=x1
popi=0
while a:
    a&=(a-1)
    popi+=1
x2=popi

Submission status: Wrong Answer

Solution code:
n=int(input())
x=str(input())
pop=[0]
a=1
b=0
for i in range(1,n):
    ni=0
    a=i
    while a:
        a&=(a-1)
        ni+=1
    nii=i%ni
    pop.append(pop[nii]+1)

x1=int(x,2)    

a=x1
popi=0
while a:
    a&=(a-1)
    popi+=1
x2=popi

for i in range(n):
    xi=(2**(n-1)>>i)^x1

Submission status: Wrong Answer

Solution code:
N = int(input())
X = input()
popcount_X = X.count('1')
numX = int(X, 2)
a = numX % (popcount_X + 1)
b = numX % (popcount_X - 1) if popcount_X != 1 else 0
for i, x in enumerate(X, 1): #リストのインデクス，要素，第二引数に開始位置
    if x == '1' and popcount_X == 1:
        print(0)
        continue
    ans = 1
    if x == '1':
        temp = (b - pow(2, N - 1, popcount_X - 1)) % (popcount_X - 1)
    else:
        temp = (a + pow(2, N - i, popcount_X + 1)) % (popcount_X + 1)
    while temp:
        p = format(temp, 'b').count('1') #2進数，1の個数
        temp %= p
        ans += 1
    print(ans)