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: Time Limit Exceeded

Solution code:
def popcount(x):
  count = 0
  bin_x = bin(x)[2:]
  #print(bin_x)
  for i in bin_x:
    if i == "1":
      count += 1
  return count

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

for i in range(N):
  temp = []
  ans = 0
  for d in X:
    temp.append(d)
  #i番目のビット反転
  if temp[i] == "1":
    temp[i] = "0"
  else:
    temp[i] = "1"
  
  #10進数に変換(str -> int)
  bin_n = str("".join(map(str, temp)))
  int_n = int(bin_n,2)
  #print("int_n = " + str(int_n))

  while int_n > 0:
    ans += 1
    j = popcount(int_n)
    int_n = int_n % j

  print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=[0]*(n+1)
s=input()
num=0
def al(x):
    pop=0
    k=1
    while x>=k:
        if x&k: pop+=1
        k<<=1
    return pop
temp=0
for i in reversed(range(0,len(s))):
    if int(s[i]):
        num+=(1<<(len(s)-i-1))
        temp+=1
k=1
for i in reversed(range(1,n+1)):
    num1=num^k
    if num1:
        l[i]+=1
        num1%=temp+(1 if num1>num else -1)
    while num1:
        l[i]+=1
        num1%=al(num1)
    k<<=1
for i in range(1,n+1):
    print(l[i])

Submission status: Time Limit Exceeded

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)

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: Time Limit Exceeded

Solution code:
import copy
N = int(input())
X = list(input())

'''
def f(num):
    ii = 0
    while num!=0:
        num = num % str(bin(num)).count('1')
        ii+=1
    return ii
'''

for i in range(N):
    X2 = copy.copy(X)
    if X[i] == '0':
        X2[i] = '1'
    elif X[i] == '1':
        X2[i] = '0'
    X3 = "".join(X2)
    X4 = int(X3,2)
    ii = 0
    while X4!=0:
        X4 = X4 % str(bin(X4)).count('1')
        ii+=1
    print(ii)

Submission status: Time Limit Exceeded

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

N2 = 2**N

Y = [[] for _ in range(N+1)]
for i in range(1, N+1):
    y = X
    if y[i-1] == '0':
        y = int(y, 2) + 2**(N-i)
    else:
        y = int(y, 2) - 2**(N-i)
    Y[i] = y
    

Dp = [[] for _ in range(N2+1)]
Dp[0] = 0

for y in Y[1:]:
#    print()
#    print(y)
    count = 0
    Z = []
    if Dp[y] != []:
        ans = Dp[y]
#        print('!!')
#        break
    else:
        while y != 0:
            Z.append(y)
            y = y%bin(y).count('1')
            count += 1
#            print(y)
        ans = count
        for i, z in enumerate(Z):
            Dp[z] = ans - i
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x=input()
for i in range(n):
    a=x
    if a[i]=="0":
        a=a[:i] + "1" + a[i+1:]
    else:
         a=a[:i] + "0" + a[i+1:]
    a2=int(a,2)
    c=0
    b=a2
    if a2==0:
        print(0)
        continue
    while b!=0:
        z=0
        while a2!=0:
            if a2%2==1:
                z+=1
            a2=a2//2
        b=b%z
        a2=b
        c+=1
    print(c)

Submission status: Time Limit Exceeded

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

# N = 23
# A = '00110111001011011001110'

def popcount(n):
    B = format(n, 'b')
    c = 0
    for i in B:
        if i == '1':
            c += 1
    return c    

def div_pop(n):
    P = popcount(n)
    return n%P

c = 0
A10 = int(A,2)
for i in range(N):
    if A[i] == '1':
        c += 1


counter = []
AC = []
for i in range(N):
    if A[i] == '1':
        counter.append(c-1)
        AC.append(A10-2**(N-1-i))
        
    else:
        counter.append(c+1)
        AC.append(A10+2**(N-1-i))

for a in AC:
    ans = 0
    while a > 0:
        ans += 1
        a = div_pop(a)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache


