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 copy
import numpy as np
N=int(input())
X=list(map(int,input()))
A=[]
for i in range(len(X)):
    S=copy.deepcopy(X)
    S[i]=abs(1-S[i])
    A.append(''.join(map(str,S)))
    
dp=np.array([0,1,1,2])
for i in range(23):
    dp=np.hstack([dp,dp+1])
    
for i in A:
    z=0
    while True:
        if z==0:
            n=int(i,2)
            f=dp[n]
            n=n%f
            z+=1
        else:
            f=dp[n]
            n=n%f
            z+=1
        if n==0:
            print(z)
            break

Submission status: Wrong Answer

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

one_num = X.count("1")
answer = []
for i in range(N):
    target = int(X[i])
    if target == 0:
        plus = pow(2,N-i-1)
        ones = one_num + 1
    else:
        plus = -pow(2,N-i-1)
        ones = one_num-1
    Xnow = X10+plus
    count = 0
    if Xnow == 0:
        answer.append(count)
        continue
    else:
        Xnow = Xnow%ones
        count+=1
        while Xnow > 0:
            Xnow2 = bin(Xnow)
            ones = Xnow2.count("1")
            Xnow = Xnow%ones
            count+=1
        answer.append(count)
    print(*answer,sep="\n")

Submission status: Wrong Answer

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

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


n = int(input())
x = input().rstrip()
x_dec = int(x,base = 2)

pop_cnt = x.count('1')
pop_cnt_0 = (pop_cnt + 1)
pop_cnt_1 = (pop_cnt - 1)
x_0 = pow(x_dec,1,pop_cnt_0)
x_1 = pow(x_dec,1,pop_cnt_1) if pop_cnt_1 > 0 else 0

x_bit = [0]*n

for i in range(n-1,-1,-1):
    if x[i] == '0':
        x_bit[i] = (x_0 + pow(2,n-1-i,pop_cnt_0))%pop_cnt_0
        #x_bit[i] = (x_dec + pow(2,n-1-i))%pop_cnt_0
        
    else:
        if pop_cnt_1 > 0:
            x_bit[i] = (x_1 - pow(2,n-1-i,pop_cnt_1))
            x_bit[i] = x_bit[i] if x_bit[i] >= 0 else x_bit[i] + pop_cnt_1
        else:
            x_bit[i] = 0

anslist = []
for i in range(n):
    ans = 1
    now = x_bit[i]
    while True:
        if now == 0:
            break
        now = now%p_count(now)
        
        ans += 1
    anslist.append(ans)


for ans in anslist:
    print(ans)

Submission status: Wrong Answer

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

one_num = X.count("1")

for i in range(N):
    target = int(X[i])
    if target == 0:
        plus = pow(2,N-i-1)
        ones = one_num + 1
    else:
        plus = -pow(2,N-i-1)
        ones = one_num-1
    Xnow = X10+plus
    count = 0
    if Xnow == 0:
        print(count)
        continue
    else:
        Xnow = Xnow%ones
        count+=1
        while Xnow > 0:
            Xnow2 = bin(Xnow)
            ones = Xnow2.count("1")
            Xnow = Xnow%ones
            count+=1
        print(1)
        #print(count)

Submission status: Wrong Answer

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

one_num = X.count("1")

for i in range(N):
    target = int(X[i])
    if target == 0:
        plus = pow(2,N-i-1)
        ones = one_num + 1
    else:
        plus = -pow(2,N-i-1)
        ones = one_num-1
    print(1)
# =============================================================================
#     Xnow = X10+plus
#     count = 0
#     if Xnow == 0:
#         print(count)
#         continue
#     else:
#         Xnow = Xnow%ones
#         count+=1
#         while Xnow > 0:
#             Xnow2 = bin(Xnow)
#             ones = Xnow2.count("1")
#             Xnow = Xnow%ones
#             count+=1
#         print(count)
# =============================================================================

Submission status: Wrong Answer

