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()
X10=int(X,2)
one=X.count('1')
def popcount(n):
  c=format(n,'b').count('1')
  if c!=0:
    return n%c
  else:
    return 0
def f(n):
  count=0
  while n>0:
    n=popcount(n)
    count+=1
  return count
if one==1:
  for i in range(N):
    if X[i]=='0':
      Y=X10+pow(2,N-i-1)
      print(f(Y))
     
    elif X[i]=='1':
      print(0)

if one>1:
  a=X10%(one-1)
  b=X10%(one+1)
  c=one-1
  d=one+1
  for i in range(N):
    if X[i]=='1':
      Y=(a-pow(2,N-i-1,c))%c
      print(f(Y)+1)
    if X[i]=='0':
      Y=(b+pow(2,N-i-1,d))%d
      print(f(Y)+1)

Submission status: Wrong Answer

Solution code:

n = int(input())
s=input()
p=0
c=0
for i in range(n):
    if s[i]=='1':
        p+=2**(n-i-1)
        c+=1
for i in range(n):
    k=p
    z=c
    if s[i]=='0':
        k+=2**(n-i-1)
        z+=1
    else:
        k-=2**(n-i-1)
        z-=1
    if z==0:
        print(0)
    elif z==1:
        print(1)
    elif (k&1)==(z&1):
        if k%z==0:
            print(1)
        else:
            print(2)
    else:
        print(3)

Submission status: Wrong Answer

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

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

for i in range(1,N+1):
    nex = popcount[i]
    if nex != 0:
        co[i] = nex + 1
    else:
        co[i] = 1
    
for i in range(N):
    x = X
    if x[i] == '0':
        x = x[:i] + '1' + x[i+1:]
    else:
        x = x[:i] + '0' + x[i+1:]
    num = x.count('1')
    if num == 0:
        print(0)
        break
    pop = int(x,2) % num
    ans = co[pop] + 1
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys

def input():
    return sys.stdin.readline()[:-1]

def ppp(x):
    s = format(x, 'b')
    return s.count('1')
   

n = int(input())
x = input()
f_li = [0]
for i in range(1, x.count('1')+1):
    for j in range(i+10):
        if i < len(f_li):
            f_li.append(f_li[i]+j)
            break
        else:
            i = i % ppp(i)
print(f_li)

for i in range(n):
    tmp = list(x)
    tmp[i] = str((int(x[i])+1)%2)
    xi = int(''.join(tmp) , 2)
    f_li.append(xi)
    if xi==0:
        print(0)
    else:
        xi = xi%ppp(xi)
        if xi==0:
            print(1)
        else:
            print(f_li[xi]+1)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

t = [0]

pl = np.array([1])
tmp = [np.array([1])]
for i in range(18):
    ne = np.concatenate([tmp[-1], tmp[-1]+1])
    tmp.append(ne)
pl = np.concatenate(tmp)

for n in range(1, N+1):
    c = pl[n-1]
    t.append(1 + t[n%c])

def count_ones_by_shift(num):
    num = (num & 0x55555555) + ((num & 0xAAAAAAAA) >> 1) 
    num = (num & 0x33333333) + ((num & 0xCCCCCCCC) >> 2)
    num = (num & 0x0F0F0F0F) + ((num & 0xF0F0F0F0) >> 4)
    num = (num & 0x00FF00FF) + ((num & 0xFF00FF00) >> 8)
    num = (num & 0x0000FFFF) + ((num & 0xFFFF0000) >> 16)
    return num

basex = int(X, 2)
base = count_ones_by_shift(basex)

for n in range(N):
    if X[n] == "0":
        c = base + 1
        x = basex + 2**(N-n-1)
    else:
        c = base - 1
        x = basex - 2**(N-n-1)
    
    if c == 0:
        print(0)
    else:
        print(1 + t[x%c])

Submission status: Wrong Answer

Solution code:

