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: Runtime Error

Solution code:
def myf(s):
    for i in range(1, 10):
        s = bin(int(s, 0) % s.count('1'))
        if int(s, 0) == 0:
            return i

n = int(input())
x = '0b' + input()
lst = ['1', '0']
for j in range(n):
  z = x[:j + 2] + lst[int(x[j + 2])] + x[j + 3:]
  print(myf(z))

Submission status: Runtime Error

Solution code:
import copy

n = int(input())
x = [int(s) for s in list(input())]
ans = [0] * n

for i in range(n):
    damy = copy.deepcopy(x)
    damy[i] = (damy[i] + 1) % 2
    num10 = 1
    while num10 > 0:
        pop = 0
        num10 = 0
        for j in range(len(damy)):
            num10 += 2 ** (n - j - 1) * damy[j]
            pop += damy[j]
        num10 = num10 % pop
        damy = [int(s) for s in str(bin(num10)).strip("0b")]
        ans[i] += 1
    print(ans[i])

Submission status: Runtime Error

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)
a = [-1]*(y+1)
a[0] = 0
a[1] = 1

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)
    reg = y_tmp
    while y_tmp != 0:
        ans += 1
        y_tmp = y_tmp % c_tmp
        c_tmp = format(y_tmp,'b').count('1')
        try:
            if 0 < y_tmp < n and a[y_tmp] != -1:
                ans += a[y_tmp]
                break
        except:
            continue
    print(ans)
    try:
        a[reg] = ans
    except:
        continue

Submission status: Runtime Error

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

def resCount(n):
    tmp = bin(n).count('1')
    if tmp == 1:
        return 1
    else:
        return 1 + resCount(n % tmp)

for i in range(N):
    res, n = 1, int(X, 2) ^ (1<<(N-i-1))
    print(resCount(n))

Submission status: Runtime Error

Solution code:
def fast_powmod(n, m):
    pow2 = 2
    result = 1
    while n > 0:
        if n % 2 == 1:
            result = (result * pow2) % m
        pow2 = (pow2 * pow2) % m
        n >>= 1

    return result

def popcnt3(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

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

res = dict()
res[1] = 1
res[2] = 1
for i in range(3, 2 * 10**5 + 1):
    val = i % popcnt3(i)
    if val == 0:
        res[i] = 1
    else:
        res[i] = res[val] + 1

count = 0
for i in x:
    if i == "1":
        count += 1

x = x[::-1]
small = 0
big = 0
for i in range(len(x)):
    if x[i] == "1":
        small += fast_powmod(i, count - 1)
        big += fast_powmod(i, count + 1)

small %= count - 1
big %= count + 1

anse = []
for i in range(len(x)):
    if x[i] == "1":
        done = False
        ans = 0
        cur = small - fast_powmod(i, count - 1)
        cur %= count - 1
        if cur == 0:
            anse.append(1)
        else:
            anse.append(res[cur] + 1)
    else:
        done = False
        ans = 0
        cur = big + fast_powmod(i, count + 1)
        cur %= count + 1
        if cur == 0:
            anse.append(1)
        else:
            anse.append(res[cur] + 1)


for i in anse[::-1]:
    print(i)
                
        
        
# print(small, big)

Submission status: Runtime Error

Solution code:
import collections

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

x_list = list(x)

num_dict = dict(collections.Counter(x_list))

num_of_1 = num_dict["1"]

first_temp = int("".join(x_list), 2)

for i in range(n):
    temp_num_of_1 = num_of_1 + 1 if x_list[i] == "0" else num_of_1 - 1

    ans = 0

    if temp_num_of_1 > 0:
        a = first_temp + 2 ** (n - i - 1) if x_list[i] == "0" else first_temp - 2 ** (n - i - 1)

        a = a % temp_num_of_1

        temp = list(bin(a)[2:])

        ans += 1
    
        while temp.count("1") != 0:
            a = int("".join(temp), 2)

            a = a % temp.count("1")

            temp = list(bin(a)[2:])

            ans += 1

    print(ans)

Submission status: Runtime Error

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

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

p = [-1 for _ in range(2*(10**7)+1)]
cnt = x.count('1')

def calc(a):
  #print('a=',a)
  if 0 <= a <= 2*(10**7) and  p[a] != -1:
    return p[a]
  else:
    if a == 0:
      ret = 0
    else:
      b = bin(a).count('1')
      ret = 1+calc(a%b)
    if 0 <= a <= 2*(10**7):
      p[a] = ret
    return ret

x0 = int(x,2)%(cnt-1)
x1 = int(x,2)%(cnt+1)
xx0 = [1]
for i in range(n+1):
  xx0.append((xx0[-1]*2)%(cnt-1))
xx1 = [1]
for i in range(n+1):
  xx1.append((xx1[-1]*2)%(cnt+1))

y = list(x)  
for i in range(n):
  if y[i] == '0':
    xx = xx1[n-i-1]
    print(calc((x1+xx)%(cnt+1))+1)
  else:
    xx = xx0[n-i-1]
    print(calc((x0-xx)%(cnt-1))+1)

Submission status: Runtime Error

Solution code:
import sys

def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))
def RN(N): return [input().strip() for i in range(N)]