Solution code:
n,x=int(input()),input()
o=x.count("1")
if o==1:
    for i,v in enumerate(x):
        if v=="1":print(0)
        else:
            if i!=n-1:
                if x[-1]=="0":print(1)
                else:print(2)
            else:print(0)

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

Submission status: Wrong Answer

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

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


n = int(input())
x = input().rstrip()
x_dec = int(x,base = 2)

pop_cnt = x.count('1')
pop_cnt_0 = pop_cnt + 1
pop_cnt_1 = pop_cnt - 1

x_bit = [0]*n

for i in range(n-1,-1,-1):
    if x[i] == '0':
        x_bit[i] = (x_dec + pow(2,n-1-i))%pop_cnt_0
        
    else:
        if pop_cnt_1 > 0:
            x_bit[i] = (x_dec - pow(2,n-1-i))%pop_cnt_1
        else:
            x_bit[i] = 0

anslist = []
for i in range(n):
    ans = 1
    now = x_bit[i]
    while True:
        if now == 0:
            break
        now = now%p_count(now)
        
        ans += 1
    anslist.append(ans)


for ans in anslist:
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = list(str(input()))
n = 0
nn = 0
for h in range(N):
    n += int(X[h])*(2 **(N-1-h))
nn = bin(n).count('1')
a = 0
aa = 0
for i in range(N):
    if (X[i] == "1"):
        a = n - (2 **(N-1-i))
        aa = nn - 1
    else:
        a = n + (2 **(N-1-i))
        aa = nn + 1
    time = 0
    while a >0:

        a = a % aa
        aa = bin(a).count('1')
        if a == 0:
            break
        time += 1
    print(time+1)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = list(str(input()))
n = 0
nn = 0
for h in range(N):
    n += int(X[h])*(2 **(N-1-h))
nn = bin(n).count('1')
a = 0
aa = 0
for i in range(N):
    if (X[i] == "1"):
        a = n - (2 **(N-1-i))
        aa = nn - 1
    else:
        a = n + (2 **(N-1-i))
        aa = nn + 1
    time = 0
    while a >0:

        a = a % aa
        aa = bin(a).count('1')
        if a == 0:
            break
        time += 1
    print(time)

Submission status: Wrong Answer

Solution code:
n=int(input())
x=input()
chk=0
for i,j in enumerate(x[::-1]):
    if j=="1": chk+=pow(2,i,n*2)
l=[]
for i,j in enumerate(x[::-1]):
    if j=="0": t=(chk+pow(2,i,n))%(n*2)
    elif j=="1": t=(chk-pow(2,i,n)+n)%(n*2)
    ans=0
    while t:
        t%=bin(t).count("1")
        ans+=1
    l.append(ans)
for i in l:
    print(i)

Submission status: Wrong Answer

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

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

def one_str():
    return input()

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

N=one_int()
S=one_str()

bit_count = S.count("1")
S_min = int(S,2) % (bit_count-1) if bit_count-1!=0 else 0
S_plu = int(S,2) % (bit_count+1)
S_num = int(S,2)



calc_dict = {i:-1 for i in range(10000)}
res_dict =  {i:-1 for i in range(10**4)}

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

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

def mods(temp, count):
    count+=1
    if temp!=0:

        if temp in res_dict:
            return count+res_dict[temp]
        
        if temp not in calc_dict:
            calc_dict[temp]= bin(temp).count("1") 
        count = mods(temp%calc_dict[temp], count)

    return count

for i in range(N):
    if S[i]=="0":
        part = (2**(N-i-1))% (bit_count+1)
        num = (S_plu + part ) % (bit_count+1)
        print(mods(num, 0))
    else:
        if S_num == 2**(N-i-1):
            print(0)
            continue
        part = (2**(N-i-1))% (bit_count-1)
        num = (S_min - part)%(bit_count-1)
        print(mods(num, 0))

Submission status: Wrong Answer

Solution code:
n = int(input())
x = input()
original_pop_count = x.count('1')
one_pop_count = original_pop_count-1
zero_pop_count = original_pop_count+1