n = int(input())
s=input()
p=0
c=0
for i in range(n):
    if s[i]=='1':
        p+=2**(n-i-1)
        c+=1
for i in range(n):
    k=p
    z=c
    if s[i]=='0':
        k+=2**(n-i-1)
        z+=1
    else:
        k-=2**(n-i-1)
        z-=1
    if z==0:
        print(1)
    elif z==1:
        print(1)
    elif (k&1)==(z&1):
        if k%z==0:
            print(1)
        else:
            print(2)
    else:
        print(3)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    *X, = map(int, input())

    memo = [-1] * 21

    def f(x):
        ret = 0
        while x > 0:
            x = x % bin(x)[2:].count('1')
            ret += 1
        return ret

    for x in range(21):
        memo[x] = f(x)

    cnt = X.count(1)

    pow2_0_1 = [1]
    pow2_1_0 = [1]

    t_0_1 = 1
    t_1_0 = 1
    for i in range(N):
        t_0_1 = t_0_1 * 2 % (cnt + 1)
        pow2_0_1.append(t_0_1)

        if cnt == 1:
            pass
        else:
            t_1_0 = t_1_0 * 2 % (cnt - 1)
            pow2_1_0.append(t_1_0)

    chg_0_1 = 0
    chg_1_0 = 0
    i = 0
    for d in reversed(X):
        if d:
            chg_0_1 = (chg_0_1 + pow2_0_1[i]) % (cnt + 1)
            if cnt == 1:
                pass
            else:
                chg_1_0 = (chg_1_0 + pow2_1_0[i]) % (cnt - 1)
        i += 1

    ans = []
    i = 0
    for d in reversed(X):
        if d:
            if cnt == 1:
                t = 0
            else:
                t = (chg_1_0 - pow2_1_0[i]) % (cnt - 1)
        else:
            t = (chg_0_1 + pow2_0_1[i]) % (cnt + 1)
        i += 1

        add_v = 1
        while t > 20 or memo[t] == -1:
            t = t % bin(t)[2:].count('1')
            add_v += 1
        ans.append(memo[t] + add_v)

    ans.reverse()

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


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
#
# sys.setrecursionlimit(10 ** 7)
#
# (int(x)-1 for x in input().split())
# rstrip()
#
# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok

Submission status: Wrong Answer

Solution code:
def popcount(x):
	count=0
	for digit in str(bin(x))[2:]:
		if digit=='1':
			count+=1
	return count

f_memo={}
def f(x):
	if x in f_memo:
		return f_memo[x]
	else:
		count=0
		while x!=0:
			x= x%popcount(x)
			count+=1
	f_memo[x]= count
	return count

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

value_x= int(x, 2)
#print('!!', value_x)
for i in range(n):
	test= value_x^(2**(n-i-1))
	print(f(test))





#print(f(n))

Submission status: Wrong Answer

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

memo = [0]*n
memo2 = [-1]*(2*10**5+10)
ans = [-1]*n
popcnt = 0

for i in range(n):
    if x[i] == "1":
        popcnt += 1

amariStaticA = 0
amariStaticB = 0
for i in range(n):
    if x[i] == "1":
        amariStaticA += pow(2, n-i-1, max(1, popcnt-1))
        amariStaticB += pow(2, n-i-1, popcnt+1)
amariStaticA %= max(1, popcnt-1)
amariStaticB %= popcnt+1

for i in range(n):
    amari = 0
    if x[i] == "0":
        amari = amariStaticB + pow(2, n-i-1, popcnt+1)
        amari %= popcnt+1
    else:
        amari = amariStaticA - pow(2, n-i-1, max(1, popcnt-1))
        amari %= max(1, popcnt-1)
    if amari == 0:
        ans[i] = 1
    else:
        memo[i] = amari