def main():
    N = II()
    Xstr = str(input())
    X = int(Xstr)


    for i in range(N):
        Xi = Xstr
        if Xstr[i] == "0":
            Xi = Xi[:i] + '1' + Xi[i+1:]
        elif Xstr[i] == "1":
            Xi = Xi[:i] + '0' + Xi[i+1:]
        
        n = 0
        for j in range(N):
            if Xi[j] == "1":
                n += 2**(N-1-j)
        #print(Xi)    
        #print(n)

        n10 = n
        n2 = bin(n)
        ans = 0
        while True:
            n2str = str(n2)
            kazu1 = n2str.count("1")
            n10 = n10 % kazu1
            ans += 1
            if n10 == 0:
                break
            n2 = bin(n10)
        print(ans)




if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(1000000000)
import copy
import numpy as np
MOD = 10 ** 9 + 7


def main():
    def popcount(n: int) -> int:
        return list(f'{n:b}').count('1')

    n = int(input())
    X = list(input())

    ppcs = np.full(int('1'*n, 2) + 1, -1)
    ppcs[0:4] = [0, 1, 1, 2]

    for i in range(n):
        x = copy.deepcopy(X)
        if x[i] == '1':
            x[i] = '0'
        else:
            x[i] = '1'

        cnt = 0
        val = int("".join(x), 2)
        defval = val
        while True:
            if ppcs[val] >= 0:
                cnt += ppcs[val]
                ppcs[defval] = cnt
                break
            else:
                val = val % popcount(val)
                cnt += 1
        print(cnt)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# coding: utf-8

import sys

sys.setrecursionlimit(10000)


def bi(x, n_digit):
    output = ""
    for i in range(n_digit-1, -1, -1):
        if x >= 2**i:
            x -= 2**i
            output += "1"
        else:
            output += "0"
    return output


def popcount(bi_n):
    output = 0
    for c in bi_n:
        if c == "1":
            output += 1
    return output


def main():
    N = int(input())
    bi_X = input()

    fs = [None] * 25

    def rec(x):
        pop_x = popcount(bi(x, 25))
        r = x % pop_x
        if r == 0:
            return 1
        elif fs[r] is not None:
            return 1 + fs[r]
        else:
            return 1 + rec(r)

    for i in range(1, 25):
        fs[i] = rec(i)
    fs[0] = 0

    pop_X = popcount(bi_X)
    qp = pop_X+1
    qm = pop_X-1

    bi_qp = [None] * N
    bi_qm = [None] * N
    bi_qp[0] = 1 % qp
    bi_qm[0] = 1 % qm
    bi_qp[1] = 2 % qp
    bi_qm[1] = 2 % qm
    for i in range(2, N):
        bi_qp[i] = ((bi_qp[1])*(bi_qp[i-1])) % qp
        bi_qm[i] = ((bi_qm[1])*(bi_qm[i-1])) % qm

    rp = 0
    rm = 0
    for i in range(N):
        p = N-1-i
        coo = int(bi_X[i])
        rp = (rp + (((coo % qp) * bi_qp[p]) % qp)) % qp
        rm = (rm + (((coo % qm) * bi_qm[p]) % qm)) % qm

    for i in range(N):
        if bi_X[i] == "0":
            ri = (rp + bi_qp[N-1-i]) % qp
            if ri < 25:
                print(1 + fs[ri])
            else:
                pop_ri = popcount(bi(ri, 25))
                print(2 + fs[ri % pop_ri])
        else:
            ri = (rm - bi_qm[N-1-i]) % qm
            if ri < 25:
                print(1 + fs[ri])
            else:
                pop_ri = popcount(bi(ri, 25))
                print(2 + fs[ri % pop_ri])