@lru_cache(maxsize=None)
def popcount(n):
    return bin(n).count('1')


@lru_cache(maxsize=None)
def f(n):
    if n == 0:
        return 0
    else:
        n = n % popcount(n)
        return f(n) + 1


N = int(input())
S = input()
S_int = int(S, 2)
p = popcount(S_int)
for i in range(N-1, -1, -1):
    if S_int & (1 << i):
        p_next = p - 1
    else:
        p_next = p + 1

    if (p_next == 0):
        print(0)
        continue

    target = S_int ^ (1 << i)
    print(f(target % p_next) + 1)

Submission status: Time Limit Exceeded

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


def bc(x):
    return bin(x).count("1")


dp = [0] * 1000000
for i in range(n - 1, -1, -1):
    num = (2 ** i) ^ x
    ans = 0
    bit_count_init = bc(num)
    #    if dp[bit_count_init] != 0:
    #        print(dp[bit_count_init])
    #        continue
    while True:
        bit_count = bc(num)
        if num == 0:
            print(ans)
            dp[bit_count_init] = ans
            break
        num %= bit_count
        ans += 1
        if dp[num] != 0:
            print(dp[num] + ans)

Submission status: Time Limit Exceeded

Solution code:
# D

def p(n): #intで入力
    st = bin(n)
    return st.count("1")

def f(n):
    cnt =0
    while n>0:
        s=p(n)
        n = n%s
        cnt +=1
    print(cnt)
    return cnt

N=int(input())
X=input()
for i in range(N):
    if X[i]=="0":
        tmp="1"
    else:
        tmp="0"
    Y=X[:i]+tmp+X[i+1:]
    Z=int(Y,2)
    f(Z)

Submission status: Time Limit Exceeded

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

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
        new = new % popcount(str(bin(new)))
        if new == 0:
            print(counter)
            break

Submission status: Time Limit Exceeded

Solution code:
import copy

def main():
    n = int(input())
    X = [int(x) for x in input()]

    def fukugen(x):
        x.reverse()
        value = 0
        for idx, v in enumerate(x):
            value += v * 2**idx
        return value

    def f(x):
        cnt = 0
        while x > 0:
            y = bin(x).count('1')
            x = x % y
            cnt += 1
            if x != 0:
                f(x)
        return cnt
     
    cx = copy.deepcopy(X)
    for i in range(n):
        if X[i] == 0:
            cx[i] = 1
        else:
            cx[i] = 0
        f_cx = fukugen(cx)
        ans = f(f_cx)
        print(ans)
        cx = copy.deepcopy(X)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

def check(n, r):
    if n == 0:
        return print(r)
    d = str(bin(n)).count('1')
    check(n%d, r+1)
    
for i in range(N):
    e = -1
    if X[i] == '0':
        e = 1
    num = int(X, 2) + e * pow(2, N-1-i)
    check(num, 0)

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))

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()
s = ''
ans = [0 for _ in range(2**n + 1)]
pop = 0
for i in x:
    if i == '1': pop += 1

for i in range(n):
    if x[i] == '0':
        s = x[:i] + '1' + x[i+1:]
        pc = pop + 1
    else:
        s = x[:i] + '0' + x[i+1:]
        pc = pop - 1
    num = int(s, 2)
    cnt = 0
    while True:
        if num == 0:
            ans[int(s, 2)] = cnt
            print(cnt)
            break
        if ans[num] > 0:
            ans[int(s, 2)] = cnt + ans[num]
            print(cnt + ans[num])
            break
        num = (num%pc)
        cnt += 1
        pc = popcount(num)

Submission status: Time Limit Exceeded

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

xlist = [0] *n
ans =  [0] *n

def count(num):
    count = 0
    while num:
        count += num & 1
        num >>= 1
    return count



for i in range(n):
    xs = x
    if x[i] == '0':
        xs=x[:i]+'1'+x[i+1:]
    else:
        xs=x[:i]+'0'+x[i+1:]
    xlist[i]=xs