for i in range(len(memo)):
    cnt = 1
    firstMemo = copy.deepcopy(memo[i])
    while memo[i] != 0:
        if memo2[memo[i]] != -1:
            cnt = memo2[memo[i]]
            memo[i] = 0
        else:
            popcnt = bin(memo[i]).count("1")
            memo[i] %= max(1, popcnt)
            cnt += 1
        if memo[i] == 0:
            ans[i] = cnt
            memo2[firstMemo] = cnt
            break


for anss in ans:
    print(anss)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 6)

mod = 1000000007
inf = int(1e18)

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def inverse(a):
    return pow(a, mod - 2, mod)


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft


memo = {}

def countbit(x):
    i = 0
    cnt = 0
    while x >= 1<<i:
        if x & (1<<i):
            cnt += 1
        i += 1
    return cnt


def count(x):
    # if c == 0:
    #     return 0
    # s = 1
    # x = x % c
    s = 0
    while x != 0:
        s += 1
        x = x % countbit(x)
    return s

def main():
    n = int(input())
    xs = list(input())
    c = len([i for i in xs if i == '1'])
    dp = {}
    dps = {}
    for i in range(-1, 2):
        cc = c + i
        if cc == 0:
            continue
        dp[cc] = [-1] * n
        base = 1 % cc
        dpstmp = 0
        for i in range(n):
            dp[cc][i] = base
            if xs[i] == '1':
                dpstmp += base
            base = base * 2 % cc
        dps[cc] = dpstmp % cc

    for i in range(n):
        cc = c
        if xs[i] == '1':
            cc -= 1
        else:
            cc += 1
        if cc == 0:
            print(0)
            continue
        res = dps[cc]
        if xs[i] == '1':
            res = (res - dp[cc][i]) % cc
        else:
            res = (res + dp[cc][i]) % cc
        s = count(res) + 1
        print(s)


main()

Submission status: Wrong Answer

Solution code:
def popcount(u):
    t = bin(u)
    h = t.count("1")
    return u % h 
    
pri = [-1 for i in range(2*(10**5) + 1)]
pri[0] = 0
for i in range(1,2*(10**5)+1):
    if pri[i] == -1:
        now =  popcount(i)
        pri[i] = pri[now] + 1
    
n = int(input())
x = list(input())
c = x.count("1") + 1
d = c - 2

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

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env pypy3

def ans(X):
    if X == 0: return 0
    X = X % (bin(X).count('1'))
    return 1+ans(X)

# test case injection
if False:
    import random
    X = ''.join(random.choice("1") for _ in range(2*10**5))
    N = len(X)
    # print(N, X)
    # exit(0)
else:
    N = int(input())
    X = input()

N = N-1

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

import array

two_pow_mod_pc_plus = array.array('i', [0]*(N+1))
two_pow_mod_pc_minus = array.array('i', [0]*(N+1))

two_pow_mod_pc_plus[0] = 1 % (popcount+1)
if popcount <= 1:
    two_pow_mod_pc_minus[0] = 0
else:
    two_pow_mod_pc_minus[0] = 1 % (popcount-1)

for i in range(1, len(two_pow_mod_pc_plus)):
    two_pow_mod_pc_plus[i] = (2*two_pow_mod_pc_plus[i-1]) % (popcount+1)

for i in range(1, len(two_pow_mod_pc_minus)):
    if popcount <= 1:
        two_pow_mod_pc_minus[i] == 1
    else:
        two_pow_mod_pc_minus[i] = (2*two_pow_mod_pc_minus[i-1]) % (popcount-1)

X_mod_pc_plus = X_int % (popcount+1)
if popcount <= 1:
    X_mod_pc_minus = 0
else:
    X_mod_pc_minus = X_int % (popcount-1)

for i, x in enumerate(X):
    # if i % 1000 == 0: print(i)
    if x == '0':
        if popcount == 0:
            print(0)
            continue
        else:
            r = 1 + ans((X_mod_pc_plus + two_pow_mod_pc_plus[N-i]) % (popcount+1))
    else:
        if popcount == 1:
            print(0)
            continue
        else:
            r = 1 + ans((X_mod_pc_minus - two_pow_mod_pc_minus[N-i]) % (popcount-1))
    print(r)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = input()
