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:
n = int(input())
x = input()

f = [-1] * (n+10)
f[0] = 0

for i in range(1, n+10):
    # python bitcount で見つけたこれを参考に https://ameblo.jp/316228/entry-10518720149.html
    f[i] = f[i % bin(i).count('1')] + 1

init_bitcount = x.count('1')
# Xを init_bitcount+1とinit_bitcount-1で割った余り

x_mod_01 = 0
x_mod_10 = 0
for digit in x:
    x_mod_01 *= 2
    x_mod_10 *= 2
    if digit == '1':
        x_mod_01 += 1
        x_mod_10 += 1
    x_mod_01 %= (init_bitcount+1)
    if init_bitcount != 1:
        x_mod_10 %= (init_bitcount-1)

# print(x_mod_01, x_mod_10, init_bitcount)

power_mod_01 = [-1] * (n+10)
power_mod_01[0] = 1
for i in range(1, n+10):
    power_mod_01[i] = power_mod_01[i-1] * 2 % (init_bitcount + 1)

if init_bitcount != 1:
    power_mod_10 = [-1] * (n+10)
    power_mod_10[0] = 1
    for i in range(1, n+10):
        power_mod_10[i] = power_mod_10[i-1] * 2 % (init_bitcount - 1)


for i in range(n):
    if x[i] == '0':
        # 0→1
        first_residue = (x_mod_01 + power_mod_01[n - i - 1]) % (init_bitcount+1)
        print(f[first_residue] + 1)
    else:
        if init_bitcount == 1:
            print(1)
            continue
        # 1→0
        first_residue = (x_mod_10 - power_mod_10[n - i - 1]) % (init_bitcount-1)
        print(f[first_residue] + 1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
read = sys.stdin.read
#readlines = sys.stdin.readlines
from collections import defaultdict

def main():
    def from10to2(p):
        res = []
        while p:
            p, t = divmod(p, 2)
            res.append(str(t))
        return "".join(res[::-1])

    def from2to10(p):
        res = 0
        num2 = 1
        for c in p[::-1]:
            if c == '1':
                res += num2
            num2 *= 2
        return res

    def f(p):
        if p == 0:
            return 0
        elif d1[p] > 0:
            return d1[p]
        else:
            ppop = from10to2(p).count('1')
            p2 = p % ppop
            fp = f(p2) + 1
            d1[p] = fp
            return fp

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

    numof1 = x.count('1')
    bin2_p = [0] * n
    num2 = 1
    for i1 in range(1, n+1):
        bin2_p[-i1] = num2
        num2 = (num2 * 2) % (numof1 + 1)

    bin2_m = [0] * n
    num2 = 1
    if numof1 == 1:
        pass
    else:
        for i1 in range(1, n+1):
            bin2_m[-i1] = num2
            num2 = (num2 * 2) % (numof1 - 1)

    xas10 = from2to10(x)
    xas10_p = xas10 % (numof1 + 1)
    if numof1 == 1:
        xas10_m = 0
    else:
        xas10_m = xas10 % (numof1 - 1)
    d1 = defaultdict(int)
    d1[0] = 0
    for j1 in range(n):
        if x[j1] == '1':
            t0 = xas10_m - bin2_m[j1]
            if numof1 != 1:
                t0 = t0 % (numof1 - 1)
            if t0 == 0:
                print(1)
            else:
                print(f(t0) + 1)
        else:
            t0 = xas10_p + bin2_p[j1]
            t0 = t0 % (numof1 + 1)
            if t0 == 0:
                print(1)
            else:
                print(f(t0) + 1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
'''Author- Akshit Monga'''
n=int(input())
x=input()
# x=x[::-1]
ans1=0
ans2=0
c=x.count('1')
for i in range(0,n):
    if x[i]=='1':
        ans1=(ans1+pow(2,i,c+1))%(c+1)
        if c!=1:
            ans2=(ans2+pow(2,i,c-1))%(c-1)
to_print=[]
for i in range(0,n):
    if x[i]=='1':
        if c==1:
            to_print.append(0)
            continue
        var=(ans2%(c-1)-pow(2,i,c-1))%(c-1)
        a = 1
        while var:
            var = var % bin(var).count('1')
            a += 1
        to_print.append(a)
    else:
        # print(ans1)
        var = (ans1%(c+1) + pow(2, i, c +1))%(c+1)
        # print(c+1)
        # print(var)
        a = 1
        while var:
            var = var % bin(var).count('1')
            a += 1
        to_print.append(a)
for i in to_print:
    print(i)

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())
x = int(input(), 2)

# 事前計算
cnt = popcnt(x)
init_big = x % (cnt + 1)
if cnt == 1:
    init_small = 0
else:
    init_small = x % (cnt - 1)

# 差分計算
result = []
for i in range(n):
    if not (x >> i) & 1:
        result.append((init_big + pow(2, i, cnt + 1)) % (cnt + 1))
    elif x == 1 << i or cnt - 1 == 0:
        result.append(0)
    else:
        result.append((init_small - pow(2, i, cnt - 1)) % (cnt - 1))

ans = []
for x in result[::-1]:
    ans.append(rec(x) + 1)

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

Submission status: Wrong Answer

Solution code:
import sys
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

def popcount(num):
    cnt = 0
    while num > 0:
        num %= bin(num).count('1')
        cnt += 1
    return cnt

def Main():
    n = read_int()
    x = read_str()
    x_int = int(x, 2)

    cnt = x.count('1')
    minus_cnt = cnt - 1
    plus_cnt = cnt + 1
    
    minus_mod = x_int % minus_cnt if minus_cnt != 0 else 0
    plus_mod = x_int % plus_cnt

    for i in range(n):
        if x[i] == '0':
            print(popcount((plus_mod + pow(2, n - 1 - i, plus_cnt)) % plus_cnt) + 1)
        elif minus_mod != 0:
            print(popcount((minus_mod - pow(2, n - 1 - i, minus_cnt)) % minus_cnt) + 1)
        else:
            print(0)

if __name__ == '__main__':
    Main()

Submission status: Wrong Answer

Solution code:
N=int(input())
X=input()
num_X = int(X, base=2)
pop_x = X.count("1")
if pop_x <= 1:
    mod0 = pop_x + 1
    res0 = num_X % mod0
else:
    mod1 = pop_x - 1
    mod0 = pop_x + 1
    res1 = num_X % (mod1)
    res0 = num_X % (mod0)

# pops = [0]*(N+20)
for i in range(N):
    tmp = 0
    if X[i] == "0":
        # +
        tmp = (res0 + pow(2, N-i-1, mod0))%mod0
    else:
        if pop_x == 1:
            print(0)
            exit()
        tmp = (res1 - pow(2, N-i-1, mod1))%mod1
    
    if tmp == 0:
        print(1)
        continue
    cnt = 1
    while tmp != 0:
        pop = bin(tmp).count("1")
        tmp %= pop
        cnt += 1
    print(cnt)

Submission status: Wrong Answer

Solution code:
N=int(input())
X=input()
num_X = int(X, base=2)
pop_x = X.count("1")
if pop_x <= 1:
    mod0 = pop_x + 1
    res0 = num_X % mod0
else:
    mod1 = pop_x - 1
    mod0 = pop_x + 1
    res1 = num_X % (mod1)
    res0 = num_X % (mod0)

# pops = [0]*(N+20)
for i in range(N):
    tmp = 0
    if X[i] == "0":
        # +
        tmp = (res0 + pow(2, N-i-1, mod0))%mod0
    else:
        if pop_x == 1:
            print(1)
            exit()
        tmp = (res1 - pow(2, N-i-1, mod1))%mod1
    
    if tmp == 0:
        print(1)
        continue
    cnt = 1
    while tmp != 0:
        pop = bin(tmp).count("1")
        tmp %= pop
        cnt += 1
    print(cnt)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


N = I()
X = LI2()
X.reverse()

if N == 1 and len(X) == 1 and X[0] == 0:
    print(0)
    exit()


def popcount(n):
    res = 0
    m = n.bit_length()
    for i in range(m):
        res += (n >> i) & 1
    return res


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

a = sum(X)
b = a-1
c = a+1
if a == 1:
    A, C = [1], [1]  # 2冪をa,b,cで割った余り
    xa, xc = 0, 0  # Xをa,b,cで割った余り
    for i in range(N):
        if X[i] == 1:
            xa += A[-1]
            xc += C[-1]
            xa %= a
            xc %= c
        A.append((2 * A[-1]) % a)
        C.append((2 * C[-1]) % c)

    ANS = []
    for i in range(N):
        if X[i] == 1:
            ANS.append(0)
        else:
            ANS.append(1 + F[(xc + C[i]) % c])

    ANS.reverse()
    print(*ANS, sep='\n')
    exit()

A,B,C = [1],[1],[1]  # 2冪をa,b,cで割った余り
xa,xb,xc = 0,0,0  # Xをa,b,cで割った余り
for i in range(N):
    if X[i] == 1:
        xa += A[-1]
        xb += B[-1]
        xc += C[-1]
        xa %= a
        xb %= b
        xc %= c
    A.append((2*A[-1])%a)
    B.append((2*B[-1])%b)
    C.append((2*C[-1])%c)

ANS = []
for i in range(N):
    if X[i] == 1:
        ANS.append(1 + F[(xb-B[i]) % b])
    else:
        ANS.append(1 + F[(xc+C[i]) % c])

ANS.reverse()
print(*ANS,sep='\n')

Submission status: Wrong Answer

Solution code:


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def popcount(N):
    if N == 0:
        return 0
    one_count = 0
    temp = N
    while temp > 0:
        one_count += temp%2
        temp //= 2
    return 1+popcount(N%one_count)


def solve():
    N = read_int()
    X = input()
    one_count = X.count('1')
    if one_count == 0:
        for _ in range(N):
            print(0)
        return

    new_X = [0]*N
    steps = [0]*N

    base_up = 1
    up_under_modulo = 0

    for i in range(N-1, -1, -1):
        if X[i] == '1':
            up_under_modulo = (up_under_modulo+base_up)%(one_count+1)
        if X[i] == '0':
            new_X[i] += base_up
            steps[i] = 1
        base_up = (base_up*2)%(one_count+1)

    base_down = 1
    down_under_modulo = 0

    if one_count > 1:
        for i in range(N-1, -1, -1):
            if X[i] == '1':
                down_under_modulo = (down_under_modulo+base_down)%(one_count-1)
            if X[i] == '1':
                new_X[i] -= base_down
                steps[i] = 1
            base_down = (base_down*2)%(one_count-1)

    for i in range(N):
        if X[i] == '1':
            if one_count > 1:
                new_X[i] = (new_X[i]+down_under_modulo)%(one_count-1)
        else:
            new_X[i] = (new_X[i]+up_under_modulo)%(one_count+1)

    for i in range(N):
        print(steps[i]+popcount(new_X[i]))


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

def solve():
    N = INT()
    xbin = input()
    xdec = int(xbin, 2)
    m = xbin.count('1')

    a = xdec % (m+1)
    b = xdec % (m-1) if m > 1 else 0

    num = [0]*N
    for i in range(1, N):
        num[i] = num[i % bin(i).count('1')] + 1

    for i in range(N):
        if xbin[i] == '0':
            y = ( a + pow(2, N-i-1, m+1) ) % ( m+1 )
            print(num[y] + 1)
        elif m <= 1:
            print(0)
        else:
            y = ( b + pow(2, N-i-1, m-1) ) % ( m-1 )
            print(num[y] + 1)

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

def solve():
    N = INT()
    xbin = input()
    xdec = int(xbin, 2)
    m = xbin.count('1')

    num = [0]*N
    for i in range(1, N):
        num[i] = num[i % bin(i).count('1')] + 1

    pop = [m + 1, m - 1]
    x = [xdec % pop[0], xdec % pop[1] if pop[1]>0 else xdec]

    reg = [[0]*2 for i in range(N)]
    reg[N-1] = [1, 1]
    for i in range(N-2, -1, -1):
        reg[i][0] = reg[i+1][0]*2 % pop[0]
        reg[i][1] = reg[i+1][1]*2 % pop[1] if pop[1]>0 else reg[i+1][1]*2

    for i in range(N):
        if xbin[i] == '0':
            y = ( x[0] + reg[i][0] ) % pop[0]
        else:
            y = ( x[1] - reg[i][1] ) % pop[1] if pop[1]>0 else x[1] - reg[i][1]
        print(num[y] + 1)

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

def solve():
    N = INT()
    xbin = input()
    xdec = int(xbin, 2)
    m = xbin.count('1')

    num = [0]*N
    for i in range(1, N):
        num[i] = num[i % bin(i).count('1')] + 1

    pop = [m + 1, m - 1]
    x = [xdec % pop[0], xdec % pop[1] if pop[1]>0 else 0]

    reg = [[0]*2 for i in range(N)]
    reg[N-1] = [1, 1]
    for i in range(N-2, -1, -1):
        reg[i][0] = reg[i+1][0]*2 % pop[0]
        reg[i][1] = reg[i+1][1]*2 % pop[1] if pop[1]>0 else 0

    for i in range(N):
        if xbin[i] == '0':
            y = ( x[0] + reg[i][0] ) % pop[0]
        else:
            y = ( x[1] - reg[i][1] ) % pop[1] if pop[1]>0 else 0
        print(num[y] + 1)

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
N = int(input())
X = input()
ans = [1] * N
A = [0] * N

cnt = X.count("1")
M0 = 0
M1 = 0
temp0 = 1
temp1 = 1

for i in range(N):
    if(X[N - 1 - i] == '1'):
        if(cnt != 1):
            M0 = (M0 + temp0) % (cnt - 1)
        M1 = (M1 + temp1) % (cnt + 1)

    if(cnt != 1):
        temp0 = (temp0 * 2) % (cnt - 1)
    temp1 = (temp1 * 2) % (cnt + 1)

temp0 = 1
temp1 = 1

for i in range(N):

    if(X[N - 1 - i] == '0'):
        A[N - 1 - i] = (M1 + temp1) % (cnt + 1)

    else:
        if(cnt == 1):
            A[i] = 0
            ans[N - 1 - i] -= 1
        
        else:
            A[N - 1 - i] = abs(M0 - temp0) % (cnt - 1)

    if(cnt != 1):
        temp0 = (temp0 * 2) % (cnt - 1)
    temp1 = (temp1 * 2) % (cnt + 1)

for i in range(N):

    while(A[i]):

        pop_count = bin(A[i]).count("1")
        A[i] %= pop_count
        ans[i] += 1

for i in range(N):  print(ans[i]);

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
X = input()
X_10 = int(X, 2)
popcount_X = X.count("1")
popcount_X_plus = popcount_X + 1
popcount_X_minus = popcount_X - 1
f_plus = X_10 % popcount_X_plus
f_minus = X_10 % popcount_X_minus if popcount_X_minus != 0 else 0

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

def f(n):
  if n == 0:
    return 0
  return n % popcount(n)

for i in range(N):
  j = N - (i + 1)
  n = 0
  ans = 1
  
  if X[i] == '0':
#    n = (f_plus + (2**j % popcount_X_plus)) % popcount_X_plus
    n = (f_plus + pow(2, j, popcount_X_plus)) % popcount_X_plus
  else:
    if popcount_X_minus == 0:
      n = 0
    else:
#      n = (f_minus - (2**j % popcount_X_minus) + popcount_X_minus) % popcount_X_minus
      n = (f_minus - pow(2, j, popcount_X_minus) + popcount_X_minus) % popcount_X_minus
  
  while n > 0:
    n = f(n)
    ans += 1
  print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
X = input()
X_10 = int(X, 2)
popcount_X = X.count("1")
popcount_X_plus = popcount_X + 1
popcount_X_minus = popcount_X - 1
f_plus = X_10 % popcount_X_plus
f_minus = X_10 % popcount_X_minus if popcount_X_minus != 0 else 0

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

def f(n):
  if n == 0:
    return 0
  return n % popcount(n)

for i in range(N):
  j = N - (i + 1)
  n = 0
  ans = 1
  
  if X[i] == '0':
#    n = (f_plus + (2**j % popcount_X_plus)) % popcount_X_plus
    n = (f_plus + pow(2, j, popcount_X_plus)) % popcount_X_plus
  else:
    if popcount_X_minus == 0:
      n = 0
    else:
#      n = (f_minus - (2**j % popcount_X_minus) + popcount_X_minus) % popcount_X_minus
      n = (f_plus - pow(2, j, popcount_X_minus) + popcount_X_minus) % popcount_X_minus
  
  while n > 0:
    n = f(n)
    ans += 1
  print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
X = input()
X_10 = int(X, 2)
popcount_X = X.count("1")
popcount_X_plus = popcount_X + 1
popcount_X_minus = popcount_X - 1
f_plus = X_10 % popcount_X_plus
f_minus = X_10 % popcount_X_minus if popcount_X_minus != 0 else 0

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

def f(n):
  if n == 0:
    return 0
  return n % popcount(n)

for i in range(N):
  j = N - (i + 1)
  n = 0
  ans = 1
  
  if X[i] == '0':
#    n = (f_plus + (2**j % popcount_X_plus)) % popcount_X_plus
    n = (f_plus + pow(2, j, popcount_X_plus)) % popcount_X_plus
    print("i, f_plus, n", i, f_plus, n)
  else:
    if popcount_X_minus == 0:
      n = 0
    else:
#      n = (f_minus - (2**j % popcount_X_minus) + popcount_X_minus) % popcount_X_minus
      n = (f_plus - pow(2, j, popcount_X_minus) + popcount_X_minus) % popcount_X_minus
      print("i, f_minus, n", i, f_minus, n)
  
  while n > 0:
    n = f(n)
    ans += 1
  print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
X = input()
X_10 = int(X, 2)
popcount_X = X.count("1")
popcount_X_plus = popcount_X + 1
popcount_X_minus = popcount_X - 1
f_plus = X_10 % popcount_X_plus
f_minus = X_10 % popcount_X_minus if popcount_X_minus != 0 else 0

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

def f(n):
  if n == 0:
    return 0
  return n % popcount(n)

for i in range(N):
  j = N - (i + 1)
  n = 0
  ans = 1
  
  if X[i] == '0':
    n = (f_plus + (2**j % popcount_X_plus)) % popcount_X_plus
    print("i, f_plus, n", i, f_plus, n)
  else:
    if popcount_X_minus == 0:
      n = 0
    else:
      n = (f_minus - (2**j % popcount_X_minus) + popcount_X_minus) % popcount_X_minus
    print("i, f_minus, n", i, f_minus, n)
  
  while n > 0:
    n = f(n)
    ans += 1
  print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
X = input()
X_10 = int(X, 2)
popcount_X = X.count("1")
popcount_X_plus = popcount_X + 1
popcount_X_minus = popcount_X - 1
f_plus = X_10 % popcount_X_plus
f_minus = X_10 % popcount_X_minus if popcount_X_minus != 0 else 0

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

def f(n):
  if n == 0:
    return 0
  return n % popcount(n)

for i in range(N):
  j = N - (i + 1)
  x = 0
  ans = 1
  
  if X[i] == '0':
    x = (f_plus + (2**j % popcount_X_plus)) % popcount_X_plus
  else:
    if popcount_X_minus == 0:
      x = 0
    else:
      x = (f_minus - (2**j % popcount_X_minus) + popcount_X_minus) % popcount_X_minus
      
  
  while x > 0:
    x = f(x)
    ans += 1
  print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
X = input()
X_10 = int(X, 2)
popcount_X = X.count("1")
popcount_X_plus = popcount_X + 1
popcount_X_minus = popcount_X - 1
f_plus = X_10 % popcount_X_plus
f_minus = X_10 % popcount_X_minus if popcount_X_minus != 0 else 0

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

def f(n):
  if n == 0:
    return 0
  return n % popcount(n)

for i in range(N):
  j = N - (i + 1)
  
  Xi = 0
  x = 0
  ans = 1
  
  if X[i] == '0':
    Xi = X_10 + 2**j
    x = (f_plus + (2**j % popcount_X_plus)) % popcount_X_plus
  else:
    Xi = X_10 - 2**j
    if popcount_X_minus == 0:
      x = 0
    else:
      x = (f_minus -(2**j % popcount_X_minus)) % popcount_X_minus
      
  
  while x > 0:
    x = f(x)
    ans += 1
  print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
X = input()
X_10 = int(X, 2)
popcount_X = X.count("1")
popcount_X_plus = popcount_X + 1
popcount_X_minus = popcount_X - 1
fX_plus = X_10 % popcount_X_plus
fX_minus = X_10 % popcount_X_minus if popcount_X_minus != 0 else 0

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

def f(n):
  if n == 0:
    return 0
  return n % popcount(n)


for i in range(N):
  j = N - (i + 1)
  
  Xi = 0
  x = 0
  ans = 1
  
  if X[i] == '0':
    Xi = X_10 + 2**j
    x = (fX_plus + 2**j % popcount_X_plus) % popcount_X_plus
  else:
    Xi = X_10 - 2**j
    if popcount_X_minus == 0:
      x = 0
    else:
      x = (fX_minus - 2**j % popcount_X_minus) % popcount_X_minus
      
  
  while x > 0:
    x = f(x)
    ans += 1
  print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
X = input()
X_10 = 0
popcount_X = 0

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

def f_func(n):
  popcnt = popcount(n)
  if popcnt == 0:
    return 0
  return n % popcnt

for i in range(N):
  j = N - (i + 1)
  X_10 += int(X[i]) * 2 ** j
  if X[i] == '1':
    popcount_X += 1

popcount_X_plus = popcount_X + 1
popcount_X_minus = popcount_X - 1

if popcount_X_plus == 0:
  fX_plus = 0
else:
  fX_plus = X_10 % popcount_X_plus

if popcount_X_minus == 0:
  fX_minus = 0
else:
  fX_minus = X_10 % popcount_X_minus

for i in range(N):
  j = N - (i + 1)
  
  Xi = 0
  f = 0
  ans = 1
  
  if X[i] == '0':
    Xi = X_10 + 2**j
    if popcount_X_plus == 0:
      f = 0
    else:
      f = (fX_plus + 2**j % popcount_X_plus) % popcount_X_plus
    
  elif X[i] == '1':
    Xi = X_10 - 2**j
    if popcount_X_minus == 0:
      f = 0
    else:
      f = (fX_minus - 2**j % popcount_X_minus) % popcount_X_minus
      
  
  while f > 0:
    f = f_func(f)
    ans += 1
  print(ans)

Submission status: Wrong Answer

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


def power(a, n, mod):
    bi=str(format(n,"b")) #2進数
    res=1
    for i in range(len(bi)):
        res=(res*res) %mod
        if bi[i]=="1":
            res=(res*a) %mod
    return res

p = x.count('1')

if p == 0:
    ans = [1]*n
    for i in range(n):
        print(ans[i])
    exit()

if p == 1:
    if x[-1] != '1':
        ans = [1]*n
        for i in range(n):
            if x[i] == '1':
                ans[i] = 0
    else:
        ans = [2]*n
        ans[-1] = 0
    for i in range(n):
        print(ans[i])
    exit()

x = list(x)
x.reverse()
temp1 = 0
for i in range(len(x)):
    temp1 += int(x[i])*power(2, i, p+1)
temp1 %= (p+1)

temp2 = 0
for i in range(len(x)):
    temp2 += int(x[i])*power(2, i, p-1)
temp2 %= (p-1)

ans = [0]*n

for i in range(n):
    if x[n-1-i] == '1':
        temp = temp2-power(2, n-1-i, p-1)
        c = p-1
    else:
        temp = temp1+power(2, n-1-i, p+1)
        c = p+1
    temp %= c
    #print(i, temp, c)
    cnt = 1
    while temp != 0:
        x_ = format(temp, 'b')
        c = x_.count('1')
        x_ = list(x_)
        x_.reverse()
        temp = 0
        for j in range(len(x_)):
            temp += int(x_[j])*power(2, j, c)
        temp %= c
        cnt += 1
    #print(i, cnt)
    ans[i] = cnt

for i in range(n):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
## coding: UTF-8
N = 23
S = '00110111001011011001110'
#N = 3
#S = '011'

#N = int(input())
#S = input()
P = int(S, 2)
#print(P)

def popcount(x):

    # 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 count(N):
    warareru = N
    waru = popcount(N)
    counter = 0
    while warareru > 0:
        warareru = warareru % waru
        waru = popcount(warareru)
        counter += 1
    return counter


#前処理
first_popcount = popcount(P)
if(first_popcount == N):
    first_use_pop = [N-1, N-1]
elif(first_popcount == 0):
    first_use_pop = [1, 1]
else:
    first_use_pop = [first_popcount+1, first_popcount-1]

tmp_0 = 1
tmp_1 = 1
kakunou_0 = []
kakunou_1 = []
tmp_0 %= first_use_pop[0]
tmp_1 %= first_use_pop[1]
kakunou_0.append(tmp_0)
kakunou_1.append(tmp_1)
for i in range(0, 2*10**5+10):
    tmp_0 *= 2
    tmp_1 *= 2
    tmp_0 %= first_use_pop[0]
    tmp_1 %= first_use_pop[1]
    kakunou_0.append(tmp_0)
    kakunou_1.append(tmp_1)
#print(first_popcount, first_use_pop, kakunou_0[:50], kakunou_1[:50])


#与えられた数字の初手処理をしておく
syote_0 = 0
syote_1 = 0
#print(S)
for i in range(N-1, -1, -1):
    #print(i, N-1-i, S[i])
    if(S[i] == '1'):
        syote_0 += kakunou_0[N-1-i]
        syote_0 %= first_use_pop[0]
        syote_1 += kakunou_1[N-1-i]
        syote_1 %= first_use_pop[1]
#print(syote_0, syote_1)
#確認OK
#print(P%first_use_pop[0], P%first_use_pop[1])


ans = []
for i in range(N):
    if(S[i] == '0'):
        now = syote_0 + kakunou_0[N-1-i]
        now %= first_use_pop[0]
        if(now == 0):
            ans.append(1)
        else:
            ans.append(1+count(now))
    else:
        now = syote_1 - kakunou_1[N-1-i]
        now %= first_use_pop[1]
        if(now == 0):
            ans.append(1)
        else:
            ans.append(1+count(now))

for i in range(N):
    print(ans[i])



'''
ans = [0]
for i in range(1, 2*10**5+10):
    ans.append(count(i))
#print(ans[:100])
#print(ans)

for i in range(100):
    max = 2 ** (2*10**5 - 1) - 1 - i
    #print(count(max))


C = popcount(P)
ret = []
for i in range(N):
    new = []
    for j in range(N):
        if(j != i):
            new.append(S[j])
        else:
            if(S[j] == '0'):
                new.append('1')
                count = C + 1
            else:
                new.append('0')
                count = C - 1
    ten = int(''.join(new), 2)
    res = ans[ten%count] + 1
    ret.append(res)


for i in range(N):
    print(ret[i])
'''

Submission status: Wrong Answer

Solution code:
#エイシング　D
n = int(input())
x = input()

def popcount(i):
    return bin(i)[2:].count("1")

poplist = [0]*(n+1)
for i in range(1,n+1):
    k = i%popcount(i)
    poplist[i] = poplist[k]+1

import sys
if n ==1:
    if x=="0":
        print(0)
    else:
        print(1)
    sys.exit()

p = x.count("1")
nbit = int(x,2)
if p!=1:
    namari1 = nbit%(p-1)
namari2 = nbit%(p+1)

for i in range(n):
    a = str(x[:i]) + str(int(not int(x[i]))) + str(x[i+1:])
    a = int(a,2)
    P = n-1-i
    if int(x[i]) == 1:
        if p == 1:
            print(0)
            continue
        else:
            #p>=2
            c = (namari1 - pow(2,P,p-1))%(p-1)
    else:
        #int(x[i])==0
        c = (namari2 + pow(2,P,p+1))%(p+1)
    print(poplist[c]+1)

Submission status: Wrong Answer

Solution code:
#エイシング　D
n = int(input())
x = input()

def popcount(i):
    return bin(i)[2:].count("1")

poplist = [0]*(n+1)
for i in range(1,n+1):
    k = i%popcount(i)
    poplist[i] = poplist[k]+1

import sys
if n ==1:
    if x=="0":
        print(0)
    else:
        print(1)
    sys.exit()

p = x.count("1")
for i in range(n):
    a = str(x[:i]) + str(int(not int(x[i]))) + str(x[i+1:])
    a = int(a,2)
    if int(x[i]) == 1:
        if p == 1:
            print(1)
            continue
        else:
            #p>=2
            c = a%(p-1)
    else:
        #int(x[i])==0
        c = a%(p+1)    
    print(poplist[c]+1)

Submission status: Wrong Answer

Solution code:

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

mod0 = X.count("1") + 1
mod1 = X.count("1") - 1

full0 = 0
full1 = 0
for i in range(N):
    if X[i] == "1":
        full0 = (full0 + pow(2, N - i - 1, mod0)) % mod0
        if mod1 > 0:
            full1 = (full1 + pow(2, N - i - 1, mod1)) % mod1

ans = [0] * N
for i in range(N):
    if X[i] == "0":
        cur = (full0 + pow(2, N - i - 1, mod0)) % mod0
    else:
        if mod1 > 0:
            cur = (full1 - pow(2, N - i - 1, mod1)) % mod1
        else:
            cur = 0

    res = 1
    while cur > 0:
        cur %= bin(cur).count("1")
        res += 1
    ans[i] = res

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