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

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


inp = input()
x = list(inp)

org = int(inp, 2)
if "1" in x:      
    l = x.count("1")
else:
    l = 0

d = {}
for i in range(n+1):
    d[i]=ans_count[i]




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

Submission status: Time Limit Exceeded

Solution code:
"""
    こんにちは。これはクシャルです
    
    Author : thekushalghosh (クシャル)
    Team   : CodeDiggers
 
    I prefer Python language over the C++ language :p :D
        
    Visit my website : thekushalghosh.github.io
"""
import sys,math,cmath,time
start_time = time.time()
##########################################################################
################# ---- THE ACTUAL CODE STARTS BELOW ---- #################
    
def solve():
    n = inp()
    s = insr()
    a = [0] * (n + 1)
    for i in range(1,n + 1):
        q = bin(i).replace("0b","")
        a[i] = a[i % q.count("1")] + 1
    w = s.count("1")
    qq = int(s,2)
    for i in range(n):
        qw = 0
        if s[i] == "0":
            qw = qw + (2 ** (n - i - 1))
            w = w + 1
        else:
            qw = qw - (2 ** (n - i - 1))
            w = w - 1
        if w == 0:
            print(0)
        else:
            print(a[(qq + qw) % w] + 1)
        if s[i] == "0":
            w = w - 1
        else:
            w = w + 1
    
################## ---- THE ACTUAL CODE ENDS ABOVE ---- ##################
##########################################################################
 
def main():
    global tt
    if not ONLINE_JUDGE:
        sys.stdin = open("input.txt","r")
        sys.stdout = open("output.txt","w")
    t = 1
    for tt in range(t):
        solve()
    if not ONLINE_JUDGE:
        print("Time Elapsed :",time.time() - start_time,"seconds")
        sys.stdout.close()
    
#---------------------- USER DEFINED INPUT FUNCTIONS ----------------------#
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    return(input().strip())
def invr():
    return(map(int,input().split()))
 
#------------------ USER DEFINED PROGRAMMING FUNCTIONS ------------------#
def counter(a):
    q = [0] * max(a)
    for i in range(len(a)):
        q[a[i] - 1] = q[a[i] - 1] + 1
    return(q)
def counter_elements(a):
    q = dict()
    for i in range(len(a)):
        if a[i] not in q:
            q[a[i]] = 0
        q[a[i]] = q[a[i]] + 1
    return(q)
 
def string_counter(a):
    q = [0] * 26
    for i in range(len(a)):
        q[ord(a[i]) - 97] = q[ord(a[i]) - 97],1
    return(q)
 
