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 sys
input = sys.stdin.readline
#N, K = (int(i) for i in input().split())
#B = [int(x) for x in input().split()]
#A = [[int(i) for i in input().split()] for i in range(N)]


def my_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


def f(x, cur):
    #print(x, cur)
    cnt = cur
    tmp = x
    while tmp:
        tmp = tmp%my_popcount(tmp)
        cnt +=1
    return cnt


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

Xint = int(X, 2)
popcountX = my_popcount(Xint)
#print("test", Xint, popcountX)
plus = Xint%(popcountX+1)
minus = 0
if popcountX != 1:
    minus = Xint%(popcountX-1)

X = list(X)
for i in range(N):
    if X[i] == "0":
        #print("arg", Xint%(popcountX+1), (2**(N-1-i))%(popcountX+1))
        print(f((plus + (2**(N-1-i))%(popcountX+1))%(popcountX+1), 1))
    else:
        if popcountX == 1:
            print(0)
        else:
            print(f((minus - (2**(N-1-i))%(popcountX-1))%(popcountX-1), 1))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
#N, K = (int(i) for i in input().split())
#B = [int(x) for x in input().split()]
#A = [[int(i) for i in input().split()] for i in range(N)]


def my_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


def f(x, cur):
    #print(x, cur)
    if x == 0:
        return cur
    return f(x%my_popcount(x), cur+1)

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

Xint = int(X, 2)
popcountX = my_popcount(Xint)
#print("test", Xint, popcountX)
plus = Xint%(popcountX+1)
minus = 0
if popcountX != 1:
    minus = Xint%(popcountX-1)

X = list(X)
for i in range(N):
    if X[i] == "0":
        #print("arg", Xint%(popcountX+1), (2**(N-1-i))%(popcountX+1))
        print(f((plus + (2**(N-1-i))%(popcountX+1))%(popcountX+1), 1))
    else:
        if popcountX == 1:
            print(0)
        else:
            print(f((minus - (2**(N-1-i))%(popcountX-1))%(popcountX-1), 1))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
#N, K = (int(i) for i in input().split())
#B = [int(x) for x in input().split()]
#A = [[int(i) for i in input().split()] for i in range(N)]


def my_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


def f(x, cur):
    #print(x, cur)
    if x == 0:
        return cur
    return f(x%my_popcount(x), cur+1)

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

Xint = int(X, 2)
popcountX = my_popcount(Xint)
#print("test", Xint, popcountX)
"""
plus = Xint%(popcountX+1)
minus = 0
if popcountX != 1:
    minus = Xint%(popcountX-1)
"""

X = list(X)
for i in range(N):
    if X[i] == "0":
        #print("arg", Xint%(popcountX+1), (2**(N-1-i))%(popcountX+1))
        print(f((Xint%(popcountX+1) + (2**(N-1-i))%(popcountX+1))%(popcountX+1), 1))
    else:
        if popcountX == 1:
            print(0)
        else:
            print(f((Xint%(popcountX-1) - (2**(N-1-i))%(popcountX-1))%(popcountX-1), 1))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
import math
import copy


def minu_int(i):
    return -1*int(i)


def zz():
    return list(map(int, sys.stdin.readline().split()))


def z():
    return int(sys.stdin.readline())


def S():
    return sys.stdin.readline()


def C(line):
    return [sys.stdin.readline() for _ in range(line)]


def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]


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


N = z()
X = S()
num = pop_count(int(X, 2))
for i in range(N):
    x = int(X, 2)
    if(X[i] == '0'):
        first = num + 1
        x += pow(2, N-i-1)
    else:
        x -= pow(2, N-i-1)
        first = num - 1
    if(x != 0):
        x = x % first
    ans = 1
    while x != 0:
        x = x % pop_count(x)
        ans += 1
    print(ans)

Submission status: Wrong Answer

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

f_list = [0 for i in range(N)]

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

def f(n) :
  if n == 0 :
    return 0
  elif f_list[n] != 0 :
    return f_list[n]
  else :
    index = n % popcount(n)
    f_list[n] = f(index) + 1
    return f_list[n]
  