XX = list(i for i in X)
c = dict()
for i in range(N):
    xxx = XX[:]
    xxx[i] = '0' if xxx[i] == '1' else '1'
    j = int(''.join(xxx), 2)
    if j in c:
        continue
    jj = j
    cnt = 0
    while jj > 0:
        cnt += 1
        jj = jj % bin(jj).count('1')
        if jj in c:
            cnt = c[jj]
            break
    print(cnt)
    c[j] = cnt

Submission status: Wrong Answer

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

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

n = int(input())
x = list(input())
xc = x.count("1")
xu = []
xd = []
if xc == 0:
    for i in range(n):
        print(0)
        exit()
t = 1
for i in range(n):
    mod = xc+1
    xu.append(t%mod)
    t *= 2
t = 1
for i in range(n):
    mod = xc-1
    if mod == 0:
        xd.append(0)
    else:
        xd.append(t%mod)
        t *= 2
xu.reverse()
xd.reverse()
s_xu = 0
s_xd = 0
for i in range(n):
    if x[i] == "1":
        s_xu += xu[i]
        s_xd += xd[i]

# print(xu)
# print(xd)

for i in range(n):
    cnt = 1
    if x[i] == "0":
        tar = (s_xu+xu[i])%(xc+1)
        #print(tar)
        while tar != 0:
            b_tar = list(bin(tar)[2:])
            tar %= b_tar.count("1")
            cnt += 1
        print(cnt)
    else:
        if s_xd-xd[i] == 0:
            print(0)
        else:
            tar = (s_xd-xd[i])%(xc-1)
            #print(tar)
            while tar != 0:
                b_tar = list(bin(tar)[2:])
                tar %= b_tar.count("1")
                cnt += 1
            print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
x = input()
pc = 0
for i in range(len(x)):
    if x[i]=='1':
        pc += 1
def popcount(s):
    c = 0
    for i in range(len(s)):
        if s[i]=='1':
            c += 1
    return c
d = dict()
for i in range(len(x)):
    X = x[0:i] + ('0' if x[i]=='1' else '1') + x[i+1:len(x)]
    if x[i]=='1':
        pop = pc-1
    else:
        pop = pc+1
    v = int('0b'+X, 0)
    if pop==0:
        print('0')
        continue
    new = v % pop
    if new == 0:
        print('1')
        continue
    counter = 1
    while True:
        counter += 1
        oldnew = new
        new = new % popcount(str(bin(new)))
        if new in d:
            d[oldnew] = d[new] + 1
            print(counter + d[new])
            break
        if new == 0:
            d[oldnew] = 0
            print(counter)
            break

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n = int(readline())
lst1 = list(readline().rstrip().decode('utf-8'))


res = lst1.copy()
res = "".join(res)
ct = res.count("1")
res = int(res,2)
if ct == 0:
    for i in range(n):
        print(0)
    exit()
if ct == 1:
    amari_of_m = -1
else:
    amari_of_m = res%(ct-1)
amari_of_p = res%(ct+1)

def pow(n,p,mod): #繰り返し二乗法(nのp乗)
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod

def func(res):
    ans = 1
    while True:
        ct = 0
        for i in range(len(bin(res))):
            if res>>i&1:
                ct += 1
        if res%ct == 0:
            print(ans+1)
            return
        else:
            res %= ct
            ans += 1

for i in range(n):
    if lst1[i] == "1" and amari_of_m == -1:
        print(1)
        continue
    resres = pow(2,n-i-1,ct-1) if lst1[i] == "1" else pow(2,n-i-1,ct+1)
    if lst1[i] == "1":
        resres -= amari_of_m
        resres %= ct-1
    else:
        resres += amari_of_p
        resres %= ct+1
    if not resres:
        print(1)
    else:
        func(resres)