main()
# print(main())

Submission status: Runtime Error

Solution code:

def popcount(n):
    s = bin(n)
    return s.count("1")
def func(org_n,n,depth):
    #print(n)
    if n == 0:
        return depth
    elif func_dp[n]!=0 :
        func_dp[org_n] = func_dp[n]+depth
        return func_dp[org_n]
    else:
        return func(org_n,n%popcount(n),depth+1)
def reverse(bin_n,i):
    i_bit_rev = bin(1<<i)
    return bin_n^int(i_bit_rev,2)
N = int(input())
X=int(input(),2)
func_dp = [0]*(2**(N+2))
for i in range(N):
    #print("X={}".format(X))
    #print("N-i-1".format(N-i-1))
    ans = func(X,reverse(X,N-i-1),0)
    print(ans)

Submission status: Runtime Error

Solution code:
keta = int(input())
code = int(input())
tikan = 0
answer = 1
popcount= 0

for i in range(keta):
    if math.floor(code/10**(keta-i-1))%10 ==  1:
        tikan = code - 10**(keta-i-1)
    else:
        tikan = code + 10**(keta-i-1)
    popcount = str(tikan).count('1')
    
    while int(str(tikan),2)%popcount != 0:
        popcount = str(tikan).count('1')
        tikan = int(str(tikan),2)%popcount
        if int(str(tikan),2)%popcount == 0:
            break
        answer += 1
    print(answer)
    tikan = 0
    answer = 1

Submission status: Runtime Error

Solution code:
n=int(input())
x=input()
d=[0]*(2**10+1)
for j in range(2**10+1):
  bin_num=j
  iti2=0
  count=0
  X=bin(bin_num)
  for i in X:
    if i=="1":
      iti2+=1
  while bin_num!=0:
    count+=1
    if iti2==0:
      break
    bin_num=bin_num%iti2
    bin_num2=bin(bin_num)
    iti2=0
    for i in bin_num2:
      if i=="1":
        iti2+=1
  d[j]=count
  
iti=0
zero=0
for i in x:
  if i=="1":
    iti+=1
zero=n-iti
for i in range(n):
  ans=0
  if x[i]=="1":
    X="0b"+x[:i]+"0"+x[i+1:]
    iti2=iti-1
  else:
    x[i]=="1"
    X="0b"+x[:i]+"1"+x[i+1:]
    iti2=iti+1
  bin_num = int(X, 0)
  if iti2!=0:
    bin_num=bin_num%iti2
    print(d[bin_num]+1)
  else:
    print(0)

Submission status: Runtime Error

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

n= int(input())
a=list(input())

v=a.count('1')

ans=[0]*n
A=[0]*n
# n以下の残り回数を記録
for i in range(v+1):
    x=i
    cnt=0
    while x>0:
        cnt+=1
        r = 0
        for j in range(19):
            if (x>>j)&1:
                r+=1
            if x>>j==0:
                break
        x=x%r
    ans[i]=cnt

# 各桁をv＋１で割ったあまり
q = [0]*n
# 各桁をv-1で割ったあまり
r = [0]*n
for i in range(n):
    if a[i]=='1':
        if v!=0:
            q[i] = pow(2, n-i-1) % (v + 1)
        if v!=1:
            r[i] += pow(2, n-i-1) % (v - 1)
qq=sum(q)%(v+1)
rr=sum(r)%(v-1)

for i in range(n):
    if a[i]=='1':
        if v!=1:
            z = rr - pow(2,n-i-1)%(v-1)
            cnt = z % (v - 1)
            A[i] = 1 + ans[cnt]
    else:
        z=qq+pow(2,n-i-1)%(v+1)
        cnt=z%(v+1)
        A[i]=1+ans[cnt]

for i in A:
    print(i)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N = int(input())
    X = input()
    X = int('0b'+X,0)

    memo = [-1] * (2**(N+1))

    def f(X):
        if memo[X]!=-1:
            return memo[X]
        x = X
        count = 0
        while x>=1:
            if x%2==1:
                count += 1
            x//=2
        if X%count == 0:
            memo[X] = 1
            return memo[X]
        else:
            memo[X] = f(X%count)+1
            return memo[X]

    for i in range(N-1,-1,-1):
        x = X^(1<<i)
        if x==0:
            print(0)
        else:
            print(f(x))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