one_mod = 0
zero_mod= 0
for b in x:
    if one_pop_count!=0:
        one_mod=(one_mod*2+int(b))%one_pop_count
    zero_mod=(zero_mod*2+int(b))%zero_pop_count
#予めf[i]を計算する
f = [0]*220000
pop_count = [0]*220000
for i in range(1,220000):
    pop_count[i]= pop_count[i//2] + i%2
    f[i] = f[i%pop_count[i]]+1
one_pow2 = [1]*220000
zero_pow2 = [1]*220000
for i in range(1,220000):
    if one_pop_count!=0:
        one_pow2[i] = one_pow2[i-1]*2%one_pop_count
    zero_pow2[i] = zero_pow2[i-1]*2%zero_pop_count


for i in range(n-1,-1,-1):
    if x[n-1-i]=='1':
        nxt = one_mod
        nxt-=one_pow2[i]
        if one_pop_count!=0:
            nxt%=one_pop_count
        print(f[nxt]+1)
    if x[n-1-i]=='0':
        nxt = zero_mod
        nxt+=zero_pow2[i]
        nxt%=zero_pop_count
        print(f[nxt]+1)

Submission status: Wrong Answer

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

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

def one_str():
    return input()

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

N=one_int()
S=one_str()

bit_count = S.count("1")
S_min = int(S,2) % (bit_count-1) if bit_count-1!=0 else 0
S_plu = int(S,2) % (bit_count+1)
S_num = int(S,2)



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

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

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

def mods(temp, count):
    count+=1
    while temp!=0:

#         if temp in res_dict:
#             print(count, temp, res_dict[temp])
#             print("come")
#             print()
#             return count+res_dict[temp]
        
#         if calc_dict[temp]==-1:
        bits = bin(temp).count("1")
            
        temp = temp%bits
        count+=1

    return count

for i in range(N):
    if S[i]=="0":
        part = (2**(N-i-1))% (bit_count+1)
        num = (S_plu + part ) #% (bit_count+1)
        print(mods(num, 0))
    else:
        if S_num == 2**(N-i-1):
            print(0)
            continue
        part = (2**(N-i-1))% (bit_count-1)
        num = (S_min - part)#%(bit_count-1)
        print(mods(num, 0))

Submission status: Wrong Answer

Solution code:
n=int(input())
x=input()
chk=0
for i,j in enumerate(x[::-1]):
    if j=="1": chk+=pow(2,i,n)
l=[]
for i,j in enumerate(x[::-1]):
    if j=="0": t=(chk+pow(2,i,n))%n
    elif j=="1": t=(chk-pow(2,i,n)+n)%n
    ans=0
    #print("#t",i,t)
    while t:
        t%=bin(t).count("1")
        ans+=1
    l.append(ans)
for i in l:
    print(i)

Submission status: Wrong Answer

Solution code:
n=int(input())
x=input()
chk=0
for i,j in enumerate(x[::-1]):
    if j=="1": chk+=pow(2,i,n)

for i,j in enumerate(x[::-1]):
    if j=="0": chk=(chk+pow(2,i,n))%n
    elif j=="1": chk=(chk-pow(2,i,n)+n)%n
    ans=0
    t=chk
    while t:
        t%=bin(t).count("1")
        ans+=1
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
#DEBUG=True
DEBUG=False
if DEBUG:
    f=open("202007_2nd/D_input.txt")
else:
    f=sys.stdin
#from 2nd count
def cnt_func(num):
    cnt=0
    while num:
        num%=bin(num).count("1")
        cnt+=1
    return cnt+1
n=int(f.readline().strip())
s=f.readline().strip()
input_val=int(s,2)
input_one_count=s.count("1")
#Base value
zero_first=input_val%(input_one_count+1)
one_first=input_val%(input_one_count-1) if input_one_count>1 else 0
ans=0
for idx,emt in enumerate(s):
    p=n-idx-1
    if emt=="0": #inverted to "1"
        ans=cnt_func((zero_first+(pow(2,p,input_one_count+1)))%(input_one_count+1))
    else: #inverted to "0"
        if input_one_count>1:
            ans=cnt_func((one_first-(pow(2,p,input_one_count-1)))%(input_one_count-1))
        else:
            ans=input_one_count
    print(ans)
f.close()

Submission status: Wrong Answer

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    N = int(input())
    S = input()
    cnt0 = S.count("1")

    if cnt0 == 0:
        print(*[1]*N, sep="\n")
        return

    X = int(S, 2)

    def f2():
        cache = [-1] * (cnt0+1)
        def f2(x):
            if cache[x] != -1: return cache[x]
            if x == 0: return 0

            y = bin(x).count("1")

            x = cache[x] = 1 + f2(x % y)
            return x
        return f2
    f2 = f2()

    dc = {}
    for k, v in (("0", 1), ("1", -1)):
        x = cnt0 + v
        y = X % x if x else 0
        dc[k] = (x, v, y, [1, N-1])

    ans = [0] * N
    for i in reversed(range(N)):
        si = S[i]
        cnt, v, n, m1 = dc[si]

        if cnt == 0:
            ans[i] = 0
            continue

        ni = N - i - 1
        m2 = (m1[0]<<(m1[1]-i)) % cnt
        n = (n + v*m2) % cnt
        m1[0] = m2; m1[1] = i

        ans[i] = 1 + f2(n)

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


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n):
  res = [None] * n
  for i in range(n):
    res[i] = II()
  return res
