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:
n=int(input())
m=input()
x=int(m,2)
li=list(m)
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
def check(a):
  co=1
  while a!=0:
    co+=1
    a%=popcount(a)
  return co
jpop=popcount(x)
jop=x%(jpop+1)
jom=x%(jpop-1)
jppp=jpop+1
jppm=jpop-1
for i in range(0,n):
  nijo=2**(n-i-1)
  if li[i]=="0":
    a=jop+nijo%jppp
    if a>=jppp:
      a-=jppp
  else:
    a=jom-nijo%jppm
    if a<0:
      a+=jppm
  if a==0:
    print(1)
    continue
  print(check(a))

Submission status: Runtime Error

Solution code:
n=int(input())

x=input()

import copy

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

NumberList = dict()

for i in range(N):
    if X[i] == '0':
        if i != 0:    
            tmp = X[:i] + '1' + X[i + 1:]
        else:
            tmp = '1' + X[i + 1:]
    else:
        if i != 0:    
            tmp = X[:i] + '0' + X[i + 1:]
        else:
            tmp = '0' + X[i + 1:]
    
    ten_m = int(tmp, 2)
    two_pop = bin(ten_m).count("1")
    
    ten_m_tmp = ten_m
    count = 0
    NumberList_tmp = []
    while ten_m != 0:
        if ten_m in NumberList:
            count += NumberList[ten_m]
            break
        ten_m = ten_m % two_pop
        two_pop = bin(ten_m).count("1")
        count += 1
        
        NumberList_tmp.append(ten_m)
    
    tmp = 1
    for i in NumberList_tmp.reverse:
        NumberList[i] = tmp
        tmp += 1
    #NumberList[ten_m_tmp] = count
    print(count)

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):
    tmp=1
    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)
    while True:
        if dp[now_val] != -1:
            break
        tmp+=1
        now_val = now_val % countbits(now_val)
    ans.append(tmp)
for i in ans:
    print(i + 1)

Submission status: Runtime Error

Solution code:
def getcount(x, count=1):
    num = str(bin(x)).count("1")
    if x % num == 0:
        return count
    else:
        return getcount(x % num, count + 1)


def bitchange(x, num):
    if x[num] == "1":
        newnum = x[:num] + "0" + x[num + 1:]
        return newnum
    else:
        newnum = x[:num] + "1" + x[num + 1:]
        return newnum


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

ind = {}
for i in range(1, 2*(10**5)+1):
    ind[i] = getcount(i)
ind[0] = 1

for i in range(len(x)):
    newnum = bitchange(x, i)
    numcount = newnum.count("1")
    if int(newnum, 2) % numcount != 0:
        print(ind[int(newnum, 2) % numcount] + 1)
    else:
        print(ind[int(newnum, 2) % numcount])

Submission status: Runtime Error

Solution code:
N = int(input())
X = input().strip()
C = X.count("1")
D = int(X, 2)
M = D % C
Mm, Mp = 0, D % (C+1)
if C > 0:
    Mm = D % (C-1)

p = [0]*(2*10**5+2)
for i in range(1, len(p)):
    n = i
    while True:
        b = bin(n).count("1")
        if b <= 0:
            break
        p[i] += 1
        n = n % b
        if p[n] > 0:
            p[i] += p[n]
            break

for i in range(1, N+1):
    m = 0
    c = C
    if X[i-1] == "1":
        c -= 1
        if c == 0:
            print(0)
            continue
        m = Mm
        d = pow(2, N-i, c)
        d = (m-d+c) % c
    else:
        c += 1
        m = Mp
        d = pow(2, N-i, c)
        d = (m+d) % c

    print(p[d]+1)

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
hako = []

for i in range(n):
    x_list = list(x)
    if x_list[i] == str(0):
        x_list[i] = 1
    else:
        x_list[i] = 0
    xx_list = [str(j) for j in x_list]
    xx = "".join(xx_list)
    hako.append(int(xx, 2))

for i in hako:
    cnt = 0
    nn = i
    while nn == 0:
        popcount = str(bin(nn)).count("1")
        nn = nn % popcount
        cnt += 1
    print(cnt)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n = int(input())
X = int(input(),2)

from collections import defaultdict
d = defaultdict(lambda: -1)

Xmemo = defaultdict(lambda: -1)
Xmemo[0]=0

from gmpy2 import popcount