s = int(tmp, 2)
nn = sum([int(a) for a in tmp if a == '1'])
POPCOUNT_TABLE16 = [0] * 2**16
for index in range(len(POPCOUNT_TABLE16)):
    POPCOUNT_TABLE16[index] = (index & 1) + POPCOUNT_TABLE16[index >> 1]


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

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

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

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


def popcnt5(v):
    return (POPCOUNT_TABLE16[v & 0xffff] +
            POPCOUNT_TABLE16[(v >> 16) & 0xffff] +
            POPCOUNT_TABLE16[(v >> 32) & 0xffff] +
            POPCOUNT_TABLE16[(v >> 48)])


def division_binary_shift(a, b):
    """
    a // b

    :param a: dividend
    :param b: divisor
    :return: quotient
    """
    if a < b:
        return 0
    if b == 0:
        raise ZeroDivisionError

    q = 0
    sq = 1
    ori_b = b
    while a >= b:
        b <<= 1
        if a >= b:
            sq <<= 1
        else:
            b >>= 1
            a -= b
            q += sq
            sq = 1
            b = ori_b

    return q


def division_binary_shift_m(a, b, m):
    """
    :param a: dividend
    :param b: divisor
    :param m: maximum bit capacity
    :return: quotient
    """
    if a < b:
        return 0
    if b == 0:
        raise ZeroDivisionError

    q = 0
    sb = b << m
    rem = a  # remainder (init is dividend)
    while rem >= b:
        while sb > rem:
            sb = sb >> 1
            m = m - 1

        q = q + (1 << m)
        rem = rem - sb

    return q


for i in range(n):
    ss = s ^ (1 << (n-i-1))
    c = 0
    t = popcnt5(ss)
    while ss != 0:
        ss -= t*division_binary_shift_m(ss, t, 64)
        t = popcnt5(ss)
        c += 1
    # print(ss, popcnt5(ss), c)
    print(c)

Submission status: Runtime Error

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

num = int(x, 2)
Cou = x.count('1')

for i in range(n):
  num_ = num
  Cou_ = Cou
  if  x[i] == '0':
    num_ += 2**(n-1-i)
    Cou_ += 1
  else:
    num_ -= 2**(n-1-i)
    Cou_ -= 1
  
  num_ = int(num_)
  ans = 0
  pop_n = 100
  while pop_n != 0:
    pop_n = num_%Cou_
    num_ = int(pop_n)
    Cou_ = bin(pop_n).count('1')
    ans += 1
    
  print(ans)

Submission status: Runtime Error

Solution code:
def main(N, X):
    lst = list(map(int, list(X)))
    num = lst.count(1)  # 初期状態で1を持つ数．

    def func(x):    # xは10進数
        lst = list(bin(x)[2:])
        amari =  x % lst.count('1')
        return amari

    d = {}
    for i in range(1, num + 2):
        d[i] = func(i)


    # 反転させるので num + 1 か， num - 1 で割る場合しか存在しない．
    plus = []   # num + 1 で各桁 (2 ** n) を割った値を保存
    minus = []  # num - 1 で各桁 (2 ** n) を割った値を保存

    p = 1
    m = 1
    for n in range(N):
        p %= (num + 1)
        plus.append(p)
        m %= (num - 1)
        minus.append(m)
        p *= 2
        m *= 2

    o = int(X, 2)   # originalの 'o'
    amari_plus = o % (num + 1)
    amari_minus = o % (num - 1)

    for i in range(N):
        if lst[i] == 0:
            amari = (amari_plus + plus[N - i - 1]) % (num + 1)
        else:
            amari = (amari_minus + num - 1 - minus[N - i - 1]) % (num - 1)
        ans = 1
        while amari != 0:
            amari = d[amari]
            ans += 1
        print(ans)




if __name__ == '__main__':
    N = int(input())
    X = input()

    # N = 2 * 10 ** 5
    # import numpy as np
    # X = ''.join([str(int(round(i))) for i in np.random.rand(N)])

    # N = 3
    # X = '011'

    # import time
    # t1 = time.time()
    main(N, X)

