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 = 2*10**5
# X = "10"*10**5
n = int(input())
X = input()
c = 0
cnt = 0
for i,x in enumerate(X):
    c += (1<<(n-i-1))*int(x)
    cnt += int(x)

amari_cnt_p = c % (cnt+1)
if cnt != 1:
    amari_cnt_m = c % (cnt-1)

dp = []
for d in range(n):
    if X[d] == "0":
        amari = (amari_cnt_p + pow(2,n-d-1,cnt+1))%(cnt+1)
    else:
        if cnt != 1:
            amari = (amari_cnt_m - pow(2,n-d-1,cnt-1))%(cnt-1)
        else:
            amari = 0
    dp.append(amari)

memo = [-1]*(2*10**5+10)
memo[0] = 1
def calc(n):
    if n == 0:
        return 1
    if memo[n] != -1:
        return memo[n]
    cnt = 2
    while True:
        c = bin(n).count("1")
        if n%c == 0:
            break
        n %= c
        cnt += 1
    memo[n] = cnt
    return cnt

for d in dp:
    ans = calc(d)
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
X = input()

def popcount(n):
	if n == 0:
		return 0
	else:
		cnt = 0
		while 0 < n:
			cnt += 1
			p = "{:b}".format(n).count("1")
			n %= p
		return cnt

n = X.count("1")

n1 = n-1
n2 = n+1

q_1 = [0]*N
q_2 = [0]*N
for i in range(N):
	if n1 != 0:
		q_1[i] = pow(2, i, n1)
	if n2 != 0:
		q_2[i] = pow(2, i, n2)

mod_sum_1 = 0
mod_sum_2 = 0

for i in range(N):
	if X[-i-1] == "1":
		mod_sum_1 += q_1[i]
		mod_sum_2 += q_2[i]

q_1 = q_1[::-1]
q_2 = q_2[::-1]

for i in range(N):
	if X[i] == "1":
		m = n1
		mod_sum = mod_sum_1 - q_1[i]
	else:
		m = n2
		mod_sum = mod_sum_2 + q_2[i]
	if mod_sum == 0:
		print(1)
	else:
		print(popcount(mod_sum%m)+1)

Submission status: Wrong Answer

Solution code:
import math
N = int(input()) + 1
#Nroot = int(math.sqrt(N/3))+1
for n in range(1,N):
    count = 0
    if n >= 6:
#        print(Nroot, int(math.pow(n,1/3))-1)
        for x in range(int(math.sqrt(n/3))+1, int(math.sqrt(n/3))-1 , -1):
            for y in range(x,0,-1):
                if (x+2*y)**2 > n:
                    for z in range(1,y+1):
    #                    print((x + y + z)**2 - (x*y + y*z + z*x), n,x,y,z)
    #                    print(x,y,z)
                        formula = (x + y + z)**2 - (x*y + y*z + z*x)
                        if formula == n:
                            if x == y and y == z:
                                count += 1
                            else:
                                count += 3
                            break

        print(count)
    else:
        print("0")

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    x = input()
    x = '0b'+x

    x = int(x,0)
    m = bin(x).count('1')
    # print(x)

    a = x%(m-1)
    b = x%(m+1)
    # exit()

    ans = dict()
    tmp_a = 1
    tmp_b = 1
    xx = [None] * n

    for i in range(n):
        if (x >> i) &1:
            y = (a - tmp_a)%(m-1)
        else:
            y = (b+tmp_b)%(m+1)
        tmp_a *= 2
        tmp_a %= (m-1)
        tmp_b *= 2
        tmp_b %= (m+1)
        # print(tmp_a,tmp_b)

        z = x ^ (1<<i) 
        t = z
        z %= bin(z).count('1')
        # y = z
        # print(t,z,y)

        cnt = 1
        c = y
        while y != 0:
            # if y in ans.keys():
            #     cnt += ans[y]
            #     break
            cnt += 1
            y = solve(y)
        ans[c] = cnt
        xx[i] = cnt
    
    for i in range(n-1,-1,-1):
        print(xx[i])