def dfs(X):
    if Xmemo[X]==-1:
        if d[X]==-1:
            pc = popcount(X)
            d[X]=pc
        else:
            pc = d[X]

        if pc == 1:
            Xmemo[X]=1
            return 1
        Xmemo[X] = dfs(X%pc)+1

    return Xmemo[X]


for i in reversed(range(n)):
    print(dfs(X^(1<<i) ))

Submission status: Runtime Error

Solution code:
V

Submission status: Runtime Error

Solution code:
def Base_n_to_10(X,n):
    out = 0
    for i in range(1,len(str(X))+1):
        out += int(X[-i])*(n**(i-1))
    return out#int outn=int(input())
def Base_10_to_n(X, n):
    if (int(X/n)):
        return Base_10_to_n(int(X/n), n)+str(X%n)
    return str(X%n)
n=int(input())
x=input()
pc=x.count("1")
la=[float("inf")]*pc
for i in range(1,pc+1):
    i10=str(Base_10_to_n(i, 2)).count("1")
    if i%i10==0:
      la[i-1]=1
    else:
      la[i-1]=la[(i%i10)-1]+1
if pc!=1:
  x10=Base_n_to_10(x,2)
  for i in range(1,n+1):
    if x[i-1]=="0":
      lk=(x10+pow(2,n-i,pc+1))%(pc+1)
    else:
      lk=(x10-pow(2,n-i,pc-1))%(pc-1)
    if lk==0:
      print(1)
    else:
      print(1+la[lk-1])
else:
  x10=Base_n_to_10(x,2)
  for i in range(1,n+1):
    if x[i-1]=="0":
      ans.append((x10+pow(2,n-i,pc+1))%(pc+1))
    else:
      ans.append("n")
  for a in ans:
    if a==0:
      print(1)
    elif a=="n":
      print(0)
    else:
      print(1+la[a-1])

Submission status: Runtime Error

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

def f(v):
    cnt = 0
    while True:
        if v == 0:
            break
        if v == 1:
            cnt += 1
            break
        v = v % bin(v)[2:].count('1')
        cnt += 1
    return cnt

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

Submission status: Runtime Error

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

outf = {}
res = []

dec_d = {}
def get_dec(bin):
  if bin in dec_d.items():
    return dec_d[bin]
  s = 0
  seed = 2 ** (len(bin)-1)
  for el in bin:
    if el == '1':
      s += seed
    seed = seed // 2
  dec_d[bin] = s
  return s

bin_d = {}
def get_bin(dec):
  if dec in bin_d.items():
    return bin_d[dec]
  s = ''
  while dec > 0:
    if dec % 2 == 1:
      s = s + '1'
    else:
      s = s + '0'
    dec = dec // 2
  bin_d[dec] = s
  return s

pop_d = {}
def popcount(n):
  if n in pop_d.items():
    return pop_d[n]
  out = 0
  while n > 0:
    if n % 2 == 1:
      out += 1
    n = n // 2
  pop_d[n] = out
  return out


for i in range(n):
  if x[i] == '0':
    lx = x[:i] + '1' + x[i+1:]
  else:
    lx = x[:i] + '0' + x[i+1:]
  x_dec = get_dec(lx)
  res.append(x_dec)

  # calc f
  kp = []
  f = 0
  while x_dec > 0:
    st = get_bin(x_dec)
    if st in outf.items():
      f += outf[st]
      break
    kp.append(x_dec)
    f += 1
    pc = popcount(x_dec)
    x_dec = x_dec % pc

  # keep
  lf = f
  for k in kp:
    st = get_bin(k)
    outf[st] = lf
    lf -= 1


for i in res:
  st = get_bin(i)
  print(outf[st])

Submission status: Runtime Error

Solution code:
N = int(input())
a = input()
def bit2(inp):
    A = len(inp)
    ans = 0
    for i in range(A):
        if inp[A-1-i] == "1":
            ans += 2 ** i
    return ans

def bitReverse(bit,i):
    k = "1"
    if bit[i] == "1":
        k = "0"
    return bit[:i] + k + bit[i+1:]
def bitCount(bit):
    count = 0
    for i in bit:
        if i == "1":
            count += 1
    return count
def toBit(inp):
    ans = str(bin(inp))
    return ans[2:]
def mod(bit,count):
    ans = 0
    m = 1
    keta = len(bit)
    for i in range(keta-1,-1,-1):
        if bit[i] == "1":
            ans += m
            ans = ans % count
        m = (m * 2) %count
    return ans%count