def factors(n):
    q = []
    for i in range(1,int(n ** 0.5) + 1):
        if n % i == 0: q.append(i); q.append(n // i)
    return(list(sorted(list(set(q)))))
 
def prime_factors(n):
    q = []
    while n % 2 == 0: q.append(2); n = n // 2
    for i in range(3,int(n ** 0.5) + 1,2):
        while n % i == 0: q.append(i); n = n // i
    if n > 2: q.append(n)
    return(list(sorted(q)))
 
def transpose(a):
    n,m = len(a),len(a[0])
    b = [[0] * n for i in range(m)]
    for i in range(m): 
        for j in range(n): 
            b[i][j] = a[j][i]
    return(b)
#-----------------------------------------------------------------------#
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
    input = sys.stdin.readline
main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x=input()
xx=x.count('1')
xx2=int(x,2)
l=[0]
for i in range(1,xx+2):
    i1=str(bin(i)).count('1')
    num=0
    while i!=0:
        i%=i1
        i1=str(bin(i)).count('1')
        num+=1
    l.append(num)

k=2**n
for i in range(n):
    k//=2
    if x[i]=='0':
        xxx=xx+1
        xxx2=xx2+k
    else:
        xxx=xx-1
        xxx2=xx2-k
    if xxx2==0:
        print(0)
    elif xxx2%xxx==0:
        print(1)
    elif xxx2<=xx+1:
        print(l[xxx2])
    else:
        print(l[xxx2%xxx]+1)

Submission status: Time Limit Exceeded

Solution code:
memo = dict()
def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

def func(p):
    hozon = p
    r = 0
    while p > 0:
        if p in memo:
            r += memo[p]
            break
        d = popcnt(p)
        # print(p, d)
        p %= d
        r += 1

    memo[hozon] = r
    return r


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

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

bin_num = int(x, 2)
L = [[0, 0] for _ in range(n)]  # [数, bit数]

for i in range(n):
    if x[i] == "1":
        L[i][0] = bin_num - 2**(n-i-1)
        L[i][1] = bit_total - 1
    else:
        L[i][0] = bin_num + 2 ** (n - i - 1)
        L[i][1] = bit_total + 1
# print(bit_total)
# print(L)

for i in range(n):
    p = L[i][0]
    d = L[i][1]
    ans = 0
    # print(p)
    if p > 0:
        ans += 1
        p %= d
        ans += func(p)

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = input()
def count_ones_by_minus(num):
    count = 0
    while num:
        num &= num -1
        count += 1
    return count
first_cnt = X.count("1")
DP = [0]*(N+1)
for i in range(1,N+1):
    DP[i] = DP[i%count_ones_by_minus(i)]+1
X_ = int(X,2)
for i in range(N):
    tmp = X_
    cnt = first_cnt
    if X[i] == "0":
        tmp += 2**(N-1-i)
        cnt += 1
    else:
        tmp -= 2**(N-1-i)
        cnt -= 1
    if tmp == 0:
        print("0")
        continue
    print(DP[tmp%cnt]+1)

Submission status: Time Limit Exceeded

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

def popcount(n, cnt, dic):
    if n in dic:
        kos = dic[n]
    else:
        cnt1 = 0
        for i in str(bin(n))[2:]:
            if i == "1":
                cnt1 += 1
        dic[n] = cnt1
        kos = cnt1
    dic2 = dic.copy()

    if n != 0:
        return popcount(n%kos, cnt+1, dic2)
    else:
        return cnt

for i in range(1, N+1):
    mask = 1<<N-i
    x = X ^ mask
    print(popcount(x, 0, {}))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
_x = list(reversed(list(input())))
x = 0
for i in range(n):
    x += int(_x[i]) * (2**i)

def popcount(n):
    c = 0
    while(n != 0):
        n = n%str(bin(n)[2:]).count('1')
        c += 1
    return c

for i in range(n):
    if ('{:' + str(n) + 'b}').format(x)[i] == '1':
        print(popcount(int(x - 2**(n-i-1))))
    else:
        print(popcount(int(x + 2**(n-i-1))))

Submission status: Time Limit Exceeded

Solution code:
class FuncMemo(dict):
    def __missing__(self, key):
        value = func(key)
        self[key] = value
        return value


class PopcountMemo(dict):
    def __missing__(self, key):
        value = popcount(key)
        self[key] = value
        return value


popcount_memo = PopcountMemo()
func_memo = FuncMemo()


def popcount(x): return bin(x).count('1')


def func(x):
    count = 0
    while x > 0:
        count += 1
        x %= popcount_memo[x]
    return count


def main():
    digits = int(input())
    binary_num = '0b' + input()
    int_num = int(binary_num, 0)
    for shift in range(digits - 1, -1, -1):
        num_tmp = int_num ^ (1 << shift)
        print(func(num_tmp))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy
N = int(input())
line = input()
initCnt = line.count('1')
for i in range(N):
    cnt = initCnt
    tmps = line
    tmp = ''
    if tmps[i] == '0':
        if i == 0:
            tmp = '1' + tmps[1:]
        elif i == N - 1:
            tmp = tmps[:-2] + '1'
        else:
            tmp = tmps[:i] + '1' + tmps[i+1:]
        cnt += 1
    elif tmps[i] == '1':
        if i == 0:
            tmp = '0' + tmps[1:]
        elif i == N - 1:
            tmp = tmps[:-2] + '0'
        else:
            tmp = tmps[:i] + '0' + tmps[i+1:]
        cnt -= 1
    else:
        print("error: tmp includes except 0 or 1")
        exit()
    if cnt == 0:
        print(0)
        continue
    num2 = int(tmp)
    num10 = int(str(num2), 2)
    devide = num10 % cnt
    devideCnt = 1
    while devide != 0:
        num10 = devide
        num2 = bin(num10)
        cnt = str(num2).count('1')
        devide = num10 % cnt
        devideCnt += 1
    print(devideCnt)

Submission status: Time Limit Exceeded

Solution code:
def divbin(s,res):
  if int(s,2)==0:
    v=res
    return v
  # ss=int(s)
  val=int(s,2)
  count=bin(val).count("1")
  val%=count
  # t_str=bin(str(count))
  t_str=bin(val)
  t_str=t_str.replace("0b","")
  res+=1
  return divbin(t_str,res)

from copy import deepcopy
n=int(input())
x=input()

# c=str(bin(n))
# c=c.replace("0b","")
s=x
p=int(x)
cnt=bin(p).count("1")
x=list(x)
# print(cnt)
for i in range(len(x)):
  tmp=cnt
  ts=""
  if x[i]=="1":
    cnt-=1
    if i==0:
      ts="0"+s[i+1:]
    elif 1<=i<len(x)-1:
      ts=s[:i]+"0"+s[i+1:]
    elif i==len(x)-1:
      ts=s[:i]+"0"
  else:
    cnt+=1
    if i==0:
      ts="1"+s[i+1:]
    elif 1<=i<len(x)-1:
      ts=s[:i]+"1"+s[i+1:]
    elif i==len(x)-1:
      ts=s[:i]+"1"
  # ans=0
  # global ans
  ans=0
  ans=divbin(ts,ans)
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    x = input()
    
    val = 0
    rui = 1
    mod = 0
    
    nagasa = 2*10**5+1
    #nagasa = 5
    d_li = [0]*(nagasa)
    
    for i in range(1,nagasa):
        t_v = i
        t_m = bin(t_v).count("1")
        ans = 0
        while t_v != 0:
            if d_li[t_v] != 0:
                ans += d_li[t_v]
                break
            ans += 1
            t_v %= t_m
            #t_m = bin(t_v).count("1")
        d_li[i] = ans
    
    #print(d_li)
    #exit()
    """
    for i in range(n):
        val += int(x[n-1-i])*rui
        rui *= 2
    """
    val = int(x, 2)
    #print(val)
    #exit()
    
    mod = bin(val).count("1")
    
    rui = pow(2,(n-1))
        
    for i in range(n):
        t_v = val
        t_m = mod
        if int(x[i]) == 1:
            t_v -= rui
            t_m -= 1
        else:
            t_v += rui
            t_m += 1
        rui //= 2
        ans = 0
        #while t_v != 0:
        if t_v != 0:
            t_v %= t_m
            ans += 1
        
        ans += d_li[t_v]
        #t_m = bin(t_v).count("1")
        #ans_li.append(ans)
        print(ans)
        #print(ans_li)
        
if __name__ == '__main__':
    main()
"""
#print(ans_li)
for i in range(n):
    print(ans_li[n-1-i])
"""

Submission status: Time Limit Exceeded

Solution code:
import copy
n=int(input())
x=list(input())
b=[]
for i in range(2**18):
  b.append(format(i,'0'+str(18)+'b'))
  if i>n+1:
    break
ct=[0]*(n+1)
for i in range(1,n):
  ct1=0
  for j in range(len(b[i])):
    if b[i][j]=='1':
      ct1+=1
  ct[i]=i%ct1

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

moda=[1]
modb=[1]
modc=[1]
for i in range(n-1):
  if CT>=2:
    moda.append(moda[-1]*2%(CT-1))
  if CT>=1:
    modb.append(modb[-1]*2%CT)
  modc.append(modc[-1]*2%(CT+1))


x.reverse()
za=0
zb=0
zc=0
for i in range(n):
  if x[i]=='1':
    if CT>=2:
      za+=moda[i]
      za%=(CT-1)
    if CT>=1:
      zb+=modb[i]
      zb%=CT
    zc+=modc[i]
    zc%=(CT+1)
x.reverse()
moda.reverse()
modc.reverse()

for i in range(n):
  y=copy.copy(x)
  y2=y[i]
  y[i]=str(1-int(y[i]))
  ct1=0
  for j in range(n):
    if y[j]=='1':
      ct1+=1
  if ct1==0:
    print(0)
  else:
    if y2=='1':
      z=za
      z-=moda[i]
      z%=ct1
    else:
      z=zc
      z+=modc[i]
      z%=ct1
    
    ans=1
    while z!=0:
      z=ct[z]
      ans+=1
    print(ans)

Submission status: Time Limit Exceeded

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

#N = 23
#X = '00110111001011011001110'

mem_func = [-1 for i in range(2**N)]

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

def func(n, l):
    if mem_func[n] != -1:
        return mem_func[n] + l
    if n == 0: return l
    n = n % popcount(n)
    return func(n, l+1)

list_X = list(X)
for i in range(N):
    x = copy.copy(list_X)
    if x[i] == '0':
        x[i] = '1'
    else:
        x[i] = '0'
    z = int(''.join(x), 2)
    mem_func[z] = func(z, 0)
    print(mem_func[z])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = [int(i) for i in input()]

ans = [0] * n
for i in range(n):
    x_tmp = x[:]
    x_tmp[i] = abs(x_tmp[i] - 1)
    y = "".join([str(val) for val in x_tmp])
    y = int(y, 2)
    while y > 0:
        y = bin(y)[2:]
        one_num = y.count("1")
        y = int(y, 2) % one_num
        y = bin(y)[2:]
        y = int(y, 2)
        ans[i] += 1

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
def inv(X, i):
    Z = X.copy()
    Z[i] = 1 - Z[i]
    return int('0b' + ''.join(map(str, Z)), 0)

def ppc(x):
    return bin(x).count('1')

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

for i in range(N):
    p = inv(X, i)
    counter = 0

    while True:
        if p == 0: break
        p = p % ppc(p)
        counter += 1

    print(counter)

Submission status: Time Limit Exceeded

Solution code:
n=(int)(input())
x=(input())
kazu = x.count('1')
a=(int)(x, 2)

for i in range(n):
  kazut = kazu
  if x[i] == '0':
    b=a+(2**(n-1-i))
    kazut += 1
  else:
    b=a-(2**(n-1-i))
    kazut -= 1
  ans = 0
  while(b != 0):
    #print(b)
    b = b % kazut
    kazut = (bin)(b).count('1')
    ans += 1
  print(ans)

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-1, -1, -1):
    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)
    pr = num
    road = []
    while True:
        if num == 0:
            break
        if ans[num] > 0:
            for r in road: ans[r] += ans[num]
            break
        road += [num]
        num = (num%pc)
        pc = popcount(num)
        for r in road: ans[r] += 1