Submission status: Wrong Answer

Solution code:
from collections import Counter
import math
def main():
    n = int(input())
    x = input().rstrip()
    for i in range(n):
        tmp = x[:]
        tmp = list(tmp)
        if tmp[i] == '0':
            tmp[i] = '1'
        else:
            tmp[i] = '0'
        tmp = "".join(tmp)
        # print('tmp', tmp)
        print(fn(int(tmp, 2)))

def fn(x):
    # print('x',x)
    bin_x = bin(x)
    if x == 0:
        return 0
    ans = 1
    c = x % bin_x.count('1')
    while c != 0:
        x = c
        bin_x = bin(x)
        c = x % bin_x.count('1')
        ans += 1
    return ans

Submission status: Wrong Answer

Solution code:
def popcount(n):
    ans = 0
    while (n > 0):
        ans += n % 2
        n = n // 2
    return ans


N = int(input())

popcountA = [0 for x in range(2 ** N)]
for i in range(1, 2**N):
    popcountA[i] = popcount(i)


AAA = [0 for x in range(2 ** N)]
for i in range(1, N):
    AAA[i] = AAA[i % popcountA[i]] + 1


X = int(input(), 2)

for i in range(N):

    Xi = X ^ (1 << (N-i-1))

    print(AAA[Xi])

Submission status: Wrong Answer

Solution code:
n = 100000
ans_count = [-1 for _ in range(n)]

for i in range(1,n+1):
    b = bin(i)
    b=list(b)
    a = b.count("1")
    f = i%a
    if f == 0:
        ans_count[i-1]=1
    else:
        ans_count[i-1] = ans_count[f-1]+1

ans_count = [0]+ ans_count

n= int(input())
inp = input()

x = list(inp)
org = int(inp, 2)
l = x.count("1")


for _ in range(n):
    print(0)

# for i in range(n):
#     a = x[i]
#     if a=="0":
#         N = org+(2**(n-i-1))
#         m= N%(l+1)
#         print(ans_count[m]+1)
#     else:
#         N = org-(2**(n-i-1))
#         m=N%(l-1)
#         print(ans_count[m]+1)

Submission status: Wrong Answer

Solution code:
import sys
import  math
from heapq import *
import fractions
import bisect
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

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

num_1=0
for i in range(N):
    if(X[i]=='1'):
        num_1+=1

mlist_num_1up=[0]*N
mlist_num_1down=[0]*N
mlist_num_1up[0]=1
mlist_num_1down[0]=1


if(num_1==1):
    for i in range(N):
        a=1
        print(a)
    sys.exit(0)
        
for i in range(1,N):
    mlist_num_1up[i]=(mlist_num_1up[i-1]*2)%(num_1+1)
    mlist_num_1down[i]=(mlist_num_1down[i-1]*2)%(num_1-1)

mlist_num_1up.reverse()
mlist_num_1down.reverse()

upmod_ori=0
downmod_ori=0
for i in range(N):
    if(X[i]=='1'):
        upmod_ori+=mlist_num_1up[i]
        downmod_ori+=mlist_num_1down[i]


fans=[0]*31
fans[0]=0
fans[1]=1
for i in range(2,31):
    mod=0
    for p in range(7):
        if((i>>p) & 1):
            mod+=1
    fans[i]=fans[i%mod]+1
    
for i in range(N):
    if(X[i]=='1'):
        mod=downmod_ori-mlist_num_1down[i]
        mod%=(num_1-1)
    else:
        mod=upmod_ori+mlist_num_1up[i]
        mod%=(num_1+1)
    mod1=0
    for p in range(31):
        if((mod>>p) & 1):
            mod1+=1
    print(fans[mod1]+1)

Submission status: Wrong Answer

Solution code:
def popcount(n):
    return str(bin(n)).count('1')

def main():
    N= int(input())
    X = input()
    for i in range(N):
        A = ''
        if X[i] == '1':
            A = X[:i] + '0' + X[i+1:]
        else:
            A = X[:i] + '1' + X[i+1:]
        c = int(A,2)
        cnt = 0

        print(cnt)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
