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 = eval("0b" + input())

def toggl_ith_bit(num, i):
    return num ^ (1 << i)

def popcount(num):
    s = 0
    b = num
    while b != 0:
        s += (b & 1 > 0)
        b >>= 1
    return s

x_count = popcount(x)
table = [-1] * (n + 1)

for i in range(n - 1, -1, -1):
    xi = toggl_ith_bit(x, i)
    if xi == 0:
        print(0)
        continue
    xi_count = x_count + 1 if (xi & (1 << i)) else x_count - 1
    cnt = 1
    xi %= xi_count
    l = []
    while xi != 0:
        if table[xi] != -1:
            cnt = table[xi]
            break
        l.append(xi)
        cnt += 1
        xi %= popcount(xi)
    for hoge in l:
        table[hoge] = cnt
    print(cnt)

Submission status: Wrong Answer

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

def main():
  n = int(input())
  x = input()
  count = 0
  sub = 1
  last = [None]*n
  for i in range(n):
    if x[i] == "1":
      count += 1
            
  if count == 0:
    for i in range(n):
      print(1)
    sys.exit()
  if count == 1:
    if x[-1] == "1":
      for i in range(n-1):
        print(2)
      print(0)
      sys.exit()
    else:
      for i in range(n-1):
        if x[i] == "1":
          print(0)
        else:
          print(1)
      print(2)
      sys.exit()

  sub1, sub2 = 1, 1
  num1, num2 = 0, 0
  for i in range(n):
    if count-1 == 1:
      sub1 = 0
    last[i] = [sub1, sub2]
    if x[n-i-1] == "1":
      num1 += sub1
      num2 += sub2
      num1 %= count-1
      num2 %= count+1
    sub1 *= 2
    sub2 *= 2
    sub1 %= count-1
    sub2 %= count+1
            
    
    
  key = [0]*(2**18+1)
  for i in range(1, 2**18):
    c = 0
    for j in range(18):
      if (i>>j)&1:
        c += 1
    judge = i%c
    key[i] = key[judge] + 1

  for i in range(n):
    if x[i] == "1":
      judge = (num1+count-1-last[n-1-i][0])%(count-1)
      print(1+key[judge])
    else:
      judge = (num2+last[n-1-i][1])%(count+1)
      print(1+key[judge])

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
n=int(input())
x=int(input(),2)
A=[0]*(n+1)
A[1]=1
def popcount(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
for i in range(2,n+1):
  k=popcount(i)
  A[i]=A[i%k]+1
for i in range(n):
  y= x^(1<<(n-1-i))
  p=popcount(y)
  if p==0:
    print(0)
  else:  
    print(A[y%(popcount(y))]+1)

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(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:
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    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=input()

    digit=x.count('1')+1
    l=[0]*digit

    def F(n):
        cnt=0
        while True:
            if n==0: break
            n%=popcount(n)
            cnt+=1
        return cnt
    
    Rem=[0]*digit
    for i in range(digit):
        Rem[i]=F(i)
    
    for i in reversed(range(len(x))):
        tenx=int(x,2)
        nx=tenx^(2**i)
        pc=popcount(nx)
        if pc==0:
            print(0)
            continue
        else:
            rem=nx%pc
            if rem==0: print(1)
            else: print(Rem[rem]+1)



    
resolve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7

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

def main():
    for i in range(N):
        Y = X[:]
        Y[i] = int(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 += 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 sys
from io import StringIO
import unittest

sys.setrecursionlimit(20000000)

def yn(b):
    print("Yes" if b==1 else "No")
    return

def count_ones_by_bin(num):
    bin_num = bin(num)[2:]
    count = 0
    for i in bin_num:
            count += int(i)
    return count

def resolve():
    readline=sys.stdin.readline

    n=int(readline())
    x=readline().rstrip()

    #pc=[0]*(10**5+1)
    #for i in range(1,10**5):
    #    pc[i]=count_ones_by_bin(i)
    amr1=[0]*((10**5)*2 + 5)
    amr2=[0]*((10**5)*2 + 5)
    bits=[False]*((10**5)*2 + 5)

    bcnt=0
    j=0
    for i in x:
        if int(i)==1:
            bcnt += 1
            bits[j]=True
        j+=1

    base1=0
    base2=0
    for i in range(n):
        jo=n-i-1
        amr1[i]=pow(2,jo,bcnt+1)
        if (bcnt-1)==0:
            amr2[i]=pow(2,jo)
        else:
            amr2[i]=pow(2,jo,bcnt-1)
        if bits[i]==True:
            base1+=amr1[i]
            base2+=amr2[i]
    for i in range(n):
        ans=0
        if bits[i]==True: #1->0
            if (bcnt-1)==0:
                base=0
            else:
                base=(base2-amr2[i])%(bcnt-1)
        else:
            base=(base1+amr1[i])%(bcnt+1)
        ans+=1
        while base > 0:
            pp=count_ones_by_bin(base)
            base=base%pp
            ans+=1
        print(ans)
    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Wrong Answer

Solution code:

import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce
from itertools import groupby
from heapq import heapify, heappush, heappop

# sys.setrecursionlimit(5000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return map(lambda x: x + d, A)
def ldec(A, d=1): return map(lambda x: x - d, A)

N = n1()
X = int(s1(), 2)

#tbl = array1(N+1, -1)
tbl = {}
tbl[0] = 0

def search(n, count):
    if n == 0:
        return count

    if n == 1:
        return count + 1

    if n in tbl:
        return tbl[n]

    m = n % bin(n).count("1")
    t = search(m, count + 1)
    tbl[m] = t
    return t

def f(x, n):
    b = bin(x)[2:]
    b = b.zfill(N)
    #print(b),
    #print((b[:n] + "x" + b[n+1:]).zfill(N))

    if b[n] == "1":
        #print(b[:n] + "0" + b[n+1:])
        return int(b[:n] + "0" + b[n+1:], 2)

    return int(b[:n] + "1" + b[n+1:], 2)

"""
for n in range(1, 10):
    ans = search(n, 0)
    print(ans)

print("-"*10)
"""

for i in range(N):
    #print(i, f(X, i)),
    ans = search(f(X, i), 0)
    print(ans)

Submission status: Wrong Answer

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

def main():
  n = int(input())
  x = input()
  count = 0
  sub = 1
  last = [None]*n
  for i in range(n):
    if x[i] == "1":
      count += 1
            
  if count == 0:
    for i in range(n):
      print(1)
    sys.exit()
  if count == 1:
    if x[-1] == "1":
      for i in range(n-1):
        print(2)
      print(0)
      sys.exit()
    else:
      for i in range(n-1):
        if x[i] == "1":
          print(0)
        else:
          print(1)
      print(2)
      sys.exit()

  sub1, sub2 = 1, 1
  num1, num2 = 0, 0
  for i in range(n):
    if count-1 == 0:
      sub1 = 0
    last[i] = [sub1, sub2]
    if x[n-i-1] == "1":
      num1 += sub1
      num2 += sub2
      num1 %= count-1
      num2 %= count+1
    sub1 *= 2
    sub2 *= 2
    sub1 %= count-1
    sub2 %= count+1
            
    
    
  key = [0]*(2**18+1)
  for i in range(1, 2**18):
    c = 0
    for j in range(18):
      if (i>>j)&1:
        c += 1
    judge = i%c
    key[i] = key[judge] + 1

  for i in range(n):
    if x[i] == "1":
      judge = (num1+count-1-last[n-1-i][0])%(count-1)
      print(1+key[judge])
    else:
      judge = (num2+last[n-1-i][1])%(count+1)
      print(1+key[judge])

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
    if i == 0:
        ans = [0] + [2] * (N - 1)
    else:
        ans = [2] + [1] * (i - 2) + [0] + [1] * (N - i)
    ans = ans[::-1]
    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:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""





n = onem()

po = input()
#num = int("0B" + po,0)
co = po.count("1")

num = [0,0]

for i in range(n):
	num[0] *= 2
	num[1] *= 2
	if po[i] == "1":
		num[0] += 1
		num[1] += 1
	if co > 1:
			num[0] %= co-1
	num[1] %= co+1
	

for i in range(n):
	if po[i] == "0":
		coco = co + 1

		ima = num[1] + pow(2,(n-1-i),coco)
		ima %= coco
		coco = format(ima,"b").count("1")
		count = 1
		while True:
			if ima == 0:
				break
			else:
				ima %= coco
				count += 1
				"""
				if ima >= 10**5 + 1:
					coco = dp[ima-(10**5 + 1)]
				else:
				"""
				coco = format(ima,"b").count("1")

	else:
		coco = co - 1
		if coco == 0:
			count = 0
			continue
		ima = num[0] - pow(2,(n-1-i),coco)
		ima %= coco
		count = 1
		coco = format(ima,"b").count("1")
		while True:
			if ima == 0:
				break
			else:
				ima %= coco
				count += 1
				"""
				if ima >= 10**5 + 1:
					coco = dp[ima-(10**5 + 1)]
				else:
				"""
				coco = format(ima,"b").count("1")
	print(count)

Submission status: Wrong Answer

Solution code:
def mpower(a, b, n):
    if b == 0:
        return 1
    if b == 1:
        return a % n
    a1 = a
    k = 1
    while a1 < n and k < b:
        a1 = a1 * a
        k = k + 1

    a1 = a1 % n
    b1 = b // k
    a2 = a
    b2 = b % k
    return (mpower(a1, b1, n)*mpower(a2, b2, n)) % n


def main():
    n = int(input())
    x = input()
    k = int(x, 2)
    p = x.count("1")
    f = [0] * (n + 1)
    for i in range(1, n + 1):
        f[i] = f[i % bin(i).count("1")] + 1
    for i in range(n - n // 10, n):
        if x[i] == "1":
            pi = p - 1
            if pi == 0:
                print(0)
                continue
            print(f[(k % pi - mpower(2, n - i - 1, pi)) % pi] + 1)
        else:
            pi = p + 1
            print(f[(k % pi + mpower(2, n - i - 1, pi)) % pi] + 1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce
from itertools import groupby
from heapq import heapify, heappush, heappop

# sys.setrecursionlimit(5000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return map(lambda x: x + d, A)
def ldec(A, d=1): return map(lambda x: x - d, A)

N = n1()
X = int(s1(), 2)

#tbl = array1(N+1, -1)
tbl = {}
tbl[0] = 0

def search(n, count):
    if n == 0:
        return count

    if n == 1:
        return count + 1

    if n in tbl:
        return tbl[n]

    m = n % bin(n).count("1")
    t = search(m, count + 1)
    tbl[m] = t
    return t

def f(x, n):
    b = bin(x)[2:]
    b = b.zfill(N)
    #print(b),
    #print((b[:n] + "x" + b[n+1:]).zfill(N))

    if b[n] == "1":
        #print(b[:n] + "0" + b[n+1:])
        return int(b[:n] + "0" + b[n+1:], 2)

    return int(b[:n] + "1" + b[n+1:], 2)


for n in range(1, 10):
    ans = search(n, 0)
    print(ans)

print("-"*10)

for i in range(N):
    #print(i, f(X, i)),
    ans = search(f(X, i), 0)
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""





n = onem()

po = input()
#num = int("0B" + po,0)
co = po.count("1")

num = [0,0]

for i in range(n):
	num[0] *= 2
	num[1] *= 2
	if po[i] == "1":
		num[0] += 1
		num[1] += 1
	if co > 1:
			num[0] %= co-1
	num[1] %= co+1
	

for i in range(n):
	if po[i] == "0":
		coco = co + 1

		ima = num[1] + pow(2,(n-1-i),coco)
		ima %= coco
		coco = format(ima,"b").count("1")
		count = 1
		while True:
			if ima == 0:
				break
			else:
				ima %= coco
				count += 1
				"""
				if ima >= 10**5 + 1:
					coco = dp[ima-(10**5 + 1)]
				else:
				"""
				coco = format(ima,"b").count("1")

	else:
		coco = co - 1
		if coco == 0:
			continue
		ima = num[0] - pow(2,(n-1-i),coco)
		ima %= coco
		count = 1
		coco = format(ima,"b").count("1")
		while True:
			if ima == 0:
				break
			else:
				ima %= coco
				count += 1
				"""
				if ima >= 10**5 + 1:
					coco = dp[ima-(10**5 + 1)]
				else:
				"""
				coco = format(ima,"b").count("1")
	print(count)

Submission status: Wrong Answer

Solution code:
n=int(input(""))
x=input("")
def pop(n):
    i=0
    while(n>0):
        if(n%2==1):
            i+=1
        n=int(n/2)
    return i
listx=[]
for i in range(n):
    listx+=[int(x[n-1-i])]
tt=0
listt=[]
for i in range(n):
    tt+=listx[i]*2**i

Submission status: Wrong Answer

Solution code:
import sys
import math
import itertools
import random
def popcount(n,cnt):
    tmp=str(bin(n))
    num=0
    for i in range(len(tmp)):
        if(tmp[i]=='1'):
            num+=1
    if(num==0):
        return cnt+1
    elif(n%num==0):
        lis[n-1]=1
        return cnt+1
    elif(n%num-1 in lis):
        return lis[n%num-1]+1
    else:
        return popcount(n%num,cnt+1) 
n=int(input())
x=input()
lis={}
for i in range(n):
    tmp=x
    if(tmp[i]=='0'):
        tmp=tmp[:i]+'1'+tmp[i+1:]
    else:
        tmp=tmp[:i]+'0'+tmp[i+1:]
    ans=popcount(int(tmp,2),0)
    print(ans)
    lis[int(tmp,2)-1]=ans

Submission status: Wrong Answer

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

def main():
  n = int(input())
  x = input()
  count = 0
  sub = 1
  last = [None]*n
  for i in range(n):
    if x[i] == "1":
      count += 1
            
  if count == 0:
    for i in range(n):
      print(1)
    sys.exit()
  if count == 1:
    if x[-1] == "1":
      for i in range(n-1):
        print(2)
      print(0)
      sys.exit()
    else:
      for i in range(n-1):
        if x[i] == "1":
          print(0)
        else:
          print(1)
      print(2)
      sys.exit()

  sub1, sub2 = 1, 1
  num1, num2 = 0, 0
  for i in range(n):
    last[i] = [sub1, sub2]
    if x[n-i-1] == "1":
      num1 += sub1
      num2 += sub2
      num1 %= count-1
      num2 %= count+1
    sub1 *= 2
    sub2 *= 2
    sub1 %= count-1
    sub2 %= count+1
            
    
    
  key = [0]*(2**18+1)
  for i in range(1, 2**18):
    c = 0
    for j in range(18):
      if (i>>j)&1:
        c += 1
    judge = i%c
    key[i] = key[judge] + 1

  for i in range(n):
    if x[i] == "1":
      judge = (num1+count-1-last[n-1-i][0])%(count-1)
      print(1+key[judge])
    else:
      judge = (num2+last[n-1-i][1])%(count+1)
      print(1+key[judge])

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
N = int(input())
X = list(map(int, input()))

Xp = sum(X)
        
# print(Xp)
a = 0
b = 0
# c = 0
for i, x in enumerate(X):
    i_reverse = N-i-1
    if Xp > 1:
        a = (a + x * (1<<i_reverse)) % (Xp-1)
    b = (b + x * (1<<i_reverse)) % (Xp+1)
    # c = (c + x * (1<<i_reverse))
    # print(bin(c))

# print(a, b)

for i in range(N):
    i_reverse = N-i-1
    if Xp > 1:
        m = ([a, b][X[i]==0] + [-1, 1][X[i]==0] * (1<<i_reverse)) % [Xp-1, Xp+1][X[i]==0]
        count = 1
        # print(i, ([a, b][X[i]==0], [-1, 1][X[i]==0]*(1<<i_reverse)), [Xp-1, Xp+1][X[i]==0], X[i]==0)
        # print(m)
        while m > 0:
            p = sum([int(c) for c in str(bin(m)[2:])])
            m = m % p
            count += 1
        print(count)
    else:
        if X[i]==0:
            print(1)
        else:
            print(0)

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):
    cnt = 1
    nex = popcount[i]
    while nex != 0:
        nex = popcount[nex]
        cnt += 1
    co[i] = cnt

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 collections import defaultdict
N = int(input())
X = list(input())
d = defaultdict(int)

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

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)
        if start == 0:
            Ans.append(c)
        else:
            while(True):
                start = d[start]
                c += 1
                if start == 0:
                    break
            Ans.append(c)
    p *= 2
    
for i in Ans[::-1]:
    print(i)

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):
    # 上から順番に見ていっている
    # print("aaa",d,X[d],n-d-1,"cnt",cnt)
    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)
# print(dp)

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
    c = bin(n).count("1")
    while n % c != 0:
        cnt += 1
        n = n%c
        c = bin(n).count("1")
    memo[n] = cnt
    return cnt
# ans = []
# print(dp)
for d in dp:
    ans = (calc(d))
    print(ans)
# print(ans)

Submission status: Wrong Answer

Solution code:
def dfs(n):
    if n == 0:
        return 0
    s = str(format(n, "b"))
    c = s.count("1")
    return dfs(n % c) + 1
n = int(input())
x = input()
xi = int(x, 2)
c = x.count("1")
l = []
for i in range(1, c + 2):
    l.append(dfs(i))
for i in range(n):
    if x[i] == "1":
        m = xi - pow(2, n - i - 1)
        c2 = c - 1
    else:
        m = xi + pow(2, n - i - 1)
        c2 = c + 1
    if m > c2:
        if m % c2 == 0:
            print(1)
        else:
            print(l[m % c2 - 1] + 1)
    else:
        print(l[m - 1])

Submission status: Wrong Answer

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

# def my_pow(base, n, mod):
#     if n == 0:
#         return 1
#     x = base
#     y = 1
#     while n > 1:
#         if n % 2 == 0:
#             x *= x
#             n //= 2
#         else:
#             y *= x
#             n -= 1
#         x %= mod
#         y %= mod
#     return x * y % mod
MOD = 10 ** 9 + 7

N = int(input())
X = list(input())
ones = X.count('1')

def popcount(n):
    ret = 0
    while n > 0:
        if n % 2 == 1:
            ret += 1
        n //= 2
    return ret

pows = [0] * N
def set_pows():
    pows[0] = 1
    for i in range(1, N):
        pows[i] = (pows[i - 1] * 2) % MOD
set_pows()

A = 0
d = 1
for a in X[::-1]:
    A += (int(a) * d) % MOD
    d *= 2

for i in range(N):
    ans = 1
    total = ones
    sumA = A
    if X[i] == '0':
        total += 1
        sumA += pows[N - i - 1]
    else:
        total -= 1
        sumA -= pows[N - i - 1]
    if total == 0:
        print(0)
        continue
    n = sumA % total
    while n != 0:
        n = n % popcount(n)
        ans += 1
    print(ans)

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[::-1]):
        if b == '1':
            break
    if i == 0:
        ans = [0] + [2] * (N - 1)
    else:
        ans = [2] + [1] * (i - 2) + [0] + [1] * (N - i)
    ans = ans[::-1]
    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()