Submission status: Wrong Answer

Solution code:
# 
import sys

from sys import stdin
input = lambda: stdin.readline().rstrip()

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

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

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

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

fo = '0' + str(N) + 'b'
for i in reversed(range(N)):
    x = toggle_nth_bit(X,i)
    #print("----")
    #print(format(X, fo))
    #print(format(x, fo))

    print(f(x))

Submission status: Wrong Answer

Solution code:

import copy
n = int(input())
X = list(input())
ans = [0] * n

def calc(x, cnt):
    if cnt == 0:
        return 0
    return 1 + calc(x % cnt, popcount(x % cnt))



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

for i in range(n):
    bit = copy.copy(X)
    if bit[i] == "0":
        bit[i] = "1"
    else:
        bit[i] = "0"
    
    x = int("".join(bit), 2)
    cnt = popcount(x)
    ans[i] = calc(x, cnt)
    

for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
n = int(input())
x = list(input())
cnt = x.count("1")

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

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

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

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


for i in range(n):
    y = x[:]
    if x[i] == "1":
        y[i] = "0"
        z = "".join(y)
        z = int(z, 2)
        if z == 0:
            print(0)
        else:
            z %= (cnt - 1)
            if z == 0:
                print(1)
            else:
                ans = 1
                while z > 0:
                    z %= popcount(z)
                    ans += 1
                print(ans)
    else:
        y[i] = "1"
        z = "".join(y)
        z = int(z, 2)
        z %= (cnt + 1)
        if z == 0:
            print(0)
        else:
            if z == 0:
                print(1)
            else:
                ans = 1
                while z > 0:
                    z %= popcount(z)
                    ans += 1
                print(ans)

Submission status: Wrong Answer

Solution code:
def popcount(u):
    t = bin(u)
    h = t.count("1")
    return u % h 
    
pri = [-1 for i in range(2*(10**5) + 1)]
pri[0] = 0
for i in range(1,2*(10**5)+1):
    if pri[i] == -1:
        now =  popcount(i)
        pri[i] = pri[now] + 1
    
n = int(input())
x = list(input())
c = x.count("1") + 1
d = c - 2

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

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

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

Submission status: Wrong Answer

Solution code:
n = int(input())
x = str(input())
kosu1 = 0
kazu = 0
for i in range(n):
    kazu += 2 ** (n - i - 1) * int(x[i])
    if x[i] == '1':
        kosu1 += 1
if kosu1 ==1:
    kazup = kazu % (kosu1 + 1)
    magic17 = [0, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 2, 3, 1, 2]
    box = [0] * (kosu1 + 1)

    amarip = [1] * n
    amarim = [1] * n
    for i in range(1, n):
        amarip[i] = (amarip[i - 1] * 2) % (kosu1 + 1)
    for i in range(n):
        if x[i] == '1':
            print(0)
        else:
            a = (kazup + amarip[n - 1 - i]) % (kosu1 + 1)

            if a <= 18:
                print(magic17[a] + 1)
            else:
                num = 0
                for i in range(len(str(bin(a)))-2):
                    if str(bin(a))[-1 - i] == '1':

                        num += 1
                print(magic17[a % num] + 1)