X = int(input(), 2)
x_popcount = sum(map(int, bin(X)[2:]))
is_zeroflg = [x_popcount-1 <= 0, False]
x_popcounts = [max(1, x_popcount - 1), x_popcount + 1]
X_per_popcounts = [X % x_popcounts[0], X % x_popcounts[1]]
mods = [0, 0]
ans = [0]*N

if X == 0:
    for i in range(N-1):
        print(1)
    print(0)
    sys.exit()

def f(n):
    cnt = 0
    while n != 0:
        popcount = sum(map(int, bin(n)[2:]))
        n = n % popcount
        cnt += 1
    return cnt


flg = X & 1 ^ 1
mods[0] = (-1) % x_popcounts[0]
mods[1] = 1 % x_popcounts[1]
tmp = (X_per_popcounts[flg] + mods[flg]) % x_popcounts[flg]
ans[0] = f(tmp) + 1
if is_zeroflg[flg]:
    ans[0] = 0

for i in range(1, N):
    flg = (X >> i) & 1 ^ 1
    mods[0] = (mods[0] * 2) % (x_popcounts[0])
    mods[1] = (mods[1] * 2) % (x_popcounts[1])
    tmp = (X_per_popcounts[flg] + mods[flg]) % x_popcounts[flg]
    ans[i] = f(tmp) + 1
    if is_zeroflg[flg]:
        ans[i] = 0

print('\n'.join(map(str, ans[::-1])))

Submission status: Wrong Answer

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

def solve(a):
    pc = bin(a).count('1')
    if pc == 0:
        return 0
    elif pc == 1:
        return 1
    return solve(a % pc) + 1
        
for i in range(n):
    a = 1 * pow(10, n - 1) >> i ^ x
    print(solve(a))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

def solve():
    N = II()
    bb = input()
    X = list(map(int, bb))
    # print(X)
    num = int(bb, 2)
    # print(num)
    # return

    bit = sum(X)
    one_bit_cnt = {num: bit}
    f_cnt = {0: 0}

    # def popcount(n):
    #     return sum( list(map(int, list(bin(n).replace('0b', '')))))

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

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

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

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

    # def f(n, pop, c=0):
    #     # print(n, pop, c)
    #     if n == 0:
    #         return c
    #
    #     cnt = f_cnt.get(n, -1)
    #     if cnt == -1:
    #         n = n % pop
    #         pop = one_bit_cnt.get(n, -1)
    #         if pop == -1:
    #             pop = popcount(n)
    #             one_bit_cnt[n] = pop
    #         cnt = f(n, pop, c+1)
    #         f_cnt[n] = cnt - c - 1
    #     else:
    #         return cnt + c
    # #     return cnt
    #
    # def f(n, pop):
    #     cnt = 0
    #     while n > 0:
    #         fc = f_cnt.get(n, -1)
    #         if fc != -1:
    #             return cnt + fc
    #         n = n % pop
    #         pop = one_bit_cnt.get(n, -1)
    #         if pop == -1:
    #             pop = popcount(n)
    #             one_bit_cnt[n] = pop
    #         cnt += 1
    #
    #     return cnt

    ex = N-1
    for i, x in enumerate(X):
        if x == 1:
            n = num - pow(2, ex)
            pop = bit - 1
        else:
            n = num + pow(2, ex)
            pop = bit + 1
        one_bit_cnt[n] = pop
        # print(n, pop)
        fc = f_cnt.get(n, -1)
        if fc != -1:
            print(fc)
        else:
            cnt = 0
            while n > 0:
                fc = f_cnt.get(n, -1)
                if fc != -1:
                    return cnt + fc
                n = n % pop
                pop = one_bit_cnt.get(n, -1)
                if pop == -1:
                    pop = popcount(n)
                    one_bit_cnt[n] = pop
                cnt += 1
            print(cnt)
            f_cnt[n] = cnt

        ex -= 1
        # print(f_cnt)
    # print(f_cnt)

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
if __name__ == "__main__":
    CH = [0,1,1,2,1,2,1,2,1,2,1,2,1,2,2,3,1,2,1,2,2]
    N = int(input())
    X = input()
    s = 0
    for x in X:
        if x == "1":
            s += 1
    num = int(X,2)
    num1 = num%(s+1)
    if s > 1:
        num2 = num%(s-1)
    for i in range(N):
        if int(X[i])==1:
            p = s-1
            if p == 0:
                print(0)
                continue
            x = (num2-2**(N-1-i))%p
            if x > 20:
                if x != 0:
                    y = x%sum(map(int,list(bin(x))[2:]))
                    print(2+CH[y])
                else:
                    y = 0
                    print(1)
            else:
                print(1+CH[x])
        else:
            p = s+1
            x = (num1+2**(N-1-i))%p
            if x > 20:
                if x != 0:
                    y = x%sum(map(int,list(bin(x))[2:]))
                    print(2+CH[y])
                else:
                    y = 0
                    print(1)
            else:
                print(1+CH[x])