def LIR(n):
  res = [None] * n
  for i in range(n):
    res[i] = LI()
  return res
def FR(n):
  res = [None] * n
  for i in range(n):
    res[i] = IF()
  return res
def LIR(n):
  res = [None] * n
  for i in range(n):
    res[i] = IF()
  return res
def LIR_(n):
  res = [None] * n
  for i in range(n):
    res[i] = LI_()
  return res
def SR(n):
  res = [None] * n
  for i in range(n):
    res[i] = S()
  return res
def LSR(n):
  res = [None] * n
  for i in range(n):
    res[i] = LS()
  return res
mod = 1000000007
inf = float('INF')

#solve
def solve():
  def f(n, c):
    tmp = n % c
    t = tmp
    b = 0
    while tmp:
      if tmp & 1:
        b += 1
      tmp //= 2
    if t:
      return f(t, b) + 1
    else:
      return 1
  n = II()
  a = S()
  b = 0
  for ai in a:
    if ai == "1":
      b += 1
  a = a[::-1]
  bp = 0
  bm = 0
  if b != 1:
    for i, ai in enumerate(a):
      if ai == "1":
        bp += pow(2, i, b + 1)
        bm += pow(2, i, b - 1)
        bp %= b + 1
        bm %= b - 1
    ans = []
    for i, ai in enumerate(a):
      if ai == "1":
        tmpbm = bm - pow(2, i, b - 1)
        tmpbm %= b - 1
        ans.append(f(tmpbm, b - 1))
      else:
        tmpbp = bp + pow(2, i, b + 1)
        tmpbp %= b + 1
        ans.append(f(tmpbp, b + 1))
    for ai in ans[::-1]:
      print(ai)
    return
  else:
    for i, ai in enumerate(a):
      if ai == "1":
        bp += pow(2, i, b + 1)
        bp %= b + 1
    ans = []
    for i, ai in enumerate(a):
      if ai == "1":
        ans.append(1)
      else:
        tmpbp = bp + pow(2, i, b + 1)
        tmpbp %= b + 1
        ans.append(f(tmpbp, b + 1))
    for ai in ans[::-1]:
      print(ai)
    return


#main
if __name__ == '__main__':
  solve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n):
  res = [None] * n
  for i in range(n):
    res[i] = II()
  return res
def LIR(n):
  res = [None] * n
  for i in range(n):
    res[i] = LI()
  return res
def FR(n):
  res = [None] * n
  for i in range(n):
    res[i] = IF()
  return res
def LIR(n):
  res = [None] * n
  for i in range(n):
    res[i] = IF()
  return res