x_pop = X.count('1')

if x_pop == 0 :
  for i in range(N) :
    print(1)
elif x_pop == 1 :
  for i in range(N) :
    if X[i] == '1' :
      print(0)
    elif i == 0 :
      print(1)
    else :
      print(0)
else :
  mod_plus = [1 for i in range(N)]
  mod_minus = [1 for i in range(N)]
  for i in range(2, N+1) :
    mod_plus[N-i] = mod_plus[N-i+1] * 2
    mod_minus[N-i] = mod_minus[N-i+1] * 2
    if mod_plus[N-i] >= x_pop + 1 :
      mod_plus[N-i] -= x_pop + 1
    if mod_minus[N-i] >= x_pop - 1 :
      mod_minus[N-i] -= x_pop - 1
  x_mod_plus = int(X, 2) % (x_pop + 1)
  x_mod_minus = int(X, 2) % (x_pop - 1)
  
  #print(int(X, 2), x_pop, x_mod_plus, x_mod_minus)
  for i in range(N) :
    #print(mod_plus[i], mod_minus[i])
    if X[i] == '0' :
      ans = x_mod_plus + mod_plus[i]
      if ans >= x_pop + 1 :
        print(f(ans - x_pop - 1)+1)
      else :
        print(f(ans)+1)
    else :
      ans = x_mod_minus - mod_minus[i]
      if ans < 0 :
        print(f(ans + x_pop - 1)+1)
      else :
        print(f(ans)+1)
        
"""
    
for i in range(N) :
  if X[i] == '0' :
    temp_X = X[:i] + '1' + X[i+1:]
  else :
    temp_X = X[:i] + '0' + X[i+1:]
  n = int(temp_X, 2)
  if n < N :
    print(f(n))
  else :
    print(f(n % popcount(n)) + 1)
"""

Submission status: Wrong Answer

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

import math
from collections import defaultdict,deque
ml=lambda:map(int,input().split())
ll=lambda:list(map(int,input().split()))
ii=lambda:int(input())
ip=lambda:list(input())
ips=lambda:input().split()

"""========main code==============="""

def fast_expo(x,y,m):
    res=1
    while(y):
        if(y&1):
            res*=x
            res%=m
        x*=x
        x%=m
        y>>=1
    return res    

dp=defaultdict(int)
dp[1]=1
dp[2]=1
for i in range(3,200001):
    k=i
    cnt=0
    while(k):
        if(k%2): cnt+=1
        k>>=1
    dp[i]=dp[i%cnt]+1
n=ii()
a=ip()
a=a[::-1]
c=a.count('1')

min_1=0
max_1=0

for i in range(n):
    if(a[i]=='1'):
        if(c-1!=0):
            min_1+=fast_expo(2,i,c-1)
            min_1%=(c-1)
        max_1+=fast_expo(2,i,c+1)
        
        max_1%=(c+1)
    
ans=[]    

for i in range(n):
    if(a[i]=='1'):
        if(c-1==0):
            ans.append(0)
        else:    
            ans.append(dp[(min_1-fast_expo(2,i,c-1)+(c-1))%(c-1)]+1)
    else:
        ans.append(dp[(max_1+fast_expo(2,i,c+1))%(c+1)]+1)
ans=ans[::-1]
for i in ans:
    print(i)

Submission status: Wrong Answer

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

#10進数に変換
decX = int(strX,2)

#1の数をカウント
pop_c = strX.count('1')

# X % popcount+1
f_p = decX % (pop_c + 1)

# X % popcount-1(0になる時は0)
if pop_c == 1:
  f_m = 0
else:
  f_m = decX % (pop_c - 1)

for i in range(0,N):
  if strX[i] == '0':
    pop_a = (f_p + (2**(N-1-i))) % (pop_c + 1) 
    Ans = 1
    
  elif strX[i] == '1' and pop_c == 1:
    pop_a = 0
    Ans = 0
    
  else:
    pop_a = (2**(N-1-i) - f_m) % (pop_c - 1)
    Ans = 1
  
  while pop_a > 0:
    wkpop = bin(pop_a).count('1')
    pop_a = pop_a % wkpop
    Ans += 1
  
  print(Ans)