Submission status: Wrong Answer

Solution code:
LIM=200002
L=[0]*LIM

def bin_sum(Y):
    S=bin(Y)[2:]
    count=0
    for i in range(len(S)):
        count+=int(S[i])
    return count

def bin_sum2(Y):
    count=0
    for i in range(len(Y)):
        count+=int(Y[i])
    return count

for i in range(1,LIM):
    L[i]+=bin_sum(i)

def pop_num(N,b,L):
    if N==0:
        return 0
    v=N%b
    return pop_num(v,L[v],L)+1
    
def pop_num2(N,b,L,M):
    if N==0:
        return 0
    v=N%b
    return M[v]+1

M=[0]*200002
for i in range(1,200002):
    M[i]+=pop_num(i,L[i],L)
print(M)
X=int(input())
Y=input()
d=bin_sum2(Y)+1
c=bin_sum2(Y)-1
for i in range(X):
    Y_i=Y[:i]+str(abs(int(Y[i])-1))+Y[i+1:]
    if Y_i[i]=="1":
        b=d
    else:
        b=c
    print(pop_num2(int(Y_i,2),b,L,M))

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
X = int(input(), 2)
x_popcount = sum(map(int, bin(X)[2:]))
is_zeroflg = [x_popcount == 1, False]
x_popcounts = [max(1, x_popcount - 1), x_popcount + 1]
X_per_popcounts = [X % x_popcounts[0], X % x_popcounts[1]]
mods = [0, 0]
ans = [0]*N

if X == 0:
    for i in range(N-1):
        print(1)
    print(0)
    sys.exit()

def f(n):
    cnt = 0
    while n != 0:
        popcount = sum(map(int, bin(n)[2:]))
        n = n % popcount
        cnt += 1
    return cnt


flg = X & 1 ^ 1
mods[0] = (-1) % x_popcounts[0]
mods[1] = 1 % x_popcounts[1]
tmp = (X_per_popcounts[flg] + mods[flg]) % x_popcounts[flg]
ans[0] = f(tmp) + 1
if is_zeroflg[flg]:
    ans[0] = 0

for i in range(1, N):
    flg = (X >> i) & 1 ^ 1
    mods[0] = (mods[0] * 2) % (x_popcounts[0])
    mods[1] = (mods[1] * 2) % (x_popcounts[1])
    tmp = (X_per_popcounts[flg] + mods[flg]) % x_popcounts[flg]
    ans[i] = f(tmp) + 1
    if is_zeroflg[flg]:
        ans[i] = 0

print('\n'.join(map(str, ans[::-1])))

Submission status: Wrong Answer