Submission status: Runtime Error

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


def P(n):
    b = bin(n)
    l = len(b)
    r = 0
    for i in range(2, l):
        if b[i] == '1':
            r += 1
    return r


for i in range(n):
    c = x.copy()
    if c[i] == '0':
        c[i] = '1'
    else:
        c[i] = '0'
    u = int(''.join(c), 2)
    sum = 0
    for j in range(20000000000):
        u = u % P(u)
        sum += 1
        if u == 0:
            break
    print(sum)

Submission status: Runtime Error

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

cnt = X.count("1")
div = [0] * (cnt + 1)
for i in range(1, cnt + 1):
    for n in range(20):
        div[i] += i >> n & 1

memo = [-1] * (cnt + 1)
memo[0] = 0
for i in range(1, cnt + 1):
    memo[i] = memo[i % div[i]] + 1

res0 = 0
res1 = 0
for i in range(N):
    if X[i] == "1":
        res0 = (res0 + pow(2, N - i - 1, cnt + 1)) % (cnt + 1)
        res1 = (res1 + pow(2, N - i - 1, cnt - 1)) % (cnt - 1)

for i in range(N):
    if X[i] == "0":
        div = cnt + 1
        tmp = (res0 + pow(2, N - i - 1, div)) % div
    else:
        div = cnt - 1
        tmp = (res1 + div - pow(2, N - i - 1, div)) % div
    print(memo[tmp] + 1)

Submission status: Runtime Error

Solution code:
n=int(input())

x=input()

bin_1cnt = [0] * 200001

for i in range(1, 200001):
    i_bin = format(i, 'b')
    i_bin_1cnt = i_bin.count('1')
    bin_1cnt[i] = i_bin_1cnt

pc_dp = [0] * 200001

for i in range(1, 200001):
    i_init = copy.deepcopy(i)
    cnt_tmp = 1
    i = i % bin_1cnt[i]
    while i != 0 and pc_dp[i] == 0:
        cnt_tmp += 1
        i = i % bin_1cnt[i]
    if i ==0:
        pc_dp[i_init] = cnt_tmp
    elif pc_dp[i] != 0:
        pc_dp[i_init] = cnt_tmp + pc_dp[i]

x_10 = int(x, 2)

for i in range(0, n):
    if x[i]=='0':
        n_i = x_10 + 2**(n-i-1)
        print(pc_dp[n_i])
    if x[i]=='1':
        n_i = x_10 - 2**(n-i-1)
        print(pc_dp[n_i])

Submission status: Runtime Error

Solution code:
import math
# from collections import defaultdict
# import time
def steps(n,p):
  c = 0
  while n:
    c += 1
    n = n%p
    p = bin(n).count('1')
  return c

n = int(input())
x = input()
incs = [1]
decs = [1]
p = x.count('1')
for i in range(1,n):
  incs.append((incs[-1]*2)%(p+1))
  decs.append((decs[-1]*2)%(p-1))
num = int(x,2)
inc = num%(p+1)
dec = num%(p-1)
# start = time.time()
for i in range(n):
  cp = p
  if x[i] == '0':
    cp += 1
    new = (inc+incs[n-i-1])%cp
  else:
    cp -= 1
    new = (dec-decs[n-i-1])%cp
  ans = steps(new,cp)
  if ans==0:
    ans=1
  print(ans)
  # steps(new,cp)
# print(time.time()-start)

Submission status: Runtime Error

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

n = int(input())
xs = list(input())[::-1]

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

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

memo = {}
memo[0] = 1
def dfs(n, depth=0):
    if n in memo:
        return depth + memo[n] - 1
    else:
        ret = dfs(n%popcount(n), depth+1)
        memo[n] = ret
        return ret

ans = []
for i in range(n):
    ans.append(dfs(x^(1<<i)))
for a in ans[::-1]:
    print(a)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
import collections as cl


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    N = II()
    X = input()
    f_memo = [-1] * len(X)**2
    f_memo[0] = 0

    next_pop = [-1] * len(X)**2

    for i in range(1, N+1):
        if X[i-1] == '0':
            reversed_X = X[:i-1]+'1' + X[i:]
        else:
            reversed_X = X[:i-1]+'0' + X[i:]
        count = -1
        n = reversed_X
        while n != '0':
            counter = cl.Counter(n)
            count += 1
            num_1 = counter['1']
            if num_1 ==0:
                break
            n = bin(int(n, 2) % num_1)

        print(count)


        # oj t -c "pypy3 main.py"
        # acc s main.py -- --guess-python-interpreter pypy