i=0


for xi in xlist:
    x = int(xi,2)
    a=0
    while not x ==0:
        x = x%count(x)
        a +=1
    ans[i]=a
    i+=1

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
X=input()
num=int(X,2)
c=X.count('1')
for i in range(n):
    tmpn=num
    tmp1=c
    if X[i]=='0':
        tmpn+=2**(n-i-1)
        tmp1+=1
    else:
        tmpn-=2**(n-i-1)
        tmp1-=1
    count=0
    while tmpn>0:
        tmpn%=tmp1
        tmp1=bin(tmpn).count("1")
        count+=1
    print(count)

Submission status: Time Limit Exceeded

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

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

def countSetBits(n): 
    count = 0
    while (n): 
        count += n & 1
        n >>= 1
    return count

# int変換
x = int(x,2)

def toggle_nth_bit(num: int, n: int):
    """下から数えてn桁目を反転"""
    return num ^ (1 << n)

ans = []

for i in range(0,n):
    tmp_x = toggle_nth_bit(x,i)
#    tmp_n = countSetBits(tmp_x)
    tmp_n = bin(tmp_x).count('1')
    tmp = 0
    while tmp_x > 0:
        tmp_x %= tmp_n
#        tmp_n = countSetBits(tmp_x)
        tmp_n = bin(tmp_x).count('1')
        tmp += 1
    ans.append(tmp)
    
print(*ans[::-1])

Submission status: Time Limit Exceeded

Solution code:
import sys

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

def ppp(x):
    s = format(x, 'b')
    return s.count('1')
def f(x):
    for j in range(x+10):
        if x == 0:
            return j
        x = x % ppp(x)
    

n = int(input())
x = input()
f_li = [f(i) for i in range(x.count('1')+1)]
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: Time Limit Exceeded

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


def arrayTo2(A):
    ans = 0
    l = len(A)
    for i in range(l):
        if (A[i] == '1'):
            ans += 2 ** (l-i-1)

    return ans


N = int(input())

popcountA = [0 for x in range(2**N)]

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


X = int(input(), 2)

for i in range(N):

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

    ans = 0
    n = Xi
    while (n > 0):
        n = n % popcountA[n]
        ans += 1

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy

def popcount(N):
  cnt = 0
  flag = True
  while not(N == 0 or N == 1):
    cnt += N % 2
    N = N // 2
  return cnt + N

N = int(input())
X = input()
d = dict()
sum = 0

for i, x in enumerate(X[::-1]):
  if x == "1":
    sum += 2 ** i
    
for n in range(N-1, -1, -1):
  if (sum >> n & 1) == 1:
    x = sum - 2**n
  else:
    x = sum + 2**n
  
  cnt = 0
  while x != 0:
    cnt += 1
    if d.get(x):
      x = x % d[x]
    else:
      d[x] = popcount(x)
      x = x % d[x]
  
  print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = input()
s = input()

hanten = 1 << int (n) - 1;
for i in range(int(n)):
    cal = (int(s, 2) ^ hanten)
    count = 0
    while (cal != 0):
        cal = cal % bin(cal).count('1')
        count = count + 1
    print(count)
    hanten = hanten >> 1

Submission status: Time Limit Exceeded

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

def calc(num, cnt, ans):
  if cnt == 0:
    ans += 1
    return ans
  mod = num % cnt
  if mod == 0:
    ans += 1
    return ans
  else:
    ans += 1
    cnt = bin(mod).count('1')
    return(calc(mod, cnt, ans))

n = int(X, 2)
c = X.count('1')
for i in range(1, N+1):
  num = n
  cnt = c
  if X[i-1] == '0':
    num += 2**(N-i)
    cnt += 1
    print(calc(num, cnt, 0))
  else:
    num -= 2**(N-i)
    cnt -= 1
    if num == 0:
      print(0)
    else:
      print(calc(num, cnt, 0))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = input()