def answer(bit,count):
    c = bitCount(bit)
    ans = mod(bit,c)
    if ans == 0:
        return count+1
    return answer(toBit(ans),count+1)
    
length = len(a)
for i in range(length):
    k = bitReverse(a,i)
    print(answer(k,0))

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

def f(n):
    cnt = 0
    while True:
        if n == 0:
            break
        n = n % popcount(n)
        cnt += 1
    return cnt

def pow_r(x, n):
    if n == 0:
        return 1
    if n % 2 == 0:
        return pow_r(x ** 2, n // 2)
    else:
        return x * pow_r(x ** 2, (n - 1) // 2)

if __name__ == "__main__":
    n = int(input())
    x = input()
    xList = list(x)
    k = len(xList) - 1
    for i in range(n):
        xList[i] = str(int(xList[i]) ^ 1)
        xNum = int("".join(xList), 2)
        print(f(xNum))
        xList[i] = str(int(xList[i]) ^ 1)

Submission status: Runtime Error

Solution code:
from sys import stdin
from collections import deque
input = stdin.readline

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

q = deque([])
b = X.count("1")

for i in range(N):
    if X[i] == "0":
        X[i] = "1"
        q.append(["".join(X), b + 1])
        X[i] = "0"
    else:
        X[i] = "0"
        q.append(["".join(X), b - 1])
        X[i] = "1"

while q:
    n, b = q.popleft()
    n = int(n, 2)
    if b == 1 or n % b == 0:
        print(1)
    elif (N % b) % 2 == 0:
        print(2)
    else:
        print(3)

Submission status: Runtime Error

Solution code:
N = int(input())
S = list(map(int,list(input())))
S.reverse()
r = [0 for _ in range(2 * (10 ** 5) + 100)]
p0 = [0 for _ in range(N + 10)]
q0 = 0
p1 = [0 for _ in range(N + 10)]
q1 = 0
q = S.count(1)
p0[0] = 1
p1[0] = 1

for i in range(N):
    p0[i + 1] = (p0[i] * 2) % (q + 1)
    if S[i] == 1:
        q0 += p0[i]
        q0 %= q + 1

for i in range(N):
    p1[i + 1] = (p1[i] * 2) % (q - 1)
    if S[i] == 1:
        q1 += p1[i]
        q1 %= q - 1

r[0] = 0
for i in range(1,2 * (10 ** 5)+10):
    qx = 0
    for i2 in range(22):
        if i >> i2 & 1:
            qx += 1
    r[i] = r[i % qx] + 1

for i in range(N):
    if S[N - i - 1] == 0:
        print(r[(q0 + p0[N-i-1]) % (q + 1)] + 1)
    else:
        print(r[(q1 - p1[N-i-1]) % (q - 1)] + 1)

Submission status: Runtime Error

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):
        if X[i] == '0':
            print(d[b % (c + 1)] + 1 if (b := (m + (1 << (n - i - 1)))) != 0 else 0)
        else:
            print(d[b % (c - 1)] + 1 if (b := (m - (1 << (n - i - 1)))) != 0 else 0)

    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)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n= int(input())



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
    else:
        ans_count[i] = ans_count[f]+1


inp = input()
x = list(inp)

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

ans_count[0]=0
d= ans_count



for i in range(n):
    a = x[i]
#     print(0)
    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: Runtime Error

Solution code:
n = int(input())
x = str(input())
X = 0
one = 0
for i in range(n):
    X+=int(x[i])*2**(n-i-1)
    if x[i]=="1":
        one+=1

l = [0, 1]
for i in range(2,n):
    if i%2==0:
        l.append(1)
    else:
        c=1
        tem = i
        while tem>1:
            tem//=2
            if tem%2==1:c+=1
        l.append(l[i%c]+1)
for i in range(n):
    if x[i]=="1":
        on=one-1
    else:
        on=one+1
    t=X^(2**(n-i-1))
    print(l[t%on]+1)

Submission status: Runtime Error

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

bit_caunt = [0]*(2**N)

for i in range(2**N+1):
    if 2**i >= 2**N:
        break
    bit_caunt[2**i] = 1
    
    for j in range(2**i+1,2**(i+1)):
        bit_caunt[j] = bit_caunt[j-2**i] + 1
        if j >= 2**N:
            break


for i in range(N-1,-1,-1):
    re_X = X^(2**i)#ビット反転した数
    ans = 0
    while re_X != 0:
        pop = bit_caunt[re_X]
        re_X = re_X % pop
        ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