Submission status: Wrong Answer

Solution code:
def popcount(x):
    return bin(x).count("1")
def solve(n):
    if n == 0:
        return 0
    return 1+solve(n % popcount(n))

N = int(input())
X = input()
num_x = int(X, 2)
p_cnt = X.count('1')
if p_cnt == 1:
    for i in range(N):
        if X[i] == '1':
            print(0)
        elif i == N-1:
            print(2)
        else:
            print(1)
    exit()
r0_p = num_x % (p_cnt+1)
r0_m = num_x % (p_cnt-1)
for i in range(N):
    if X[i] == '0':
        c_p_cnt = p_cnt+1
        r = (r0_p + pow(2, (N - 1 - i), c_p_cnt)) % c_p_cnt
    else:
        c_p_cnt = p_cnt-1
        if c_p_cnt == 0:
            print(0)
            continue
        r = (r0_p - pow(2, (N - 1 - i), c_p_cnt)) % c_p_cnt
    print(1 + solve(r % c_p_cnt))

Submission status: Wrong Answer

Solution code:
N = int(input())
num = input()
X = int(num,2)
c = num.count('1')
def A(s):
    if s == 0:
        return 1
    return A(s%(bin(s).count('1'))) + 1
if c==1:
  for i in range(N):
    if num[i] == '1':
      print(0)
    elif i == N-1:
      print(2)
    else:
      print(1)
  exit()
amari1 = X%(c+1)
amari2 = X%(c-1)
for i in range(N):
    if num[i] == '1':
        print(A((amari2-pow(2,N-1-i,c-1))%(c-1)))
    else:
        print(A((amari1+pow(2,N-1-i,c+1))%(c-1)))

Submission status: Wrong Answer

Solution code:
N = int(input())
num = input()
X = int(num,2)
c = num.count('1')
def A(s):
    if s == 0:
        return 1
    return A(s%(bin(s).count('1'))) + 1
if c==1:
  for i in range(N):
    if num[i] == '1':
      print(0)
    elif i == N-1:
      print(2)
    else:
      print(1)
  exit()
amari1 = X%(c+1)
amari2 = X%(c-1)
for i in range(N):
    if num[i] == '1':
        print(A(amari2-pow(2,N-1-i,c-1)))
    else:
        print(A(amari1+pow(2,N-1-i,c+1)))

Submission status: Wrong Answer

Solution code:
N = int(input())
num = input()
X = int(num,2)
c = num.count('1')
def A(s):
    if s == 0:
        return 1
    return A(s%(bin(s).count('1'))) + 1
amari1 = X%(c+1)
if c != 1:
    amari2 = X%(c-1)
    for i in range(N):
        if num[i] == '1':
            ans = A((amari2-2**(N-1-i))%(c-1))
            print(ans)
        else:
            ans = A((amari1+2**(N-1-i))%(c+1))
            print(ans)
else:
    for i in range(N):
        if num[i] == '1':
            print(0)
        else:
            print(2)

Submission status: Wrong Answer

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

decX = int(strX,2)
cnt = strX.count('1')

pop_p = decX % (cnt + 1)

if cnt == 1:
  pop_m = 0
else:
  pop_m = decX % (cnt - 1)

for i in range(0,N):
  if strX[i] == '0':
    pop = ((2**(N-1-i)) % (cnt + 1) + pop_p) % (cnt + 1)
    Ans = 1
    
  elif strX[i] == '1' and cnt == 1:
    pop = 0
    Ans = 0
    
  else:
    pop = (2**(N-1-i) % (cnt - 1) - pop_m) % (cnt - 1)
    Ans = 1
  
  while pop > 0:
    wkcnt = bin(pop).count('1')
    pop = pop % wkcnt
    Ans += 1
  
  print(Ans)