X10=int(X,2)
one=X.count('1')
if one>1:
  a=X10%(one-1)
  b=X10%(one+1)
  c=one-1
  d=one+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]=='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)
else:
  for i in range(N):
    if X[i]==0:
      if X[N-1]==1:
        print(2)
      else:
        print(1)
    if X[i]==1:
      print(0)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n=int(input())
x=input()
d={}

for i in range(n):
  count=0
  if x[i]=="1":
    y=x[:i]+"0"+x[i+1:]
  else:
    y=x[:i]+"1"+x[i+1:]
  c=int(y,2)
  a=int(y,2)

  while True:
    if a in d:
      print(d[a])
      break
    b=bin(a).count("1")
    if b==0 or a==0:
      d[c]=count
      print(count)
      break
    a%=b
    count+=1

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N = int(readline())
    X = int(readline().strip(), 2)


    def count(x):
        cnt = 0
        while x:
            x %= bin(x).count("1")
            cnt += 1
        return cnt
        
    ans = []
    for i in range(N):
        tmp = X ^ (1 << i)
        ans.append(count(tmp))

    print(ans[::-1])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from functools import lru_cache
from collections import Counter


@lru_cache(maxsize=4*(10**5))
def _f(n):
    string=bin(n)
    popcount=string.count('1')
    return n%popcount

@lru_cache(maxsize=4*(10**5))
def f(n):
    if n==0:
        return 0
    else:
        return 1+f(_f(n))

cache=[f(i) for i in range(2*(10**5)+10)]


N=int(input())
X=[i for i in input()]

pc=0
for x in X:
    if x=='1':
        pc+=1

first=[]

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

    if pc==0:
        first.append(0)
    else:
        first.append(int("".join(X), 2)%pc)


    if X[i]=='1':
        X[i]='0'
        pc-=1
    else:
        X[i]='1'
        pc+=1

for f in first:
    print(cache[f]+1)