def LIR_(n):
  res = [None] * n
  for i in range(n):
    res[i] = LI_()
  return res
def SR(n):
  res = [None] * n
  for i in range(n):
    res[i] = S()
  return res
def LSR(n):
  res = [None] * n
  for i in range(n):
    res[i] = LS()
  return res
mod = 1000000007
inf = float('INF')

#solve
def solve():
  def f(n, c):
    tmp = n % c
    t = tmp
    b = 0
    while tmp:
      if tmp & 1:
        b += 1
      tmp //= 2
    if t:
      return f(t, b) + 1
    else:
      return 1
  n = II()
  a = S()
  b = 0
  for ai in a:
    if ai == "1":
      b += 1
  a = a[::-1]
  bp = 0
  bm = 0
  if b != 1:
    for i, ai in enumerate(a):
      if ai == "1":
        bp += pow(2, i, b + 1)
        bm += pow(2, i, b - 1)
        bp %= b + 1
        bm %= b - 1
    ans = []
    for i, ai in enumerate(a):
      if ai == "1":
        tmpbm = bm - pow(2, i, b - 1)
        tmpbm %= b - 1
        ans.append(f(tmpbm, b - 1))
      else:
        tmpbp = bp + pow(2, i, b + 1)
        tmpbp %= b + 1
        ans.append(f(tmpbp, b + 1))
    for ai in ans[::-1]:
      print(ai)
    return
  else:
    for i, ai in enumerate(a):
      if ai == "1":
        bp += pow(2, i, b + 1)
        bp %= b + 1
    ans = []
    for i, ai in enumerate(a):
        tmpbp = bp + pow(2, i, b + 1)
        tmpbp %= b + 1
        ans.append(f(tmpbp, b + 1))
    for ai in ans[::-1]:
      print(ai)
    return


#main
if __name__ == '__main__':
  solve()

Submission status: Wrong Answer

Solution code:
N = int(input())
X = str(input())
count = X.count("1")
num, nump, numm = 0, 0, 0
now, nowp, nowm = 1, 1, 1

if count == 0:
  for i in range(N):
    print(1)
    quit()
elif count == 1:
  if X[-1] == "1":
    for i in range(N):
      if i != N - 1:
        print(2)
      else:
        print(1)
  else:
    for i in range(N):
      if i!= N - 1:
        print(1)
      else:
        print(2)
  quit()
  

xx = [0] * N
x_plus = [0] * N
x_minus = [0] * N
for i in range(1, N + 1):
  if i != 1:
    now *= 2
    nowp *= 2
    
    now %= count
    nowp %= (count + 1)
    

    nowm *= 2
    nowm %= (count - 1)
  
  else:
    now %= count
    nowp %= (count + 1)
    nowm %= (count - 1) 
  xx[i - 1] = now
  x_plus[i - 1] = nowp
  x_minus[i - 1] = nowm
  if X[-i] == "1":
    num += now
    num %= count
    nump += nowp
    nump %= count + 1
    numm += nowm
    numm %= count - 1
    
#print(num, xx, x_plus, x_minus)    

nextn = [0] * N
#ans = [1] * N
for i in range(N):
    if X[i] == "0":
      a = nump + x_plus[N - 1 - i]
      b = count + 1
      #print(a, b)
      nextn[i] = a % b
    else:
      #if count == 2:
      #  nextn[i] = 0
      #else:
        a = numm - x_minus[N - 1 - i]
        b = count - 1
        nextn[i] = a % b
        
#print(nextn)    
for i in range(N):
  if nextn[i] == 0:
    print("1")
  else:
    nownow = nextn[i]
    ans = 1
    while nownow != 0:
      alpha = bin(nownow)[2:]
      beta = str(alpha).count("1")
      nownow %= beta
      ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = str(input())
count = X.count("1")
num, nump, numm = 0, 0, 0
now, nowp, nowm = 1, 1, 1

if count == 0:
  for i in range(N):
    print(1)
    quit()