Submission status: Wrong Answer

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

x0 = int('0b'+x,0)

ceil = 2*10**5+2
ppc = [0]*(ceil)

def popcount(n):    
  if n == 0:
    return 0
  if ppc[n] != 0:
    return ppc[n]
    
  b = bin(n).count('1')  
  tmp = n%b
  ppc[n] = popcount(tmp) + 1
  return ppc[n]

c1 = bin(x0).count('1')  
p = 1
ans = [0]*n

if c1-1 == 0:
  x0m1 = 0
else:  
  x0m1 = x0 % (c1 - 1)
x0m0 = x0 % (c1 + 1)

for i in range(n): 
  
  if x[n-i-1] == '1':    
    if x0m1 == 0:
      ans[i] = 0
      continue
      
    tmp = (x0m1 - p) % (c1 - 1)
  
    if c1-1 == 0:
      tmp = 0
    else:
      tmp2 = tmp % (c1 - 1)
      
  else:    
    tmp = (x0m0 + p) % (c1 + 1)
    tmp2 = tmp % (c1 + 1)
    
  if tmp > ceil:      
    ans[i]=popcount(tmp2)+2
  else:
    ans[i]=popcount(tmp)+1
  p *= 2
  
for i in range(n):
  print(ans[-1-i])

Submission status: Wrong Answer

Solution code:
N = int(input())
X = str(input())
motosuji = int(X,2)
X = list(X)
motokosu = X.count("1")
#print(motosuji,motokosu)
MAX = 2*pow(10,5)+10
base = [0 for _ in range(MAX)] #0から19までの答えを保存
for i in range(MAX):
  now = i
  temp = 0
  while now != 0:
    ones = 0
    tnow = now*1
    for t in range(len(bin(now))-2):
      if (now>>t)&1 == 1:
        ones += 1
    #print(i,ones,now)
    now = now%ones
    #print(now,base[now])
    base[i] = base[now] + 1
    break
    #temp += 1
  #base[i] = temp
#print(base)
A = []
for i in range(N): #i桁目を入れ替える
  if X[i] == "0": #その桁が0なら1にする
    kosu = motokosu + 1
    suji = motosuji + pow(2,N-1-i,kosu)
  else: #その桁が1なら0にする
    kosu = motokosu - 1
    if kosu == 0:
      suji = 0
    else:
      suji = motosuji - pow(2,N-1-i,kosu)
    
  #print(suji,kosu)
  if suji == 0:
    ans = 0
  else:
    nxt = suji%kosu
    ans = 1+base[nxt]
  #A.append(ans)
  print(ans)

#print(*A,sep="\n")
#print(2**17)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = str(input())
motosuji = int(X,2)
X = list(X)
motokosu = X.count("1")
#print(motosuji,motokosu)
MAX = 2*pow(10,5)+10
base = [0 for _ in range(MAX)] #0から19までの答えを保存
for i in range(MAX):
  now = i
  temp = 0
  while now != 0:
    ones = 0
    tnow = now*1
    for t in range(20):
      if (now>>t)&1 == 1:
        ones += 1
    #print(i,ones,now)
    now = now%ones
    #print(now,base[now])
    base[i] = base[now] + 1
    break
    #temp += 1
  #base[i] = temp
#print(base)
A = []
for i in range(N): #i桁目を入れ替える
  if X[i] == "0": #その桁が0なら1にする
    suji = motosuji + pow(2,N-1-i)
    kosu = motokosu + 1
  else: #その桁が1なら0にする
    suji = motosuji - pow(2,N-1-i)
    kosu = motokosu - 1
    
  #print(suji,kosu)
  if suji == 0:
    nxt = 0
  else:
    nxt = suji%kosu
  ans = 1+base[nxt]
  A.append(ans)

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

Submission status: Wrong Answer