Solution code:
N = int(input())
X = list(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.copy()
    x[i] = '1' if x[i] == '0' else '0'
    x = ''.join(x)
    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:
from functools import lru_cache

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

maxbit = x.count("1")

box = [0] * (maxbit + 1)

@lru_cache(maxsize=None)
def f(i):
  cnt = 1
  while i > 0:
    if box[i] != 0:
      return box[i] + cnt
    i %= bin(i).count("1")
    cnt += 1
  return cnt

for i in range(1, maxbit + 1):
  box[i] = f(i)

for i in range(lenx):
  if x[i] == "0":
    mb = maxbit + 1
    t = x10 + 2 ** (lenx - 1 - i)
  else:
    mb = maxbit - 1
    t = x10 - 2 ** (lenx - 1 - i)
  if t == 0:
    print(0)
  else:
    t %= mb 
    if t == 0:
      print(1)
    else:
      ans = f(t)
      box[t] = ans
      print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = input()
count = X.count("1")
total = int(X,2)
check = [0]*(N+1)
for i in range(1,count+1):
    pop = bin(i).count("1")
    if i%pop==0:
        check[i]=1
    else:
        check[i]= check[i%pop]+1
for i in range(N):
    if X[i] == '0':
        ans = (total+2**(N-1-i))%(count+1)
        print(check[ans]+1)
    else :
        if count == 1:
            print("1")
        else:
            ans = (total-2**(N-1-i))%(count-1)
            print(check[ans]+1)

Submission status: Wrong Answer

Solution code:
from collections import Counter

N = int(input())
X = input()
cnt = Counter(str(X))['1']
cnt = str(bin(cnt))[2:]
X = bin(int(X, 2))

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
X = int(input(), 2)
x_popcount = sum(map(int, bin(X)[2:]))
x_popcounts = [max(1, x_popcount - 1), x_popcount + 1]
X_per_popcounts = [X % x_popcounts[0], X % x_popcounts[1]]
mods = [0, 0]
ans = [0]*N

if X == 0:
    for i in range(N-1):
        print(1)
    print(0)
    sys.exit()

def f(n):
    cnt = 0
    while n != 0:
        popcount = sum(map(int, bin(n)[2:]))
        n = n % popcount
        cnt += 1
    return cnt


flg = X & 1 ^ 1
mods[0] = (-1) % x_popcounts[0]
mods[1] = 1 % x_popcounts[1]
tmp = (X_per_popcounts[flg] + mods[flg]) % x_popcounts[flg]
ans[0] = f(tmp) + 1
if x_popcounts[flg] == 0:
    ans[0] = 0

for i in range(1, N):
    flg = (X >> i) & 1 ^ 1
    mods[0] = (mods[0] * 2) % (x_popcounts[0])
    mods[1] = (mods[1] * 2) % (x_popcounts[1])
    tmp = (X_per_popcounts[flg] + mods[flg]) % x_popcounts[flg]
    ans[i] = f(tmp) + 1
    if x_popcounts[flg] == 0:
        ans[i] = 0

print('\n'.join(map(str, ans[::-1])))

Submission status: Wrong Answer

Solution code:
def pc(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f

N=int(input())
X=input()
x=int(X,2)
c=pc(x)

for i in range(N):
    if X[i]=="0":
        x2=x+2**(N-i-1)
        p=c+1
    else:
        x2=x-2**(N-i-1)
        p=c-1
    ans=0
    while x2>0:
        x2%=p
        p=pc(x2)
        ans+=1
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
X = input()

def popcount(n):
	if n == 0:
		return 0
	else:
		cnt = 0
		while 0 < n:
			cnt += 1
			p = "{:b}".format(n).count("1")
			n %= p
		return cnt

n = X.count("1")

n1 = n-1
n2 = n+1

q_1 = [0]*N
q_2 = [0]*N
for i in range(N):
	if n1 != 0:
		q_1[i] = pow(2, i, n1)
	if n2 != 0:
		q_2[i] = pow(2, i, n2)

mod_sum_1 = 0
mod_sum_2 = 0

for i in range(N):
	if X[-i-1] == "1":
		mod_sum_1 += q_1[i]
		mod_sum_2 += q_2[i]

q_1 = q_1[::-1]
q_2 = q_2[::-1]

for i in range(N):
	if X[i] == "1":
		m = n1
		mod_sum = mod_sum_1 - q_1[i]
	else:
		m = n2
		mod_sum = mod_sum_2 + q_2[i]
	if mod_sum == 0:
		print(0)
	else:
		print(popcount(mod_sum%m)+1)

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')

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

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')
    print(ans)

Submission status: Wrong Answer

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

def main():
    N = int(input())
    X = [None] * N
    l = list(input())
    Xc = 0
    for i in range(N):
        X[i] = int(l[i])
        Xc += X[i]

    for i in range(N):
        Y = X[:]
        Y[i] = Y[i]^1
        if Y[i]:
            div = Xc + 1
        else:
            div = Xc - 1
        # print(Y,div)
        count = 0
        ans = 0
        for j in range(N):
            if Y[j]:
                ans += pow(2,N-1-j)
                ans %= div
        count += 1
        while ans > 0:
            tmp = str(bin(ans)).count('1')
            ans %= tmp
            count += 1
        print(count)

if __name__ == "__main__":
    main()

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)))