elif count == 1:
  if X[-1] == "1":
    while True:
      a = 1
    for i in range(N):
      if i != N - 1:
        print(2)
      else:
        print(1)
  else:
    for i in range(N):
      print(1)
  quit()
  

xx = [0] * N
x_plus = [0] * N
x_minus = [0] * N
for i in range(1, N + 1):
  if i != 1:
    now *= 2
    nowp *= 2
    
    now %= count
    nowp %= (count + 1)
    

    nowm *= 2
    nowm %= (count - 1)
  
  else:
    now %= count
    nowp %= (count + 1)
    nowm %= (count - 1) 
  xx[i - 1] = now
  x_plus[i - 1] = nowp
  x_minus[i - 1] = nowm
  if X[-i] == "1":
    num += now
    num %= count
    nump += nowp
    nump %= count + 1
    numm += nowm
    numm %= count - 1
    
#print(num, xx, x_plus, x_minus)    

nextn = [0] * N
#ans = [1] * N
for i in range(N):
    if X[i] == "0":
      a = nump + x_plus[N - 1 - i]
      b = count + 1
      #print(a, b)
      nextn[i] = a % b
    else:
      #if count == 2:
      #  nextn[i] = 0
      #else:
        a = numm - x_minus[N - 1 - i]
        b = count - 1
        nextn[i] = a % b
        
#print(nextn)    
for i in range(N):
  if nextn[i] == 0:
    print("1")
  else:
    nownow = nextn[i]
    ans = 1
    while nownow != 0:
      alpha = bin(nownow)[2:]
      beta = str(alpha).count("1")
      nownow %= beta
      ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = str(input())
count = X.count("1")
num, nump, numm = 0, 0, 0
now, nowp, nowm = 1, 1, 1

if count == 0:
  for i in range(N):
    print(1)
    quit()
elif count == 1:
  if X[-1] == "1":
    #while True:
     # a = 1
    for i in range(N):
      if i != N - 1:
        print(2)
      else:
        print(1)
  else:
    for i in range(N):
      print(1)
  quit()
  

xx = [0] * N
x_plus = [0] * N
x_minus = [0] * N
for i in range(1, N + 1):
  if i != 1:
    now *= 2
    nowp *= 2
    
    now %= count
    nowp %= (count + 1)
    

    nowm *= 2
    nowm %= (count - 1)
  
  else:
    now %= count
    nowp %= (count + 1)
    nowm %= (count - 1) 
  xx[i - 1] = now
  x_plus[i - 1] = nowp
  x_minus[i - 1] = nowm
  if X[-i] == "1":
    num += now
    num %= count
    nump += nowp
    nump %= count + 1
    numm += nowm
    numm %= count - 1
    
#print(num, xx, x_plus, x_minus)    

nextn = [0] * N
#ans = [1] * N
for i in range(N):
    if X[i] == "0":
      a = nump + x_plus[N - 1 - i]
      b = count + 1
      #print(a, b)
      nextn[i] = a % b
    else:
      #if count == 2:
      #  nextn[i] = 0
      #else:
        a = numm - x_minus[N - 1 - i]
        b = count - 1
        nextn[i] = a % b
        
#print(nextn)    
for i in range(N):
  if nextn[i] == 0:
    print("1")
  else:
    nownow = nextn[i]
    ans = 1
    while nownow != 0:
      alpha = bin(nownow)[2:]
      beta = str(alpha).count("1")
      nownow %= beta
      ans += 1
    print(ans)

Submission status: Wrong Answer

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

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

def solve(X):
    Y = int(X, 2)
    c = X.count("1")
    m, p = c-1, c+1
    Ym, Yp = Y%m if m else 0, Y%p
    for i in range(N):
        if X[i] == "1":
            Y = (Ym - pow(2,N-i-1,m))%m if Ym else -1
        else:
            Y = (Yp + pow(2,N-i-1,p))%p
        print(f(Y) + 1 if Y!=-1 else 0)

N = int(input())
solve(input())

Submission status: Wrong Answer