Solution code:
N = int(input())
X = str(input())
motosuji = int(X,2)
X = list(X)
motokosu = X.count("1")
#print(motosuji,motokosu)
MAX = 2*pow(10,5)+10
base = [0 for _ in range(MAX)] #0から19までの答えを保存
for i in range(MAX):
  now = i
  temp = 0
  while now != 0:
    ones = 0
    tnow = now*1
    for t in range(20):
      if (now>>t)&1 == 1:
        ones += 1
    #print(i,ones,now)
    now = now%ones
    temp += 1
  base[i] = temp
#print(base)
A = []
for i in range(N): #i桁目を入れ替える
  if X[i] == "0": #その桁が0なら1にする
    suji = motosuji + pow(2,N-1-i)
    kosu = motokosu + 1
  else: #その桁が1なら0にする
    suji = motosuji - pow(2,N-1-i)
    kosu = motokosu - 1
    
  #print(suji,kosu)
  if suji == 0:
    nxt = 0
  else:
    nxt = suji%kosu
  ans = 1+base[nxt]
  A.append(ans)

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain, product
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    N = ii()
    X = input()
    X_POP = X.count('1')
    X_POP_P = X_POP + 1
    X_POP_N = X_POP - 1
    FX_P = 0
    FX_N = 0
    for i, b in enumerate(X):
        FX_P <<= 1
        FX_N <<= 1
        if b=='1':
            FX_P += 1
            FX_N += 1
        FX_P %= X_POP_P
        FX_N %= X_POP_N or 1
    #
    def popcount(n):
        return bin(n).count('1')
    def f(n):
        if n==0:
            return 0
        else:
            return f(n % popcount(n)) + 1
    ans = []
    for i, b in enumerate(reversed(X)):
        if b=='0':
            fx = (FX_P + pow(2, i, X_POP_P)) % X_POP_P
        else:
            if X_POP_N==0:
                fx = 0
            else:
                fx = (FX_N - pow(2, i, X_POP_N)) % X_POP_N
        ans.append(f(fx)+1)
    print(*reversed(ans))



main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain, product
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    N = ii()
    X = input()
    X_POP = X.count('1')
    X_POP_P = X_POP + 1
    X_POP_N = max(X_POP - 1, 1)
    FX_P = 0
    FX_N = 0
    for i, b in enumerate(X):
        FX_P <<= 1
        FX_N <<= 1
        if b=='1':
            FX_P += 1
            FX_N += 1
        FX_P %= X_POP_P
        FX_N %= X_POP_N
    #
    def popcount(n):
        return bin(n).count('1')
    def f(n):
        if n==0:
            return 0
        else:
            return f(n % popcount(n)) + 1
    ans = []
    for i, b in enumerate(reversed(X)):
        if b=='0':
            fx = (FX_P + pow(2, i, X_POP_P)) % X_POP_P
        else:
            fx = (FX_N - pow(2, i, X_POP_N)) % X_POP_N
        ans.append(f(fx)+1)
    print(*reversed(ans))



main()

Submission status: Wrong Answer

Solution code:
from sys import stdin,stdout                           #
import math                                            #
import heapq                                           #
                                                       #
t = 1                                                  #
def aint():                                            #
	return int(input().strip())                        #
def lint():                                            #
	return list(map(int,input().split()))              #
def fint():                                            #
	return list(map(int,stdin.readline().split()))     #
                                                       #	
########################################################
def f(n):
	if n==0:
		return 0
#	print(n)
	N=n
	cnt=0
	while(N):
		cnt+=N&1
		N>>=1
	return f(n%cnt)+1

def main():
	n=aint()
	x=input()
	c=x.count("1")
	if(c==0):
		for i in range(n):
			print("1")
		return
	elif(c==1):
		for i in range(n):
			if(x[i]=="1"):
				print(0)
			elif x[i]=="0":
				if x[n-1]=="1":
					print("2")
				else:
					print(1)
		return
	mod1=c+1
	mod2=c-1
	mul1=1
	mul2=1
	rem1=0
	rem2=0
	for i in range(n-1,-1,-1):
		if(x[i]=='1'):
			rem1=(rem1+mul1)%mod1
			rem2=(rem2+mul2)%mod2
		mul1=(2*mul1)%mod1
		mul2=(2*mul2)%mod2
	ans=[]
	mul1=1
	mul2=1