ans = [0 for _ in range(N)]

def popcount(n):
  c = 0
  n = str(bin(n))[2:]
  for _ in range(len(n)):
    if n[_] == '1':
      c += 1
  return c

nofinish = [_ for _ in range(N)]
start = []
if N == 1:
  if X[0] == '1':
    a = '0'
  else:
    a = '1'
  ia = int(a, 2)
  start.append(ia)

if N > 1:
  if X[0] == '1':
    a = '0' + X[1:]
  else:
    a = '1' + X[1:]
  ia = int(a, 2)
  start.append(ia)

  for k in range(1, N-1):
    if X[k] == '1':
      a = X[:k] + '0' + X[k+1:]
    else:
      a = X[:k] + '1' + X[k+1:]
    ia = int(a, 2)
    start.append(ia)
  if X[-1] == '1':
    a = X[:-1] + '0'
  else:
    a = X[:-1] + '1'
  ia = int(a, 2) 
  start.append(ia)


for k in range(len(start)):
  for count in range(10*5):
    if start[k] == 0:
      ans[k] = count
      break
    else:
      start[k] = start[k] % popcount(start[k])
  


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

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy
from collections import deque
import collections
stdin = sys.stdin

mod = 10**9+7

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
x = ns()
dp = {}


def popcount(n):
    b = bin(n)
    return b.count('1')

def f(xx):
    res = 0
    x = int(xx, 2)
    p = int(xx, 2)
    tmpdp = {}
    while p>0:
        if p in dp:
            res += dp[p]
            break
        pop = popcount(p)
        p = p%pop
        res += 1
        tmpdp[p] = res
    dp[x] = res
    for i,j in tmpdp.items():
        dp[i] = res - j
    return res

for i in range(n):
    if x[i]=='0':
        tmp = x[:i] + '1' + x[i+1:]
        print(f(tmp))
    else:
        tmp = x[:i] + '0' + x[i+1:]
        print(f(tmp))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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


def pop_counter(n):
    return n % Counter(bin(n))['1']


ans = 0
for n, i in enumerate(X):
    ans = 0
    if i == '1':
        tmp = int_X - pow(2, N - 1 - n)
    else:
        tmp = int_X + pow(2, N - 1 - n)
    while tmp != 0:
        tmp = pop_counter(tmp)
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

x = input()
ans = []


def popcount(s):
    count = 0
    binary = str(bin(s))
    for i in range(len(binary)):
        if binary[i] == "1":
            count += 1
    return count


def f(n):
    count = 0
    while True:
        pop = popcount(n)
        if pop == 0:
            break
        n = n % pop
        count += 1
    ans.append(count)


for i in range(n):
    num = int(x, 2)
    if x[n-i-1] == "1":
        num -= 2**i
    else:
        num += 2**i
    f(num)