Submission status: Wrong Answer

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

def calc(S, L):
    cnt = 0
    for i in range(L):
        if S[i] == "1":
            cnt += 1

    a_1 = 1
    r_1 = [0] * (L+1)
    for i in reversed(range(L)):
        r_1[i] = (r_1[i+1] + int(S[i]) * a_1) % cnt
        a_1 = (a_1 * 2) % cnt

    return r_1[0]

def calc_first(S, L):
    cnt = 0
    for i in range(L):
        if S[i] == "1":
            cnt += 1

    a_1 = 1
    a_2 = 1
    r_1 = [0] * (L+1)
    r_2 = [0] * (L+1)
    for i in reversed(range(L)):
        r_1[i] = (r_1[i+1] + int(S[i]) * a_1) % (cnt+1)
        if cnt-1 > 0:
            r_2[i] = (r_2[i+1] + int(S[i]) * a_2) % (cnt-1)

        a_1 = (a_1 * 2) % (cnt + 1)
        if cnt-1 > 0:
            a_2 = (a_2 * 2) % (cnt - 1)

    for i in range(L):
        if S[i] == "0":
            ans = (r_1[0] - r_1[i] + r_1[i+1] + pow(2, N-i-1, (cnt+1))) % (cnt+1)
        else:
            if cnt - 1 == 0:
                ans = 0
            else:
                ans = (r_2[0] - r_2[i] + r_2[i+1]) % (cnt-1)

        cnt_ans = 1
        while ans > 0:
            ans = calc(str(bin(ans))[2:], len(str(bin(ans))[2:]))
            cnt_ans += 1
        print(cnt_ans)

calc_first(X, N)

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
X = int(input(), 2)
x_popcount = sum(map(int, bin(X)[2:]))
x_popcounts = [max(1, x_popcount - 1), x_popcount + 1]
X_per_popcounts = [X % x_popcounts[0], X % x_popcounts[1]]
mods = [0, 0]
ans = [0]*N

if X == 0:
    for i in range(N-1):
        print(1)
    print(0)
    sys.exit()

def f(n):
    cnt = 0
    while n != 0:
        popcount = sum(map(int, bin(n)[2:]))
        n = n % popcount
        cnt += 1
    return cnt


flg = X & 1 ^ 1
mods[0] = (-1) % x_popcounts[0]
mods[1] = 1 % x_popcounts[1]
tmp = (X_per_popcounts[flg] + mods[flg]) % x_popcounts[flg]
ans[0] = f(tmp) + 1

for i in range(1, N):
    flg = (X >> i) & 1 ^ 1
    mods[0] = (mods[0] * 2) % (x_popcounts[0])
    mods[1] = (mods[1] * 2) % (x_popcounts[1])    
    tmp = (X_per_popcounts[flg] + mods[flg]) % x_popcounts[flg]
    ans[i] = f(tmp) + 1
    if x_popcounts[flg] == 0:
        ans[i] == 0