def f(num):
  result = popcount(num)
  if result == 0:
    return 1
  else :
    return f(bin(result)) + 1

def popcount(tmp):
  return int(tmp, 2) % tmp.count("1")

total_number = int(input())
bin_number = list(input())

for i in range(total_number):
  tmp = bin_number.copy()
  if tmp[i] == "0":
    tmp[i] = "1"
  else:
    tmp[i] = "0"

  print(f("".join(tmp)))

Submission status: Runtime Error

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

def popcount(n):
  n = bin(n)
  cnt = 0
  for i in str(n):
    if i == '1':
      cnt += 1
  return cnt

def f_pop(n):
  cnt = 0
  if n == 0:
    cnt = 0
  else:
    while True:
      n = n % popcount(n)
      cnt += 1
      if n == 0:
        break
  return(cnt)

for i in range(n):
  tmp = x
  if tmp[i] == '1':
    tmp[i] = '0'
  elif tmp[i] == '0':
  fx = int(tmp)
  print(popcount(fx))

Submission status: Runtime Error

Solution code:
N = int(input())
X = int(input(), 2)
dp = [-1]*N
dp[0] = 0
checked = [False]*N
for i in range(1, N):
    c = bin(i).count("1")
    dp[i] = dp[i%c] + 1
for i in range(N):
    Xi = X ^ 2**(N-i)
    C = bin(Xi).count("1")
    print(dp[Xi%C]+1)

Submission status: Runtime Error

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

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
x_pop = popcount(x)
for i in reversed(range(0,n)):
    if x&(1<<i):
        tmp_pop = x_pop - 1
    else:
        tmp_pop = x_pop + 1
    tmp = (x^(1<<i)) % tmp_pop
    if tmp <= 0:
        print(1)
        continue
    cnt = 2
    tmp2 = tmp % popcount(tmp)
    while tmp2 > 0:
        tmp %= popcount(tmp)
        cnt += 1
        tmp2 %= popcount(tmp2)
    print(cnt)

Submission status: Runtime Error

Solution code:
N = int(input())
X = [i for i in input()]
sum_X = X.count("1")


def f(n, p):
    count = 1
    while True:
        n = int(n, 2) % p
        if n == 0:
            break
        n = format(n, "b")
        p = n.count("1")
        count += 1
    return count


for i in range(0, N):
    tempX = ""
    count = sum_X
    if X[i] == "0":
        count += 1
        X[i] = "1"
        tempX = "".join(X)
        X[i] = "0"
    else:
        count -= 1
        X[i] = "0"
        tempX = "".join(X)
        X[i] = "1"

    print(f(tempX, count))

Submission status: Runtime Error

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

popc = [0] * ((1 << 19) + 1)
for bit in range(1, 1 << 19):
    opt = bin(bit).count('1')
    popc[bit] = bit % opt

f_list = [0] * ((1 << 19) + 1)
for i in range(1, 1 << 19):
    now = popc[i]
    cnt = 1
    while True:
        if now == 0:
            f_list[i] = cnt
            break
        now = popc[now]
        cnt += 1

N = getN()
X = input()
NX = len(X)
time = X.count('1')
t1 = time + 1
t2 = time - 1

lis_left_1 = [0] * (NX + 1)

now = 1 % t1
lis_left_1[0] = now
for i in range(1, NX + 1):
    now = (2 * now) % t1
    lis_left_1[i] = now

lis_left_2 = [0] * (NX + 1)

now = 1 % t2
lis_left_2[0] = now
for i in range(1, NX + 1):
    now = (2 * now) % t2
    lis_left_2[i] = now

left_mother_1 = 0
for i in range(NX):
    if int(X[i]) == 1:
        left_mother_1 += lis_left_1[NX - i - 1]

left_mother_2 = 0
for i in range(NX):
    if int(X[i]) == 1:
        left_mother_2 += lis_left_2[NX - i - 1]

for i in range(N):
    # 1が0に left_mother_2, t2
    if int(X[i]) == 1:
        if t2 == 0:
            print(0)
        opt_mom = left_mother_2
        opt_mom -= lis_left_2[NX - i - 1]
        opt_mom %= t2
        print(f_list[opt_mom] + 1)
    # 0が1に left_mother_1, t1
    else:
        opt_mom = left_mother_1
        opt_mom += lis_left_1[NX - i - 1]
        opt_mom %= t1
        print(f_list[opt_mom] + 1)

Submission status: Runtime Error

Solution code:

N=int(input())
X=input()
R = int(X, 2)
def F(bi):
    global c
    stbi=bin(bi)
    pop=stbi.count("1")
    next=bi%pop
    c += 1
    if next == 0:
        return
    F(next)
    return
for n in range(N):
    c=0
    if X[n]=="0":
        r=R+(2**((N-n)-1))
    else:
        r=R-(2**((N-n)-1))
    F(r)
    print(c)

Submission status: Runtime Error

Solution code:
from math import *
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:
import sys
sys.setrecursionlimit(10 ** 6)
import copy
n = int(input())
k = input()
xnum = int(k,2)

def f(x):
    a = bin(x)
    a = a[2:]
    num = a.count('1')
    ans = 1
    hantei = x % num
    while hantei != 0:
        ans += 1
        a = bin(hantei)
        a = a[2:]
        num = a.count('1')
        hantei = hantei % num
    return ans

z = []
for i in range(n):
    y = copy.deepcopy(k)
    if y[i] == '1':
        ynum = xnum - 2 ** (n-i-1)
        z.append(ynum)
    else:
        ynum = xnum + 2 ** (n-i-1)
        z.append(ynum)

for j in z:
    ans = f(j)
    print(ans)

Submission status: Runtime Error

Solution code:

import collections
import math
N=int(input())
X=input()

prep=[0 for i in range(N)]
ans=[0 for i in range(N)]

for i in range(1,N):
    cc=collections.Counter(bin(i)[2:])
    temp=cc['1']
    sec=i%temp
    if sec==0:
        prep[i]=1
    else:
        prep[i]=1+prep[sec]


for j in range(N):
    temp=[X[t] for t in range(N)]
    if temp[j]=='0':
        temp[j]='1'
    else:
        temp[j]='0'
    temp.insert(0,'0b')
    cc2=collections.Counter(temp)
    div=cc2['1']
    s = ','.join(temp)
    s=s.replace(',','')
    tempreal=int(s,0)
    ans[j]=prep[tempreal%div]

for anss in ans:
    print(anss+1)

Submission status: Runtime Error

Solution code:
import sys 

readline = sys.stdin.readline 

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

def popcount(number, bit_counter):
    num = number
    counter = 0
    while num != 0:
        bit_con = bit_counter if counter == 0 else bin(num)[2:].count('1')
        num = num % bit_con
        counter += 1

    return counter

x_copy = X.copy()
for i in range(N):
    # ビットの反転
    # x_copy = X.copy()
    bit_count_n = bit_count
    if x_copy[i] == '0':
        x_copy[i] = '1'
        bit_count_n += 1
    else:
        x_copy[i] = '0'
        bit_count_n -= 1

    bit_int = int("".join(x_copy), 2)

    print(popcount(bit_int, bit_count_n))

Submission status: Runtime Error

Solution code:
def func(X):
    cnt = 0
    while X != '0':
        cnt += 1
        X =bin(int(X,2) % X.count('1'))[2:]
    return cnt
N = int(input())
X = input()
for i in range(N):
    if X[i] == '1':
        print(func(X[:i] + '0' + X[(i+1):]))
    else:
        print(func(X[:i] + '1' + X[(i+1):]))

Submission status: Runtime Error

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

def popcount(n):
    bin_str=bin(n)
    cnt=list(bin_str).count('1')
    return(cnt)

def f(n):
    n=int(str(n), 2)
    cnt=1
    while n % popcount(n) != 0:
        cnt+=1
        n = n % popcount(n)
    return(cnt)

for i in range(N):
    temp=list(X)
    if temp[i]=='0':
        temp[i]='1'
    else:
        temp[i]='0'
    print(f(''.join(temp)))

Submission status: Runtime Error

Solution code:
def f(L):
    if L:
        return 2*f(L[:-1])+L[-1]
    else:
        return 0

N=int(input())
X=input()
Zero="0"*N

X=list(map(int,X))

H=X.count(1)
Z=f(X)
G=1<<N

A=[]
for i in range(N):
    G>>=1
    
    if X[i]==0:
        J=H+1
    else:
        J=H-1
        
    Y=Z^G

    if Y==0:
        A.append(0)
        continue
    
    I=1
    Y=Y%J
    try:
        while True:
            Y=Y%bin(Y).count("1")
            I+=1
    except ZeroDivisionError:
        A.append(I)

print("\n".join(map(str,A)))

Submission status: Runtime Error

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

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