#	print(mod1,mod2)
#	print(rem1,rem2)
	for i in range(n-1,-1,-1):
		if(x[i]=='0'):
#			print("At index",i,"val",(rem1+mul1)%mod1)
			ans.append(f((rem1+mul1)%mod1)+1)
		else:
#			print("At index",i,"val",(rem2-mul2)%mod2)
			ans.append(f((rem2-mul2)%mod2)+1)
		mul1=(2*mul1)%mod1
		mul2=(2*mul2)%mod2
#	print("Ans:")
	for i in range(n-1,-1,-1):
		print(ans[i])
	return

#t=int(input())

########################################################
for i in range(t):                                     #
	#print("Case #"+str(i+1)+":",end=" ")		       #
	main()                                             #

Submission status: Wrong Answer

Solution code:
def pc(x):
    return format(x, 'b').count('1')


N = int(input())
X = input()
Xo = int(X, 2)

count = 0
ans = 0
ori = pc(Xo)
X = list(X)

Xp = Xo%(ori + 1)
if ori == 1:
    Xm = 0
else:
    Xm = Xo % (ori - 1)

# for i in range(N-1, -1, -1):
for i in range(N):
    if ori == 1 and X[i] == '1':
        print(0)
        continue
    else:
        if X[i] == '1':
            # ans = Xm - pow(2, i, ori - 1)
            ans = Xm - pow(2, N-1-i, ori - 1)
            ans %= ori - 1
        else:
            # ans = Xp - pow(2, i, ori + 1)
            ans = Xm + pow(2, N-1-i, ori + 1)
            ans %= ori + 1
    count = 1
    while ans > 0:
        # count += 1
        # if ans == 1:
        #     break
        ans %= pc(ans)
        count += 1

   
    print(count)
    count = 0

Submission status: Wrong Answer

Solution code:
def pc(x):
    return format(x, 'b').count('1')


N = int(input())
X = input()
Xo = int(X, 2)

count = 0
ans = 0
ori = pc(Xo)
X = list(X)

Xp = Xo%(ori + 1)
if ori == 1:
    Xm = 0
else:
    Xm = Xo % (ori - 1)

# for i in range(N-1, -1, -1):
for i in range(N):
    if ori == 1 and X[i] == '1':
        print(0)
        continue
    else:
        if X[i] == '1':
            # ans = Xm - pow(2, i, ori - 1)
            ans = Xm - pow(2, N-1-i, ori - 1)
            ans %= ori - 1
        else:
            # ans = Xp - pow(2, i, ori + 1)
            ans = Xm - pow(2, N-1-i, ori + 1)
            ans %= ori + 1
    count = 1
    while ans > 0:
        # count += 1
        # if ans == 1:
        #     break
        ans %= pc(ans)
        count += 1

   
    print(count)
    count = 1

Submission status: Wrong Answer

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

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

def solve(n,cnt):
    if n == 0:
        return 0
    p = popcnt(n)
    l = n % p
    cnt += popcnt(l)
    return cnt
    
N = int(input())
P = input()
I = P.count("1")
Df = int(P,2)
Ans = [1]
#print(solve(N,cnt))

for i in range(1, N+1):
    cnt = 1
    Ans.append(solve(i, cnt)+1)
#print("Ans = ", Ans)

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

if P[N-1] == "1":
    tmp = Df - 1
    cur = I - 1
else:
    tmp = Df + 1
    cur = I + 1
if cur == 0:
    print(0)
else:
    print(Ans[tmp%cur])

Submission status: Wrong Answer

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

def solve(n,cnt):
    if n == 0:
        return 0
    p = popcnt(n)
    l = n % p
    cnt += popcnt(l)
    return cnt
    
N = int(input())
P = input()
I = P.count("1")
Df = int(P,2)
Ans = [1]
#print(solve(N,cnt))