else:
    kazup = kazu % (kosu1 + 1)
    kazum = kazu % (kosu1 - 1)
    magic17 = [0,1,1,2,1,2,1,2,1,2,1,2,1,2,2,3,1,2,1]
    box = [0] * (kosu1 +1)

    amarip = [1] * n
    amarim = [1] * n
    for i in range(1,n):
        amarip[i] = (amarip[i - 1]*2) % (kosu1 + 1)
        amarim[i] = (amarim[i - 1]*2) % (kosu1 - 1)
    for i in range(n):
        if x[i] == '1':
            a = (kazum - amarim[n-1-i]) % (kosu1 - 1)

            if a <= 18:
                print(magic17[a]+1)
            else:
                num = 0

                for i in range(len(str(bin(a)))-2):
                    if str(bin(a))[-1-i] == '1':

                        num += 1
                print(magic17[a % num] + 1)
        else:
            a = (kazup + amarip[n - 1 - i]) % (kosu1 + 1)
            if a <= 18:
                print(magic17[a] + 1)
            else:
                num = 0
                for i in range(len(str(bin(a)))-2):
                    if str(bin(a))[-1 - i] == '1':

                        num += 1
                print(magic17[a % num] + 1)

Submission status: Wrong Answer

Solution code:
n = int(input())
x = input()
xx = int(x, 2)
value = [0, 1]
count_1 = x.count('1')
for i in range(2, 2 * (10 ** 5) + 1):
    ans = 1
    i = i % bin(i).count('1')
    value.append(ans + value[i])

for i in range(n):
    ttt = xx & pow(2, n - i - 1)
    if ttt > 0:
        t = xx - pow(2, n - i - 1)
        point = count_1 - 1
    else:
        t = xx + pow(2, n - i - 1)
        point = count_1 + 1
    print(t)

Submission status: Wrong Answer

Solution code:
import sys
import time
import math
def inpl():
    return list(map(int, input().split()))
st = time.perf_counter()
# ------------------------------

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

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

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

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

N = int(input())
X = int(input(), 2)
a = popcount(X)
print(bin(X))
for i in range(N-1, -1, -1):
	if X & 1<<(i) != 0:
		aa = a-1
	else:
		aa = a+1
	x = X ^ 1<<(i)
	if x==0:
		print(0)
		continue
	x = x % aa
	cnt = 1
	while x != 0:
		cnt += 1
		x = x % popcount(x)
	print(cnt)

# ------------------------------
ed = time.perf_counter()
print('time:', ed-st, file=sys.stderr)

Submission status: Wrong Answer

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

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

memo = {
        0: 0,
        # 1: 1,
        # 2: 1,
        # 3: 2
        }
def f(n, cnt=0):
    # print(n,cnt)
    if n in memo:
        # print("memo,", memo[n])
        return cnt + memo[n]
    cnt += 1
    nxt = n % popcnt(n)
    # print(n,cnt,nxt)
    if nxt == 0:
        return cnt
    ret = f(nxt, cnt)
    memo[n] = ret
    return ret

n = int(input())
x = int(input(), 2)
ans = [0] * n


for i in range(n):
    tmp = x
    if (tmp >> (n-i-1)) & 1:
        tmp &= ~(1 << (n-i-1))
    else:
        tmp |= (1 << (n-i-1))
    # print("print(f({}))".format(tmp))
    ans[i] = f(tmp)

for v in ans:
    print(v)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from functools import lru_cache

import sys
sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


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


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


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


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, X):
    @lru_cache(maxsize=None)
    def f(y):
        c = bin(y).count('1')
        if c == 0:
            return 0
        r = y % c

        return 1 + f(r)

    C = X.count('1')
    cmr = 0
    cpr = 0
    for b in X:
        cmr *= 2
        cmr += int(b)
        if C-1 == 0:
            cmr = 0
        else:
            cmr %= C - 1
        cpr *= 2
        cpr += int(b)
        cpr %= C + 1

    for i in range(N):
        t = 1
        b = 2 ** (N-i-1)
        if X[i] == '0':
            x = (cpr + b) % (C+1)
        else:
            if C-1 == 0:
                x = 0
            else:
                x = (cmr - b) % (C-1)
        while True:
            c = bin(x).count('1')
            # print(x, c)
            if c == 0:
                break
            x = x % c
            t += 1
        print(t)


def main():
    N = read_int()
    X = read_str()
    slv(N, X)

    # import random
    # N = 10**5
    # N *= 2
    # X = ''.join(random.choices('01', k=N))
    # print(slv(N, X))