main()

Submission status: Runtime Error

Solution code:
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

N,X = open(0).read().split()
N = int(N)
X = list(X)

for i in range(0, N):
    xs = X[:]
    xs[i] = "1" if xs[i] == "0" else "0"
    x = int("".join(xs), 2)
    ans = 0
    while x != 0:
        x = x % popcount(x)
        ans += 1
    print(ans)

Submission status: Runtime Error

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

Xs = []
for i in range(N):
    tmp = list(binary)
    if tmp[i] == '0':
        tmp[i] = '1'
    else:
        tmp[i] = '0'
    Xs.append(int('0b' + ''.join(tmp), 2))

for X in Xs:
    cur = X
    count = 0
    while True:
        cur = cur % bin(cur).count('1')
        count += 1
        if cur == 0:
            break
    print(count)

Submission status: Runtime Error

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)
a = [-1]*(y+1)
a[0] = 0
a[1] = 1

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)
    reg = y_tmp
    while y_tmp != 0:
        ans += 1
        y_tmp = y_tmp % c_tmp
        c_tmp = format(y_tmp,'b').count('1')
        if 0 < y_tmp < n and a[y_tmp] != -1:
            ans += a[y_tmp]
            break
    print(ans)
    try:
        a[reg] = ans
    except:
        continue

Submission status: Runtime Error

Solution code:
N=int(input())
X=input()
XX=0
for i in range(N):
    XX+=int(X[N-i-1])*2**i
#print(XX)

POPCOUNT_TABLE16 = [0] * 2**16
for index in range(len(POPCOUNT_TABLE16)):
    POPCOUNT_TABLE16[index] = (index & 1) + POPCOUNT_TABLE16[index >> 1]

def popcnt5(v):
    return (POPCOUNT_TABLE16[ v        & 0xffff] +
            POPCOUNT_TABLE16[(v >> 16) & 0xffff] +
            POPCOUNT_TABLE16[(v >> 32) & 0xffff] +
            POPCOUNT_TABLE16[(v >> 48)         ])

table=[0,1]+[-1 for i in range(219998)]
for i in range(2,220000):
    table[i]=table[i%popcnt5(i)]+1

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

#print(table[:21])

plus=0  #もとの数字に1のときのmodをしたやつ
minus=0

for i in range(N):
    plus+=int(X[i])*pow(2,N-1-i,moto-1)
    minus+=int(X[i])*pow(2,N-1-i,moto+1)
    plus%=(moto-1)
    minus%=(moto+1)

#print(moto,plus,minus)

for i in range(N):
    ans=0
    if X[i]=='1':
        ans=plus
        ans-=pow(2,N-1-i,moto-1)
        ans%=(moto-1)
    else:
        ans=minus
        ans+=pow(2,N-1-i,moto+1)
        ans%=(moto+1)
    print(table[ans]+1)

Submission status: Runtime Error

Solution code:
def pop_count(T):
    T = (T & 0x55555555) + ((T >> 1) & 0x55555555)
    T = (T & 0x33333333) + ((T >> 2) & 0x33333333)
    T = (T & 0x0F0F0F0F) + ((T >> 4) & 0x0F0F0F0F)
    T = (T & 0x00FF00FF) + ((T >> 8) & 0x00FF00FF)
    T = (T & 0x0000FFFF) + ((T >> 16) & 0x0000FFFF)
    return T


N = int(input())
X = input()
cnt = X.count("1")

if cnt == 0:
    for _ in range(N):
        print(1)
    exit()
if cnt == 1:
    if X[-1] == "0":
        res = 0
    else:
        res = 1
    for i, x in enumerate(X):
        if x == "1":
            print(0)
        else:
            print(res)
    exit()


res = [0]*21
for i in range(1, 21):
    tmp = 0
    x = i
    while x:
        cnt = pop_count(x)
        x %= cnt
        tmp += 1
    res[i] = tmp


cnt = X.count("1")
Xrev = X[::-1]
sum01 = 0
sum10 = 0
memo01 = [0] * N
memo10 = [0] * N