memo = {}
for i in range(N):
  if X[i]=='1':
    bitStr = X[:i] + '0' + X[i+1:]
  else:
    bitStr = X[:i] + '1' + X[i+1:]
  num = int(bitStr, 2)
  tempnum = num
  if num in memo:
    print(memo[num])
    continue
  res = 0
  while num!=0:
    num = popctmod(num)
    res += 1
  memo[num] = res
  print(res)

Submission status: Runtime Error

Solution code:
pcmap={}
answermap={}

def popcount(a):
    if a in pcmap.keys():
        return pcmap[a]
    else:
        s = str(bin(a))
        pcmap[a] = s.count('1')
        return pcmap[a]

def func(a):
    cnt=0
    while True:
        a2=popcount(a)
        if a2==0:
            break
        a %= a2
        cnt+=1
    return cnt

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

for i in range(n):
    x2 = list(x)
    if x[i] =='0':
        x2[i] = '1'
    else:
        x2[i] = '0'
    if x2 in answermap.keys():
        print(answermap[x2])
    else:
        x3 = int("".join(x2),2)
        ans = func(x3)
        answermap[x2] = ans
        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, N):
        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 = input()
memo = {1:1, 2:1}
n1 = 0
for i in range(n):
    if x[i] == "1":
        n1 += 1
mup = [1]
mdown = [1]
for i in range(1, n):
    mup.append(mup[-1]*2%(n1+1))
    mdown.append(mdown[-1]*2%(n1-1))
mup.reverse()
mdown.reverse()
mmup = 0
mmdown = 0
for i in range(n):
    mmup = (mmup+mup[i]*int(x[i]))%(n1+1)
    mmdown = (mmdown+mdown[i]*int(x[i]))%(n1-1)
for i in range(n):
    if x[i] == "0":
        state = "up"
        n1i = n1+1
    else:
        state = "down"
        n1i = n1-1
    if state == "up":
        mm = (mmup+mup[i])%n1i
    else:
        mm = (mmdown-mdown[i])%n1i
    count = 1
    while mm > 0:
        if mm in memo:
            count += memo[mm]
            break;
        else:
            mmm = mm
            a = 0
            while mmm > 0:
                if mmm%2 == 1:
                    a += 1
                    mmm //= 2
            memo[mm] = a
            mm %= a
            count += 1
    print(count)

Submission status: Runtime Error

Solution code:
import math
from copy import copy
di = {}
di[0] = 0
for i in range(1, 2*(10**6)+1):
    di[i] = 0
for i in range(1, 2*(10**6)+1):
    count = 0
    for j in range(int(math.log2(i))+4):
        if (i>>j)&1:
            count += 1
    di[i] = di[i%count] + 1
n = int(input())
x = list(input())
x.reverse()
count = 0
for i in x:
    if i =='1':
        count += 1
mod_p = count + 1
mod_m = count - 1
di_p = {}
di_m = {}
for i in range(n):
    di_p[i] = pow(2, i, mod_p)
    if mod_m >= 1:
        di_m[i] = pow(2, i, mod_m)
s_p = 0
s_m = 0
for i in range(n):
    if x[i] == '1':
        s_p += di_p[i]
        s_m += di_m[i]
    else:
        continue
for i in range(n-1, -1, -1):
    sm = copy(s_m)
    sp = copy(s_p)
    if x[i] == '1':
        sm -= di_m[i]
        sm %= mod_m 
        print(di[sm]+1)
    else:
        sp += di_p[i]
        sp %= mod_p
        print(di[sp]+1)

Submission status: Runtime Error

Solution code:
#

import sys
input=sys.stdin.readline

def main():
    N=int(input())
    X=input().strip("\n")[::-1]
    cnt=[0]*N
    for i in range(1,N):
        n=i
        while(n>0):
            pc=0
            for j in range(19):
                if (n>>j)&1==1:
                    pc+=1
            n%=pc
            cnt[i]+=1
    pc=X.count("1")
    t=0
    c=[0]*N
    for i in range(N):
        if X[i]=="1":
            t+=2**i
            c[i]=1
    X=t
    ans=[0]*N
    for i in range(N):
        if c[i]==1:
            x=X-pow(2,i)
            pci=pc-1
            x-=(x//pci)*pci
            ans[i]=cnt[x%pci]+1
        else:
            x=X+pow(2,i)
            pci=pc+1
            x-=(x//pci)*pci
            ans[i]=cnt[x%pci]+1
    ans=ans[::-1]
    for i in range(N):
        print(ans[i])
    
    
    
if __name__=="__main__":
    main()