for i in range(1, N+1):
    cnt = 1
    Ans.append(solve(i, cnt)+1)
#print("Ans = ", Ans)

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

if P[N-1] == "1":
    tmp = Df - 1
    cur = I - 1
else:
    tmp = Df + 1
    cur = I + 1
if cur == 0:
    print(0)
else:
    print(Ans[tmp%cur])

Submission status: Wrong Answer

Solution code:
n=int(input())
x=input()
count_x=x.count("1")
px10=0
nx10=0
xi=[0]*n
ans=[0]*(n+1)
for i in range(1,n+1):
    popcount=format(i,"b").count("1")
    fx=i%popcount
    ans[i]=ans[fx]+1
for i in range(n):
    px10+=(int(x[i])*pow(2,n-1-i,count_x+1))%(count_x+1)
    if count_x!=0 and count_x!=1:
        nx10+=int(x[i])*pow(2,n-1-i,count_x-1)%(count_x-1)
for i in range(n):
    if x[i]=="0":
        xi10=(px10+pow(2,n-1-i,count_x+1))%(count_x+1)
        print(ans[xi10]+1)
    else:
        if count_x!=1:
            xi10=(nx10-pow(2,n-1-i,count_x-1))%(count_x-1)
        else:
            xi10=0
        print(ans[xi10]+1)

Submission status: Wrong Answer

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


N = int(input())
X = input()
f = 0
count = 1
c = []
ans = 0
fi = 0
ori = X.count("1")
result = 0
for i in range(N-1, -1, -1):
    fi = toggle_nth_bit(int(X, 2), i)
    if X[i] == "1":
        result = ori - 1
    else:
        result = ori + 1
    if result != 0:
        ans = fi % result
    else:
        print(0)
        continue
    while ans > 0:
        count += 1
        if ans == 1:
            break
        ans = ans % bin(ans).count("1")

   
    print(count)
    count = 1

Submission status: Wrong Answer

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


original_popcount=x.count('1')
one_to_zero_p=original_popcount-1
zero_to_one_p=original_popcount+1
X=int(x,2)

f=[0]*n

for i in range(n):
    if x[i]=='1':
        if one_to_zero_p==0:
            continue
        f[i]=(X-pow(2,n-1-i))%one_to_zero_p
    else:
        f[i]=(X+pow(2,n-1-i))%zero_to_one_p

n_max=3*10**5
dp=[0]*n_max
for i in range(1,n+1):
    p=bin(i).count('1')
    nxt=i%p
    dp[i]=dp[nxt]+1

for i in f:
    if i==0:
        print(1)
    else:
        print(dp[i]+1)

Submission status: Wrong Answer

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


N = int(input())
X = input()
f = 0
count = 1
c = []
ans = 0
fi = 0
ori = X.count("1")
result = 0
for i in range(N-1, -1, -1):
    # print(i)
    fi = toggle_nth_bit(int(X, 2), i)
    # f = bin(toggle_nth_bit(int(X, 2), i))
    if X[i] == "1":
        result = ori - 1
    else:
        result = ori + 1
    # f = toggle_nth_bit(int(X, 2), i)
    if result != 0:
        ans = fi % result
    else:
        print(0)
        continue
    while ans != 0:
        # f = bin(fi)
        count += 1
        if ans == 1:
            break
        # ans = ans % popcount(ans)
        ans = ans % bin(ans).count("1")

        # print(f)
        # print(fi)
        # count += 1
        # print(count)
    # c.append(count)
    print(count)
    count = 1

# ans = str(bin(toggle_nth_bit(int(X,2), 0)))
# for i in c:
#     print(i)

Submission status: Wrong Answer

Solution code:
n = int(input())
x = input()
x2 = int(x, 2)
c = x.count('1')

for i in range(n):
    k = 1 << (n-i-1)
    if int(x[i]):
        y = x2 - k
        c1 = c-1
    else:
        y = x2 + k
        c1 = c+1
    if y == 0:
        print(0)
        continue
    surplus = y % c1
    cnt = 1