if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,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 copy import deepcopy
from time import time
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 LIST()  : return list(MAP())

n = INT()
x = input()
c = x.count('1')
a = [0]*(n+1)

y = 0
for i in range(n):
    y += int(x[i])*2**(n-1-i)

for i in range(n):
    ans = 0
    if x[i] == '0':
        c_tmp = c + 1
        y_tmp = y + 2**(n-1-i)
    else:
        c_tmp = c - 1
        y_tmp = y - 2**(n-1-i)
    while y_tmp != 0:
        ans += 1
        y_tmp = y_tmp % c_tmp
        c_tmp = format(y_tmp,'b').count('1')
        if y_tmp != 0 and a[y_tmp] != 0:
            ans += a[y_tmp] - 1
            break
    a[i] = ans
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def main():
    n = int(input())
    s = int(input(), 2)
    pc0 = bin(s).count("1")
    ans = []
    for i in range(n):
        k = 1 << (n - 1 - i)
        x = k ^ s
        if x >= s:
            pc1 = pc0 + 1
        else:
            pc1 = max(1, pc0 - 1)
        x %= pc1
        cnt = 1
        while x > 0:
            pc = bin(x).count("1")
            x %= pc
            cnt += 1
        ans.append(cnt)
    print("\n".join(str(y) for y in ans))
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())
X = list(input())
d = defaultdict(int)

for i in range(1, N):
    c = 0
    t = 0
    k = format(i, "b")
    for j in k:
        if j == "1":
            c += 1
    d[i] = d[i%c] + 1


n = 0
for i in X:
    if i == "1":
        n += 1

p = 1
total1 = 0
total2 = 0
for i in X[::-1]:
    if i == "1":
        total1 += p % (n+1)
        if n-1 > 0:
            total2 += p % (n-1)
    p *= 2

total1 %= (n+1)
if n-1 > 0:
    total2 %= (n-1)
Ans = []
p = 1
for i in X[::-1]:
    c = 1
    if n - 1 <= 0 and i == "1":
        Ans.append(c)
    else:
        if i == "0":
            start = total1
            start += p % (n+1)
            start %= (n+1)
        else:
            start = total2
            start -= p % (n-1)
            start += n - 1
            start %= (n-1)
        Ans.append(c+d[start])
    p *= 2

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

Submission status: Wrong Answer

Solution code:
import collections
memo = collections.defaultdict(int)
memo[0] = 0
memo[1] = 1


def f(x):
    if x in memo:
        return memo[x]
    else:
        y = x % bin(x).count('1')
        ret = 1 + f(y)
        memo[x] = ret
        return ret


N = int(input())
sX = input()
modX = sX.count('1')
if modX == 0:
    for _ in range(N):
        print(1)
elif modX == 1:
    sX = sX[::-1]
    for i, b in enumerate(sX):
        if b == '1':
            break
    #print(i)
    if i == 0:
        ans = [0] + [2] * (N - 1)
        ans = ans[::-1]
    else:
        ans = [1] * N
        ans[-1] = 2
        ans[-i] = 0
    print('\n'.join(map(str, ans)))
else:
    modp = modX + 1
    modm = modX - 1
    sX = sX[::-1]
    Xmodp = 0
    Xmodm = 0
    for i, b in enumerate(sX):
        if b == '1':
            Xmodp += pow(2, i, modp)
            Xmodp %= modp
            Xmodm += pow(2, i, modm)
            Xmodm %= modm
    s = []
    for i, b in enumerate(sX):
        if b == '1':
            s += [(Xmodm - pow(2, i, modm)) % modm]
        else:
            s += [(Xmodp + pow(2, i, modp)) % modp]
    ans = []
    for k in s[::-1]:
        ans += [1 + f(k)]
    print('\n'.join(map(str, ans)))