for i in range(n):
    if x[i] == '0':
        s = x[:i] + '1' + x[i+1:]
    else:
        s = x[:i] + '0' + x[i+1:]
    print(ans[int(s, 2)])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def main():
    def f(n):
        if n == 0:
            return 0
        if d[n] != 0:
            return d[n]
        d[n] = f(n % sum(list(map(int, bin(n)[2:])))) + 1
    def rev(i):
        nonlocal c, X, m
        if X[i] == '0':
            c += 1
            m += 1 << (n - i - 1)
        else:
            c -= 1
            m -= 1 << (n - i - 1)
    def res(i):
        nonlocal c, X, m
        if X[i] == '0':
            c -= 1
            m -= 1 << (n - i - 1)
        else:
            c += 1
            m += 1 << (n - i - 1)

    n = int(input())
    X = list(input())
    d = defaultdict(int)
    d[0] = 0
    printl = lambda x, y: print(d[x % y] + 1 if x != 0 else 0)
    for i in range(1, n):
        f(i)
    c = sum(list(map(int, X)))
    m = int(''.join(X), 2)
    for i in range(n):
        rev(i)
        printl(m, c)
        res(i)





if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
x=input()
num=0
n=0
ans=[]
def twice(a):
    num=a
    b=0
    while a>0:
        b+=a%2
        a=a//2
    num=num%b
    return num