Solution code:
N = int(input())
X = str(input())
count = X.count("1")
num, nump, numm = 0, 0, 0
now, nowp, nowm = 1, 1, 1

if count == 0:
  for i in range(N):
    print("1")
    quit()
elif count == 1:
  if X[-1] == "1":
    for i in range(N):
      if i != N - 1:
        print("2")
      else:
        print("1")
  else:
    for i in range(N):
      print("1")
  quit()
  

xx = [0] * N
x_plus = [0] * N
x_minus = [0] * N
for i in range(1, N + 1):
  if i != 1:
    now *= 2
    nowp *= 2
    
    now %= count
    nowp %= (count + 1)
    

    nowm *= 2
    nowm %= (count - 1)
  
  else:
    now %= count
    nowp %= (count + 1)
    nowm %= (count - 1) 
  xx[i - 1] = now
  x_plus[i - 1] = nowp
  x_minus[i - 1] = nowm
  if X[-i] == "1":
    num += now
    num %= count
    nump += nowp
    nump %= count + 1
    numm += nowm
    numm %= count - 1
    
#print(num, xx, x_plus, x_minus)    

nextn = [0] * N
#ans = [1] * N
for i in range(N):
    if X[i] == "0":
      a = nump + x_plus[N - 1 - i]
      b = count + 1
      #print(a, b)
      nextn[i] = a % b
    else:
      #if count == 2:
      #  nextn[i] = 0
      #else:
        a = numm - x_minus[N - 1 - i]
        b = count - 1
        nextn[i] = a % b
        
#print(nextn)    
for i in range(N):
  if nextn[i] == 0:
    print("1")
  else:
    nownow = nextn[i]
    ans = 1
    while nownow != 0:
      alpha = bin(nownow)[2:]
      beta = str(alpha).count("1")
      nownow %= beta
      ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = str(input())
count = X.count("1")
num, nump, numm = 0, 0, 0
now, nowp, nowm = 1, 1, 1

if count == 0:
  for i in range(N):
    print("1")
    quit()
elif count == 1:
  if X[-1] == "1":
    for i in range(N):
      if i != N - 1:
        print("1")
      else:
        print("2")
  else:
    for i in range(N):
      print("1")
  quit()
  

xx = [0] * N
x_plus = [0] * N
x_minus = [0] * N
for i in range(1, N + 1):
  if i != 1:
    now *= 2
    nowp *= 2
    
    now %= count
    nowp %= (count + 1)
    

    nowm *= 2
    nowm %= (count - 1)
  
  else:
    now %= count
    nowp %= (count + 1)
    nowm %= (count - 1) 
  xx[i - 1] = now
  x_plus[i - 1] = nowp
  x_minus[i - 1] = nowm
  if X[-i] == "1":
    num += now
    num %= count
    nump += nowp
    nump %= count + 1
    numm += nowm
    numm %= count - 1
    
#print(num, xx, x_plus, x_minus)    

nextn = [0] * N
#ans = [1] * N
for i in range(N):
    if X[i] == "0":
      a = nump + x_plus[N - 1 - i]
      b = count + 1
      #print(a, b)
      nextn[i] = a % b
    else:
      #if count == 2:
      #  nextn[i] = 0
      #else:
        a = numm - x_minus[N - 1 - i]
        b = count - 1
        nextn[i] = a % b
        
#print(nextn)    
for i in range(N):
  if nextn[i] == 0:
    print("1")
  else:
    nownow = nextn[i]
    ans = 1
    while nownow != 0:
      alpha = bin(nownow)[2:]
      beta = str(alpha).count("1")
      nownow %= beta
      ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = str(input())
count = X.count("1")
num, nump, numm = 0, 0, 0
now, nowp, nowm = 1, 1, 1

if count == 0:
  for i in range(N):
    print("1")
    quit()
elif count == 1:
  if X[-1] == "1":
    for i in range(N):
      if i != N - 1:
        print("1")
      else:
        print("2")
  else:
    for i in range(N):
      print("1")
  quit()
  