for i, x in enumerate(Xrev):
    val01 = pow(2, i, cnt + 1)
    val10 = pow(2, i, cnt - 1)
    if x == "1":
        sum01 += val01
        sum01 %= cnt + 1
        sum10 += val10
        sum10 %= cnt - 1
    memo01[i] = val01
    memo10[i] = val10
memo01.reverse()
memo10.reverse()

for i, x in enumerate(X):
    if x == "0":
        p = (sum01 + memo01[i]) % (cnt + 1)
        print(1 + res[p])
    else:
        p = (sum10 - memo10[i] + cnt - 1) % (cnt - 1)
        print(1 + res[p])

Submission status: Runtime Error

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

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

p = [-1 for _ in range(2*(10**7)+1)]
cnt = x.count('1')

def calc(a):
  #print('a=',a)
  if 0 <= a <= 2*(10**7) and  p[a] != -1:
    return p[a]
  else:
    if a == 0:
      ret = 0
    else:
      b = bin(a).count('1')
      ret = 1+calc(a%b)
    p[a] = ret
    return ret

x0 = int(x,2)%(cnt-1)
x1 = int(x,2)%(cnt+1)
xx0 = [1]
for i in range(n+1):
  xx0.append((xx0[-1]*2)%(cnt-1))
xx1 = [1]
for i in range(n+1):
  xx1.append((xx1[-1]*2)%(cnt+1))

y = list(x)  
for i in range(n):
  if y[i] == '0':
    xx = xx1[n-i-1]
    print(calc((x1+xx)%(cnt+1))+1)
  else:
    xx = xx0[n-i-1]
    print(calc((x0-xx)%(cnt-1))+1)

Submission status: Runtime Error

Solution code:
N = int(input())
two_num = list(map(int, list(input())))
# N = 3
# two_num = [0,1,1]
ans = [[0]*N]
import copy

for i in range(N):
    bin_list = copy.deepcopy(two_num)
    if bin_list[i] == 0:
        bin_list[i] = 1
    else:
        bin_list[i] = 0
    num=1
    ans = 0
    while num:
        ans+=1
        num = 0
        for i, j in enumerate(reversed(bin_list)):
            num += (2**i) * j
        count = bin_list.count(1)
        num = num % count
        bin_list = list(map(int, list(format(num, 'b'))))
    print(ans)

Submission status: Runtime Error

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

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

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

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

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


for n in range(N,0,-1):
    number = popcount(int(X))

    answer=0
    if X[n-1]=='0':
        a+=2**(n-1)
        b=0
        b+=a
        while b !=0:
            b=b%(number+1)
            answer+=1
            number=popcount(bin(b))
    else:
        a-=2**(n-1)
        b = 0
        b += a
        while b != 0:
            b = b % (number + 1)
            answer += 1
            number = popcount(bin(b))
    print(answer)

Submission status: Runtime Error

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


@lru_cache(maxsize=None)
def countbits(n):
    res = 0
    while n:
        res += n % 2
        n //= 2
    return res


n = inp()
x = str_inp()
dp = collections.defaultdict(lambda: -1)
dp[0] = 0
bits_amount = 0
ans = []
for i in range(n):
    bits_amount += int(x[i])
minus_val = 0
plus_val = 0
if bits_amount != 0:
    for i in range(n):
        if int(x[i]):
            minus_val += pow(2, n - i - 1, bits_amount - 1)
            minus_val %= (bits_amount - 1)
if bits_amount != n:
    for i in range(n):
        if int(x[i]):
            plus_val += pow(2, n - i - 1, bits_amount + 1) % (bits_amount + 1)
            plus_val %= (bits_amount + 1)
for i in range(n):
    if int(x[i]):  # 1->0
        now_val = (minus_val - pow(2, n - i - 1, bits_amount - 1)) % (bits_amount - 1)
    else:
        now_val = (plus_val + pow(2, n - i - 1, bits_amount + 1)) % (bits_amount + 1)
    path = [now_val]
    while True:
        if dp[now_val] != -1:
            break
        now_val = now_val % countbits(now_val)
        path.append(now_val)
    tmp = dp[now_val]
    for j in range(1, len(path)):
        tmp += 1
        dp[path[len(path) - j - 1]] = tmp
    ans.append(dp[path[0]])
for i in ans:
    print(i + 1)