for i in range(N):
    if x[i]=="1":
        n+=1
        num+=2**(N-1-i)*int(x[i])
for i in range(N):
    Ans=0
    if x[i]=="0":
        Num=1+n
        A=2**(N-i-1)+num
        if Num==0:
            Ans=0
        else:
            a=A%Num
            Ans+=1
            while a>0:
                a=twice(a)
                Ans+=1
    else:
        Num=n-1
        A=num-2**(N-i-1)
        if Num==0:
            Ans=0
        else:
            a=A%Num
            Ans+=1
            while a>0:
                a=twice(a)
                Ans+=1
    ans.append(Ans)
for i in range(N):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
n,x=int(input()),input()
o=x.count("1")
l={}
a=int(x,2)
l[0]=0
for i in range(1,o+1):
    t=i
    t%=bin(t).count("1")
    l[i]=l[t]+1

c=pow(2,n-1)
for b in x:
    if b=="1":
        k=a-c
        gg=o-1
    else:
        k=a+c
        gg=o+1
    if k:
        k%=gg
        print(1+l[k])
    else:print(0)
    c//=2

Submission status: Time Limit Exceeded

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


N = int(input())

AAA = [0]
for i in range(1, 2**N):
    AAA.append(AAA[i % popcount(i)] + 1)