xx = [0] * N
x_plus = [0] * N
x_minus = [0] * N
for i in range(1, N + 1):
  if i != 1:
    now *= 2
    nowp *= 2
    
    now %= count
    nowp %= (count + 1)
    

    nowm *= 2
    nowm %= (count - 1)
  
  else:
    now %= count
    nowp %= (count + 1)
    nowm %= (count - 1) 
  xx[i - 1] = now
  x_plus[i - 1] = nowp
  x_minus[i - 1] = nowm
  if X[-i] == "1":
    num += now
    num %= count
    nump += nowp
    nump %= count + 1
    numm += nowm
    numm %= count - 1
    
print(num, xx, x_plus, x_minus)    

nextn = [0] * N
#ans = [1] * N
for i in range(N):
    if X[i] == "0":
      a = nump + x_plus[N - 1 - i]
      b = count + 1
      #print(a, b)
      nextn[i] = a % b
    else:
      #if count == 2:
      #  nextn[i] = 0
      #else:
        a = numm - x_minus[N - 1 - i]
        b = count - 1
        nextn[i] = a % b
        
#print(nextn)    
for i in range(N):
  if nextn[i] == 0:
    print("1")
  else:
    nownow = nextn[i]
    ans = 1
    while nownow != 0:
      alpha = bin(nownow)[2:]
      beta = str(alpha).count("1")
      nownow %= beta
      ans += 1
    print(ans)

Submission status: Wrong Answer

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

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

def popcount(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

pops = popcount(x)
x_pop_p = x%(pops + 1)
try:
    x_pop_m = x%(pops - 1)
except:
    x_pop_m = 0
#print(x_pop_p)
#print(x_pop_m)
#print()
pows_of_2 = [0]*(n)
pows_of_2[0] = 1
for i in range(1,n):
    pows_of_2[i] = pows_of_2[i-1] * 2
for i in reversed(range(0,n)):
    bit = x^(1<<i)
    #print(bin(bit))
    #print(bit)
    #print(popcount(bit))
    if bit == 0:
        print(0)
        continue
    if x&(1<<i):
        tmp = (x_pop_m - pows_of_2[i])%(pops - 1)
    else:
        tmp = (x_pop_p + pows_of_2[i]) % (pops + 1)
    #print(tmp)
    if tmp == 0:
        print(1)
        continue
    cnt = 2
    tmp_pop = popcount(tmp)
    if tmp_pop == 0:
        print(cnt-1)
        continue
    tmp = tmp % tmp_pop
    while tmp > 0:
        cnt += 1
        tmp_pop = popcount(tmp)
        if tmp_pop == 0:
            print(cnt-1)
            continue
        tmp %= tmp_pop
    print(cnt)
    #print()

Submission status: Wrong Answer

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

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

def solve(X):
    Y = int(X, 2)
    c = X.count("1")
    m, p = c-1, c+1
    Ym, Yp = Y%m if m else -1, Y%p
    for i in range(N):
        if X[i] == "1":
            if Ym == -1:
                print(0)
            else:
                Y = (Ym - pow(2,N-i-1,m))%m
        else:
            Y = (Yp + pow(2,N-i-1,p))%p
        print(f(Y) + 1)

N = int(input())
solve(input())

Submission status: Wrong Answer

Solution code:
n, X = open(0).read().split()
n = int(n)
x = int(X, 2)
X = list(map(int, X))

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

ma = 2 * 10**5 + 1
dp = [0] * ma
for i in range(1, ma):
    dp[i] = dp[i % popcount(i)] + 1

c = popcount(x)
a = x % (c+1)
if c == 1:
    for i in range(n):
        if X[i]:
            print(0)
        else:
            print(dp[(a + pow(2, n-i-1, c+1)) % (c+1)] + 1)
else:
    b = x % (c-1)
    for i in range(n):
        if X[i]:
            print(dp[(b - pow(2, n-i-1, c-1)) % (c-1)] + 1)
        else:
            print(dp[(a + pow(2, n-i-1, c+1)) % (c+1)] + 1)