print('\n'.join(map(str, ans[::-1])))

Submission status: Wrong Answer

Solution code:
import numpy as np
from typing import List, Tuple

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


def divmod_long(bits: List[int], div: int) -> Tuple[List[int], int]:
    val = 0
    q = []
    for b in bits:
        val = val * 2 + b
        if val < div:
            q.append(0)
            continue
        else:
            q.append(1)
            val = val - div
    return q, val


def f(bits, div):
    cnt = 0
    q, r = divmod_long(bits, div)
    cnt += 1
    while r != 0:
        r = r % bin(r).count('1')
        cnt += 1
    return cnt


popcount = sum(X)
for i in range(N):
    if X[i] == 0:
        X[i] = 1
        print(f(X, popcount + 1))
        X[i] = 0
    else:
        X[i] = 0
        print(f(X, popcount - 1))
        X[i] = 1

Submission status: Wrong Answer

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

def calc(S, L):
    cnt = 0
    for i in range(L):
        if S[i] == "1":
            cnt += 1

    a_1 = 1
    r_1 = [0] * (L+1)
    for i in reversed(range(L)):
        r_1[i] = (r_1[i+1] + int(S[i]) * a_1) % cnt
        a_1 = (a_1 * 2) % cnt

    return r_1[0]

def calc_first(S, L):
    cnt = 0
    for i in range(L):
        if S[i] == "1":
            cnt += 1

    a_1 = 1
    a_2 = 1
    r_1 = [0] * (L+1)
    r_2 = [0] * (L+1)
    for i in reversed(range(L)):
        r_1[i] = (r_1[i+1] + int(S[i]) * a_1) % (cnt+1)
        if cnt-1 > 0:
            r_2[i] = (r_2[i+1] + int(S[i]) * a_2) % (cnt-1)

        a_1 = (a_1 * 2) % (cnt + 1)
        if cnt-1 > 0:
            a_2 = (a_2 * 2) % (cnt - 1)

    for i in range(L):
        if S[i] == "0":
            ans = (r_1[0] - r_1[i] + r_1[i+1] + pow(2, N-i-1, (cnt+1))) % (cnt+1)
        else:
            if cnt - 1 >= 0:
                ans = 0
            else:
                ans = (r_2[0] - r_2[i] + r_2[i+1]) % (cnt-1)

        cnt_ans = 1
        while ans > 0:
            ans = calc(str(bin(ans))[2:], len(str(bin(ans))[2:]))
            cnt_ans += 1
        print(cnt_ans)

calc_first(X, N)

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
X = int(input(), 2)
x_popcount = sum(map(int, bin(X)[2:]))
x_popcounts = [max(1, x_popcount - 1), x_popcount + 1]
X_per_popcounts = [X % x_popcounts[0], X % x_popcounts[1]]
mods = [0, 0]
ans = [0]*N

if X == 0:
    for i in range(N-1):
        print(1)
    print(0)
    sys.exit()

def f(n):
    cnt = 0
    while n != 0:
        popcount = sum(map(int, bin(n)[2:]))
        n = n % popcount
        cnt += 1
    return cnt


flg = X & 1 ^ 1
mods[0] = (-1) % x_popcounts[0]
mods[1] = 1 % x_popcounts[1]
tmp = (X_per_popcounts[flg] + mods[flg]) % x_popcounts[flg]
ans[0] = f(tmp) + 1

for i in range(1, N):
    flg = (X >> i) & 1 ^ 1
    if x_popcounts[flg] == 0:
        ans[i] == 0
    mods[0] = (mods[0] * 2) % (x_popcounts[0])
    mods[1] = (mods[1] * 2) % (x_popcounts[1])
    tmp = (X_per_popcounts[flg] + mods[flg]) % x_popcounts[flg]
    ans[i] = f(tmp) + 1

print('\n'.join(map(str, ans[::-1])))

Submission status: Wrong Answer

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

memo = [-1]*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 anss in ans:
    print(anss)