for i in range(len(ans)):
    print(ans[-i-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

for i in range(N):
    if X[i] == '1':
        tmp = - (1<<(N-i-1))
        n = int(X, 2) + tmp
    else:
        tmp = (1<<(N-i-1))
        n = int(X, 2) + tmp
        
    cnt = 0
    while n != 0:
        n %= Counter(bin(n))['1']
        cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = int(input(), 2)
def popcount(n):
    c = bin(n).count("1")
    print('S')
    return c
# したからi番目を反転
def reverse_x(i,x):
    a = 1<<i
    b = x^a
    return b
def f(n):
    def popcount(n):
        c = bin(n).count("1")
        return c
    count = 0
    while n != 0:
        n = n % popcount(n)
        count += 1
    return count
for i in range(N):
    print(f(reverse_x(N-i-1,X)))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = str(input())
x = list(X)
def popcount(x):
  l = list(bin(x))[2:]
  return sum(int(i) for i in l)

for n in range(N):
  xn = x.copy()
  xn[n] = str(1 - int(xn[n]))
  xn = int(''.join(map(str, xn)), 2)
  count = 0
  while int(xn) != 0:
    xn = xn%popcount(xn)
    count += 1
  print(count)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    X = int(input(),2)
    LIST = []
    PM = [-1]*N
    ANS = [0]*N
    TEMP = [0]*N
    CHAIND = [0]*N
    bit = 1
    for i in range(N):
        LIST.append(X^bit)
        PM[i] += (X & bit == 0)*2
        bit = bit<<1

    for i in range(N):
        cnt = count_ones_by_bitmask(X)
        if LIST[i]!=0:
            TEMP[i] += LIST[i] % (cnt+PM[i])
            ANS[i] += 1

    CHA = list(set(TEMP))

    for i in range(len(CHA)):
        an = 0
        cha = CHA[i]
        cnt = count_ones_by_bitmask(CHA[i])
        while cnt>0:
            an += 1
            cha = cha%cnt
            cnt = count_ones_by_bitmask(cha)
        CHAIND[CHA[i]] = an

    for i in reversed(range(N)):
        print(ANS[i]+CHAIND[TEMP[i]])





def count_ones_by_bitmask(num):
    count = 0
    while num:
        count += num & 1
        num >>= 1
    return count

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

    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:
            fc = f(n, pop)
            print(fc)
            f_cnt[n] = fc

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

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
x = eval('0b' + input())

memo = {}

# def slove(x):
#     cnt = 0
#     tmp = []
#     while x:
#         if x in memo:
#             return cnt + memo[x]
#         else:

#         x = x % popcount(x)
#         cnt += 1
#     return cnt

def solve(x, cnt):
    if x == 0:
        return cnt

    if x in memo:
        return cnt + memo[x]
    else:
        ans = solve(x % bin(x).count("1"), cnt + 1)
        memo[x] = ans - cnt
        return ans


ans = []

for i in range(n):
    y = 0
    if x & (1 << i):
        y = x & ~(1 << i)
    else:
        y= x | (1 << i)
    ans.append(solve(y, 0))

for ansi in reversed(ans):
    print(ansi)

Submission status: Time Limit Exceeded

Solution code:
def bitcount(N):  # 立ってるbitの数
    bitcnt = [0]
    for _ in range(N):
        bitcnt += [i + 1 for i in bitcnt]
    return bitcnt

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

num = 0
for i, bit in enumerate(x[::-1]):
    num += int(bit) * pow(2, i)
lbit = bitcount(18)
cnt = x.count('1')

for i in range(n):
    ans = 0
    if x[i] == '0':
        tmp = num + pow(2, n - (i + 1))
        ctmp = cnt + 1
    elif x[i] == '1':
        tmp = num - pow(2, n - (i + 1))
        ctmp = cnt -  1
    while tmp > 0:
        ans += 1
        tmp %= ctmp
        ctmp = lbit[tmp]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

def f(num):
    ans = 0

    while num != 0:
        pop_count = bin(num).count('1')
        num %= pop_count
        ans += 1
        
    return ans

def main():
    n = i_input()
    x = s_input()

    x10 = int(x, 2)

    for i in range(n):
        if x[i] == '0':
            num = x10 + 2 ** (n-1-i)
        else:
            num = x10 - 2 ** (n-1-i)
        print(f(num))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=input()
X=int(S,2)

#Sのビット数
bitcount=0
for i in range(N):
  if S[i]=='1':
    bitcount+=1

def f(n):
  c=0
  x=1
  while x<=n:
    if n&x>0:
      c+=1
    x*=2
  return n%c

ls=[0 for i in range(bitcount+2)]  
ls2=[0 for i in range(bitcount+2)]
for i in range(1,bitcount+2):
  ls[i]=f(i)
  ls2[i]=ls2[ls[i]]+1

for i in range(N):
  if S[i]=='0':
    print(ls2[(X^(2**(N-1-i)))%(bitcount+1)]+1)
  else:
    if (X^(2**(N-1-i)))==0:
      print(0)
    else:
      print(ls2[(X^(2**(N-1-i)))%(bitcount-1)]+1)