X = int(input(), 2)

for i in range(N):
    Xi = X ^ (1 << (N-i-1))
    print(AAA[Xi])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = list(str(input()))
popcount = X.count("1")

for n in range(1,N+1):
    temp = X[n-1]
    if X[n-1] == "0":
        X[n-1] = "1"
        pop = popcount + 1
    else:
        X[n-1] = "0"
        pop = popcount - 1
    X_int = int("".join(X),2)
    # print(X)
    X[n-1] = temp
    # print(X_int)
    # print(pop)
    count = 0
    while X_int != 0:
        # print(X_int,pop)
        X_int = X_int % pop
        temp_list = list(str(bin(X_int)))
        pop = temp_list.count("1")
        count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    sys.setrecursionlimit(200000)
    N = int(input())
    Y = input()
    X = int(Y,2)
    memo = {}
    Ycnt = Y.count("1")
    memo2 = {}

    def f(n,cnt):
        if n == 0:
            return 0
        if n not in memo:
            d = cnt
            nx = n%d
            if nx not in memo2:
                binNx = bin(nx)
                nxCnt = binNx.count("1")
                for i in range(len(Y)-len(binNx)):
                    tmp = nx
                    tmp <<= i
                    memo2[tmp] = nxCnt
            else:
                nxCnt = memo2[nx]
            memo[n] = f(nx,nxCnt)+1
        return memo[n]

    for i in range(N):
        if Y[i] == "1":
            cnt = Ycnt - 1
        else:
            cnt = Ycnt + 1
        a = N-i
        tmp = pow(2,a-1)
        n = X^tmp
        print(f(n,cnt))
main()

Submission status: Time Limit Exceeded

Solution code:
# # by Quarz
# # generator
#
# import random
#
# ri = random.randint
#
#
# def randomArray(x, y, n):
#     ret = []
#     for i in range(n):
#         ret.append(ri(x, y))
#     return ret
#
#
# def pr(a):
#     file.write(str(a).replace(" ", "").replace("\'", "\"") + '\n')
#
#
# def randomDag(n, m):
#     permutation = [i for i in range(n)]
#     random.shuffle(permutation)
#
#     added_edges = set()
#     # indeg = [0 for _ in range(n)]
#     for i in range(n-1):
#         # print(m // (n-1))
#         rem = ri(1, max(1, min(n-i-1, m // (n-1))))
#         while rem != 0:
#             j = ri(i+1, n-1)
#             u = permutation[i]
#             v = permutation[j]
#             if (u, v) in added_edges: continue
#             # indeg[v] += 1
#             added_edges.add((u, v))
#             rem -= 1
#
#
#     # print(indeg)
#     # print([min(1, indeg[i]) ^ 1 for i in range(n)])
#     # cnt = sum([min(1, indeg[i]) ^ 1 for i in range(n)])
#     # print(cnt)
#
#     # add remaining edges
#     loop = 0
#     while len(added_edges) < m and loop < 10**3:
#         loop += 1
#         u = ri(0, n-2)
#         v = ri(u+1, n-1)
#         u = permutation[u]
#         v = permutation[v]
#         # if indeg[v] == 0: continue
#         if (u, v) in added_edges: continue
#         added_edges.add((u, v))
#         loop = 0
#
#     return [[x[0], x[1]] for x in added_edges]
#
#     #
#     # indeg = random.sample(permutation[1:n-1], ri(0, n-2))
#     # indeg.append(permutation[0])
#     #
#     #
#     # # make it connected
#     # for i in range(1, n):
#     #     u = permutation[ri(0, i-1)]
#     #     v = permutation[i]
#     #     # edges.append((u, v))
#     #     added_edges.add((u, v))
#     #
#     #
#
#
#
# with open('test2.txt', 'w') as file:
#     for i in range(20):
#         n = ri(2, 10)
#         m = ri(n-1, (n * (n-1)) // 2)
#         pr(n)
#         pr(str(randomDag(n, m)).replace(' ', ''))
#
#     for i in range(20):
#         n = ri(11, 50)
#         m = min(500, ri(n-1, (n * (n-1)) // 2))
#         pr(n)
#         pr(str(randomDag(n, m)).replace(' ', ''))
#
#     for i in range(10):
#         n = ri(50, 500)
#         m = min(1000, ri(n-1, (n * (n-1)) // 2))
#         pr(n)
#         pr(str(randomDag(n, m)).replace(' ', ''))
#     for i in range(10):
#         n = ri(500, 5000)
#         m = min(10**4, ri(n-1, (n * (n-1)) // 2))
#         pr(n)
#         pr(str(randomDag(n, m)).replace(' ', ''))
#     for i in range(2):
#         n = ri(5000, 10**4)
#         m = min(ri(2, 3) * n, ri(n-1, (n * (n-1)) // 2))
#         pr(n)
#         pr(str(randomDag(n, m)).replace(' ', ''))
#     for i in range(2):
#         n = ri(10**4, 10**4)
#         m = min(min(10**5, 2 * n), ri(n-1, (n * (n-1)) // 2))
#         pr(n)
#         pr(str(randomDag(n, m)).replace(' ', ''))
#     for i in range(1):
#         n = ri(10**5, 10**5)
#         m = min(10**5, ri(n-1, (n * (n-1)) // 2))
#         pr(n)
#         pr(str(randomDag(n, m)).replace(' ', ''))


import sys

input = sys.stdin.readline

n = int(input())
y = str(input())
ones = 0
for i in y:
    if i == '1': ones += 1
x = int(y, 2)

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

out = []
rem1 = -1
rem2 = -1
if ones > 1:
    rem1 = x % (ones - 1)
if ones < n:
    rem2 = x % (ones + 1)

for i in range(n):
    tmp = (1 << i) * -1
    o = ones - 1
    if y[n - i - 1] == '0':
        tmp = 1 << i
        o = ones + 1

    # tmp = tmp + x
    if o == 0:
        out.append(0)
        continue
    if o == 1:
        out.append(1)
        continue

    if o > ones:
        tmp = (rem2 % o + tmp % o) % o
    else:
        tmp = (rem1 % o + tmp % o) % o

    cnt = 1
    while tmp > 0:
        tmp %= get(tmp)
        cnt += 1

    out.append(cnt)

for i in range(n):
    print(out[n-i-1])

Submission status: Time Limit Exceeded

Solution code:
def f(n, c_one):                                       
    cnt = 0                                            
    while n:                                           
        n = n % c_one                                  
        cnt += 1                                       
        # c_one = bin(n).count('1') # ここがボトルネック        
        c_one = 0                                      
        tmp = n                                        
        while tmp:                                     
            if tmp % 2 == 1:                           
                c_one += 1                             
            tmp //= 2                                  
    return cnt                                         
                                                       
                                                       
N = int(input())                                       
binary_str = str(input())                              
# N = 2 * 10 ** 5                                      
# binary_str = '1' * (2 * 10 ** 5)                     
binary_num = int(binary_str, 2)                        
cnt_one = binary_str.count('1')                        
for i in range(N):                                     
    idx = (N - 1 - i)                                  
    if binary_str[i] == '1':                           
        print(f(binary_num - 2 ** idx, cnt_one - 1))   
    else:                                              
        print(f(binary_num + 2 ** idx, cnt_one + 1))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

def hanten(num):
  if(N==1):
    if(X=="0"):
      return '1'
    else:
      return '0'
  else:
    if(num==0):
      if(X[num]=="0"):
        s = '1' + X[i+1:]
      else:
        s = '0' + X[i+1:]
      return s

    elif(num==N-1):
      if(X[num]=="0"):
        s = X[:num] + '1'
      else:
        s = X[:num] + '0'
      return s
    else:
      if(X[num]=="0"):
        s = X[:num] + '1' + X[num+1:]
      else:
        s = X[:num] + '0' + X[num+1:]
      return s


def scount(num2):
#  clist=list(num2)
  counter=Counter(num2)
  return counter["1"]

def popcount(num3,cnt):
  s=int(num3,2)%cnt
  return bin(s)

i=0

while(i<N):
  res=0
  number=X
  number=hanten(i)
#  print("hantengo:"+number)
  while(int(number,2)!=0):
    r1=scount(number)
    r2=popcount(number,r1)
    number=r2
    res+=1
#    print("next"+number)
  print(res)
  i+=1

Submission status: Time Limit Exceeded

Solution code:
def m():
    N = int(input())
    X = input()
    R = list(reversed(X))

    memo = [0] * (N+2)
    for i in range(1, N+2):
        p = 0
        k = i
        while k != 0:
            if k % 2 == 1:
                p+=1
            k //= 2
        memo[i] = p

    def f(n):
        r = 0
        while n != 0:
            n = n % memo[n]
            r += 1
        return r
    memo2 = [0] * (N+2)
    for i in range(1, N+2):
        memo2[i] = f(i)


    total = 0
    for i in range(N):
        total += int(R[i]) * pow(2, i)

    base = X.count('1')
    for i in range(N):
        ans = 0
        if X[i] == '1':
            tmp = total - pow(2, N - 1 - i)
            if (base-1) == 0:
                print(0)
                continue
            tmp %= (base - 1)
            ans = memo2[tmp] + 1
        else:
            tmp = total + pow(2, N - 1 - i)
            tmp %= (base + 1)
            ans = memo2[tmp] + 1
        print(ans)


m()

Submission status: Time Limit Exceeded

Solution code:
def popcnt1(n):
    return bin(n).count("1")

n=int(input())
x=input()
q=int(x, 2)
p=popcnt1(q)


for i in range(n):
    if x[i]=="1":
    
        q=int(x, 2)-2**(n-i-1)
        p=popcnt1(q)

    else:
        q=int(x, 2)+2**(n-i-1)
        p=popcnt1(q)
    s=0
    while q>0:
        if x[i]=="1":

            q%=p
            p=popcnt1(q)
        else:
            q%=p
            p=popcnt1(q)
        s+=1
    print(s)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[4]:


import copy


# In[139]:


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


# In[140]:


def func(N,X):
    for i in range(N):
        xi = copy.deepcopy(X)
        xi[i] = str(1-int(X[i]))
        popcount = xi.count("1")
        num = int("".join(xi),2)
        if num == 0:
            ans = 0
        else:
            if num%popcount == 1:
                ans = 2
            elif num%popcount == 2:
                ans = 2
            elif num%popcount == 3:
                ans = 3
            else:
                ans = 1
                while num%popcount != 0:
                    num = num%popcount
                    popcount = format(num,"b").count("1")
                    ans += 1
        print(ans)


# In[141]:


func(N,X)