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:
import heapq as hq

T = int(input())
for _ in range(T):
    N = int(input())
    camels = [list(map(int, input().split())) for _ in range(N)]
    base = 0
    camels_L = [[] for _ in range(N+1)]
    camels_R = [[] for _ in range(N+1)]
    # 左から詰めるラクダと右から詰めるラクダを仕分ける
for camel in camels:
    if camel[1] >= camel[2]:
        camels_L[camel[0]].append(camel[1] - camel[2])
        base += camel[2] # LとRの低いほうを加算
    else:
        # Rラクダは右から何列目かを考えるのでN - camel[0]と反転する
        camels_R[N - camel[0]].append(camel[2] - camel[1])
        base += camel[1] # LとRの低いほうを加算

diff = 0

# Lラクダについて考える
heap_camels = []
hq.heapify(heap_camels)
for i in range(1, N+1):
    # 左からi番目までが限度のラクダをまとめて追加
    for camel in camels_L[i]:
        hq.heappush(heap_camels, camel)
        # 左からi番目までに入りきらない場合に低いものから除外
    while len(heap_camels) > i:
        hq.heappop(heap_camels)
        # heapqに残ったものがすべての条件を満たしうれしさが最大
    diff += sum(heap_camels)

        # Rラクダについても同様
heap_camels = []
hq.heapify(heap_camels)
for i in range(1, N+1):
    for camel in camels_R[i]:
        hq.heappush(heap_camels, camel)
    while len(heap_camels) > i:
        hq.heappop(heap_camels)
diff += sum(heap_camels)
print(diff + base)

Submission status: Runtime Error

Solution code:
n=int(input())

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

one_cnt=s.count("1")

modp=[0]*n
modm=[0]*n

for i in range(n):
    modp[i]=(pow(2,(n-i-1),one_cnt+1)*int(s[i]))%(one_cnt+1)
    modm[i]=(pow(2,(n-i-1),one_cnt-1)*int(s[i]))%(one_cnt-1)

ans=[]
memo_one=[0]*(n+10)

#print(modp,modm)

for i in range(n):
    cnt=0
    mod=0

    for j in range(n):
        if s[i]=="1":
            if one_cnt-1==0:
                ans.append(0)
                break

            if i!=j:
                mod=(mod+modm[j])%(one_cnt-1)
        else:
            if i!=j:
                mod=(mod+modp[j])%(one_cnt+1)
            else:
                mod=(mod+2**(n-i-1))%(one_cnt+1)
    cnt=1

   # print(i,mod)

    if mod==0:
        ans.append(cnt)
    else:
        while 1:
            cnt+=1
            if memo_one[mod]!=0:
                mod=mod%(memo_one[mod])
            else:
                tmp=(bin(mod).count("1"))
                memo_one[mod]=tmp
                mod=mod%(tmp)
            if mod==0:
                ans.append(cnt)
                break
            #print(mod,one_cnt,s[i],cnt)




#print(ans_memo)

for item in ans:
    print(item)

Submission status: Runtime Error

Solution code:
n=int(input())

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

one_cnt=s.count("1")

modp=[0]*n
modm=[0]*n

for i in range(n):
    modp[i]=(pow(2,(n-i-1),one_cnt+1)*int(s[i]))%(one_cnt+1)
    modm[i]=(pow(2,(n-i-1),one_cnt-1)*int(s[i]))%(one_cnt-1)

ans=[]
memo_one=[0]*(n+1)

#print(modp,modm)

for i in range(n):
    cnt=0
    mod=0

    for j in range(n):
        if s[i]=="1":
            if i!=j:
                mod=(mod+modm[j])%(one_cnt-1)
        else:
            if i!=j:
                mod=(mod+modp[j])%(one_cnt+1)
            else:
                mod=(mod+2**(n-i-1))%(one_cnt+1)
    cnt=1

   # print(i,mod)

    if mod==0:
        ans.append(cnt)
    else:
        while 1:
            cnt+=1
            if memo_one[mod]!=0:
                mod=mod%(memo_one[mod])
            else:
                tmp=(bin(mod).count("1"))
                memo_one[mod]=tmp
                mod=mod%(tmp)
            if mod==0:
                ans.append(cnt)
                break
            #print(mod,one_cnt,s[i],cnt)




#print(ans_memo)

for item in ans:
    print(item)

Submission status: Runtime Error

Solution code:
n=int(input())

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

one_cnt=s.count("1")

modp=[0]*n
modm=[0]*n

for i in range(n):
    modp[i]=(pow(2,(n-i-1),one_cnt+1)*int(s[i]))%(one_cnt+1)
    modm[i]=(pow(2,(n-i-1),one_cnt-1)*int(s[i]))%(one_cnt-1)

ans=[]

#print(modp,modm)
memo_one=[-1]*(n+1)
for i in range(n):
    cnt=0
    mod=0

    for j in range(n):
        if s[i]=="1":
            if i!=j:
                mod=(mod+modm[j])%(one_cnt-1)
        else:
            if i!=j:
                mod=(mod+modp[j])%(one_cnt+1)
            else:
                mod=(mod+pow(2,n-i-1,one_cnt+1))%(one_cnt+1)
    cnt=1

   # print(i,mod)

    if mod==0:
        ans.append(cnt)
    else:
        while 1:
            cnt+=1
            if memo_one[mod]==-1:
                tmp=bin(mod).count("1")
                mod=mod%(tmo)
                memo_one[mod]=tmp
            else:
                mod=mod%memo_one[mod]

            if mod==0:
                ans.append(cnt)
                break
            #print(mod,one_cnt,s[i],cnt)




#print(ans_memo)

for item in ans:
    print(item)

Submission status: Runtime Error

Solution code:
n=int(input())

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

one_cnt=s.count("1")

modp=[0]*n
modm=[0]*n

for i in range(n):
    modp[i]=(pow(2,(n-i-1),one_cnt+1)*int(s[i]))%(one_cnt+1)
    modm[i]=(pow(2,(n-i-1),one_cnt-1)*int(s[i]))%(one_cnt-1)

ans=[]

#print(modp,modm)

for i in range(n):
    cnt=0
    mod=0

    for j in range(n):
        if s[i]=="1":
            if i!=j:
                mod=(mod+modm[j])%(one_cnt-1)
        else:
            if i!=j:
                mod=(mod+modp[j])%(one_cnt+1)
            else:
                mod=(mod+2**(n-i-1))%(one_cnt+1)
    cnt=1

   # print(i,mod)

    if mod==0:
        ans.append(cnt)
    else:
        while 1:
            cnt+=1
            mod=mod%(bin(mod).count("1"))
            if mod==0:
                ans.append(cnt)
                break
            #print(mod,one_cnt,s[i],cnt)




#print(ans_memo)

for item in ans:
    print(item)

Submission status: Runtime Error

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

def dec(X):
    a = ''.join(X)
    b = int(a,2)
    return b

def pc(x):
    a = x.count('1')
    return a

al = [0] * N
import copy
for i in range(N):
    ans = 0
    c = X.copy()
    if c[i] == '0':
        c[i] = '1'
    else:
        c[i] = '0'
    x = dec(c) % pc(c)
    if x == 0:
        ans += 1
    else:
        ans += 1
        while x != 0:
            xl = list(format(x,'b'))
            x = dec(xl) % pc(xl)
            ans += 1
    al[i] = ans
for i in range(N):
    print(al[i])

Submission status: Runtime Error

Solution code:
def popcount(n):
    bit_count = bin(n).count('1')
    n = n % bit_count 
    return n

if __name__ == "__main__":
    import sys 

    readline = sys.stdin.readline 

    N = int(input())
    X = readline()
    bit_count = X.count('1')
    mod1 = int(X, 2) % (bit_count + 1)
    mod2 = int(X, 2) % (bit_count - 1)



    for i in range(N):
        if X[i] == '0':
            X_rest = (mod1 + pow(2, N - 1 - i, bit_count + 1)) % (bit_count + 1)
        else:
            if bit_count - 1 != 0:
                X_rest = (mod2 - pow(2, N - 1 - i, bit_count - 1)) % (bit_count - 1)
            else:
                print(0)
                continue

        counter = 1
        while X_rest != 0:
            X_rest = popcount(X_rest)
            counter += 1
        print(counter)

Submission status: Runtime Error

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

N = int(readline())
X = readline().rstrip()

X0 = int(X, 2)
count1 = X.count("1")

X0mod0to1 = X0 % (count1 + 1) # 0->1に変化した際の、X0を割った余り
X0mod1to0 = X0 % (count1 - 1) # 1->0に変化した際の、X0を割った余り

from collections import defaultdict
dp = defaultdict(int)
dp[0] = 0
def f(x): # 愚直にf(x)を求める式
  temp = x
  if x in dp:
    return dp[x]
  cnt = 0
  while x != 0:
    cnt += 1
    pc = bin(x).count("1")
    x %= pc
  dp[temp] = cnt
  return cnt

val = 1
ans = [-1] * N

for i in range(N - 1, -1, -1): # 下の桁から順に、f(Xi)の値を求める
  if X[i] == "0": # 0を1に変える場合
    pat = (X0mod0to1 + val % (count1 + 1)) % (count1 + 1)
    ans[i] = f(pat) + 1
  elif X[i] == "1": # 1を0に変える場合
    pat = (X0mod1to0 - val % (count1 - 1)) % (count1 - 1)
    ans[i] = f(pat) + 1
  val *= 2

print(*ans, sep = "\n")

Submission status: Runtime Error

Solution code:
def popcount(n):
    bit_count = bin(n).count('1')
    n = n % bit_count 
    return n

if __name__ == "__main__":
    import sys 

    readline = sys.stdin.readline 

    N = int(input())
    X = readline()
    bit_count = X.count('1')
    mod1 = int(X, 2) % (bit_count + 1)
    mod2 = int(X, 2) % (bit_count - 1)



    for i in range(N):
        X_rest = 0
        if X[i] == '0':
            X_rest = (mod1 + pow(2, N - 1 - i, bit_count + 1)) % (bit_count + 1)
        else:
            if bit_count - 1 != 0:
                X_rest = (mod2 - pow(2, N - 1 - i, bit_count - 1)) % (bit_count - 1)
            else:
                print(0)
                continue

        counter = 1
        while X_rest != 0:
            X_rest = popcount(X_rest)
            counter += 1
        print(counter)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# 標準入力を取得
N = int(input())
X = int(input(), 2)

# メイン処理


def popcount(n: int) -> int:
    return bin(n).count("1")


popcount_X = popcount(X)
X_plus = X % (popcount_X + 1)
X_minus = X % (popcount_X - 1)
for n in range(1, N + 1):
    x = X ^ (1 << (N - n))
    if x == 0:
        print(0)
        continue

    if not ((X >> (N - n)) & 1):
        x = (X_plus + 2 ** (N - n)) % (popcount_X + 1)
    else:
        x = (X_minus - 2 ** (N - n)) % (popcount_X - 1)
    c = 1
    while x != 0:
        x %= popcount(x)
        c += 1
    print(c)

Submission status: Runtime Error

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

N = int(readline())
X = readline().rstrip()

X0 = int(X, 2)
count1 = X.count("1")

X0mod0to1 = X0 % (count1 + 1) # 0->1に変化した際の、X0を割った余り
X0mod1to0 = X0 % (count1 - 1) # 1->0に変化した際の、X0を割った余り

def f(x): # 愚直にf(x)を求める式
  cnt = 0
  while x != 0:
    cnt += 1
    pc = bin(x).count("1")
    x %= pc
  return cnt

val = 1
ans = [-1] * N

for i in range(N - 1, -1, -1): # 下の桁から順に、f(Xi)の値を求める
  if X[i] == "0": # 0を1に変える場合
    pat = (X0mod0to1 + val % (count1 + 1)) % (count1 + 1)
    ans[i] = f(pat) + 1
  elif X[i] == "1": # 1を0に変える場合
    pat = (X0mod1to0 - val % (count1 - 1)) % (count1 - 1)
    ans[i] = f(pat) + 1
  val *= 2

print(*ans, sep = "\n")

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
##for i in range(n):
#    x_lst.append(int(x)%10)
#    x //= 10
#x_lst.reverse()
for i in range(n):
    x_lst = list(x)
    if x_lst[i] == '0':
        x_lst[i] = '1'
    else:
        x_lst[i] = '0'
    x2 = str("".join(map(str, x_lst)))
    x10 = int(x2, 2)
    xcount = str(x2).count('1')
    ans = 0
    while True:
        if xcount == 0:
            break
        else:
            cnt = x10 % xcount
            elif cnt == 0:
                ans += 1
                break
            else:
                x10 = cnt
                xcount = str(bin(x10)).count('1')
                ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
##for i in range(n):
#    x_lst.append(int(x)%10)
#    x //= 10
#x_lst.reverse()
for i in range(n):
    x_lst = list(x)
    if x_lst[i] == '0':
        x_lst[i] = '1'
    else:
        x_lst[i] = '0'
    x2 = str("".join(map(str, x_lst)))
    x10 = int(x2, 2)
    xcount = str(x2).count('1')
    ans = 0
    while True:
        cnt = x10 % xcount
        if cnt == 0:
            ans += 1
            break
        else:
            x10 = cnt
            xcount = str(bin(x10)).count('1')
            ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
##for i in range(n):
#    x_lst.append(int(x)%10)
#    x //= 10
#x_lst.reverse()
for i in range(1, n+1):
    x_lst = list(x)
    if x_lst[i-1] == 0:
        x_lst[i-1] = 1
    else:
        x_lst[i-1] = 0
    x2 = str("".join(map(str, x_lst)))
    x10 = int(x2, 2)
    xcount = str(x2).count('1')
    ans = 0
    while True:
        cnt = x10 % xcount
        if cnt == 0:
            ans += 1
            break
        else:
            x10 = cnt
            xcount = str(bin(x10)).count('1')
            ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
def popcount(n):
    bit_count = bin(n).count('1')
    n = n % bit_count 
    return n

if __name__ == "__main__":
    import sys 

    readline = sys.stdin.readline 

    N = int(input())
    X = readline()
    bit_count = X.count('1')
    X_int = int(X, 2)


    for i in range(N):
        # ビットの反転
        X_int_copy = X_int
        bit_count_n = bit_count
        if X[i] == '0':
            bit_count_n += 1
            X_int_copy += pow(2, N - 1 - i)
        else:
            bit_count_n -= 1
            X_int_copy -= pow(2, N - 1 - i)

        # print("反転後{}".format(X_int_copy))
        # ビット反転後に0になった場合
        if X_int_copy == 0:
            print(0)

        # 1回操作しておく
        popcount_X = X_int_copy % bit_count_n 
        counter = 1
        while popcount_X != 0:
            popcount_X = popcount(popcount_X)
            counter += 1

        print(counter)

Submission status: Runtime Error

Solution code:
def popcount(n):
    bit_count = bin(n).count('1')
    n = n % bit_count 
    return n

if __name__ == "__main__":
    import sys 

    readline = sys.stdin.readline 

    N = int(input())
    X_str= readline()
    X = list(X_str)
    bit_count = X_str.count('1')
    X_int = int(X_str, 2)


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

        # print("反転後{}".format(X_int_copy))
        # ビット反転後に0になった場合
        if X_int_copy == 0:
            print(0)

        # 1回操作しておく
        popcount_X = X_int_copy % bit_count_n 
        counter = 1
        while popcount_X != 0:
            popcount_X = popcount(popcount_X)
            counter += 1

        print(counter)

Submission status: Runtime Error

Solution code:
def func(z,c):
    if c == 0:
        z = 0
    else:
        z = z%c
    a = bin(z)
    b = 0
    for i in range(len(a)):
        if a[i] == "1":
            b += 1
    return z,b

n = int(input())
x = input()
c = 0
sw = 0
for i in range(n):
    if x[i] == "1":
        c += 1
s0 = int(x,2)%(c+1)
if c <= 1:
    s1 = 0
else:
    s1 = int(x,2)%(c-1)
for i in range(n):
    sw = 0
    if x[i] == "0":
        d = c + 1
        z = (s0 + pow(2,n-i-1,d))%d
    else:
        d = c - 1
        if d == 0:
            sw = 1
        else:
            z = (s1 - pow(2,n-i-1,d))%d
    ans = 1
    p = bin(z)
    e = 0
    for A in str(p):
        if A == "1":
            e += 1
    d = e
    if sw == 1 or d == 0:
        ans = 0
    else:
        while z:
            z,d = func(z,d)
            ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
def func(z,c):
    if c == 0:
        z = 0
    else:
        z = z%c
    a = bin(z)
    b = 0
    for i in range(len(a)):
        if a[i] == "1":
            b += 1
    return z,b

n = int(input())
x = input()
c = 0
sw = 0
for i in range(n):
    if x[i] == "1":
        c += 1
s0 = int(x,2)%(c+1)
if c <= 1:
    s1 = 0
else:
    s1 = int(x,2)%(c-1)
for i in range(n):
    sw = 0
    if x[i] == "0":
        d = c + 1
        z = (s0 + pow(2,n-i-1,d))%d
    else:
        d = c - 1
        if d == 0:
            sw = 1
        else:
            z = (s1 - pow(2,n-i-1,d))%d
    ans = 1
    p = bin(z)
    e = 0
    for A in str(p):
        if A == "1":
            e += 1
    d = e
    if sw == 1:
        ans = 0
    else:
        while z:
            z,d = func(z,d)
            ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
def func(z,c):
    if c == 0:
        z = 0
    else:
        z = z%c
    a = bin(z)
    b = 0
    for i in range(len(a)):
        if a[i] == "1":
            b += 1
    return z,b

n = int(input())
x = input()
c = 0
for i in range(n):
    if x[i] == "1":
        c += 1
s0 = int(x,2)%(c+1)
s1 = int(x,2)%(c-1)

for i in range(n):
    if x[i] == "0":
        d = c + 1
        z = (s0 + pow(2,n-i-1,d))%d
    else:
        d = c - 1
        z = (s1 - pow(2,n-i-1,d))%d
    ans = 1
    #print(z)
    p = bin(z)
    e = 0
    for A in str(p):
        if A == "1":
            e += 1
    d = e
    while z:
        z,d = func(z,d)
        ans += 1
    print(ans)

Submission status: Runtime Error

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

count = x.count('1')
one_count = count - 1
zero_count = count + 1

one_mod = 0
zero_mod = 0
for b in x:
    if one_count:
        one_mod = (one_mod * 2 + int(b)) % one_count
    zero_mod = (zero_mod * 2 + int(b)) % zero_count

f = [0] * 22000
pop_count = [0] * 22000
for i in range(1, 22000):
    pop_count[i] = pop_count[i//2] + i % 2
    f[i] = f[i % pop_count[i]] + 1

for i in range(n):
    if x[i] == '1':
        if one_count:
            nxt = one_mod
            nxt -= pow(2, n-i-1, one_count)
            nxt %= one_count
            print(f[nxt] + 1)
        else:
            print(0)
    if x[i] == '0':
        nxt = zero_mod
        nxt += pow(2, n-i-1, zero_count)
        nxt %= zero_count
        print(f[nxt] + 1)

Submission status: Runtime Error

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

count = x.count('1')
one_count = count - 1
zero_count = count + 1

one_mod = 0
zero_mod = 0
for b in x:
    if one_count:
        one_mod = (one_mod * 2 + int(b)) % one_count
    zero_mod = (zero_mod * 2 + int(b)) % zero_count

f = [0] * 20001
pop_count = [0] * 20001
for i in range(1, 20001):
    pop_count[i] = pop_count[i//2] + i % 2
    f[i] = f[i % pop_count[i]] + 1

for i in range(n):
    if x[i] == '1':
        if one_count:
            nxt = one_mod
            nxt -= pow(2, n-i-1, one_count)
            nxt %= one_count
            print(f[nxt] + 1)
        else:
            print(0)
    if x[i] == '0':
        nxt = zero_mod
        nxt += pow(2, n-i-1, zero_count)
        nxt %= zero_count
        print(f[nxt] + 1)

Submission status: Runtime Error

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

ary = [None for i in range(200010)]
ary[0] = 0

def f(n):
  if ary[n] is not None:
    return ary[n]
  b = bin(n).count('1')
  r = 1 + f(n%b)
  ary[n] = r
  return ary[n]


a1 = a + 1
a0 = a - 1
for i in range(200010):
  f(i)


one = [1] * 200010
zero = [1] * 200010
for i in range(1, 200010):
    if a0 != 0:
        one[i] = one[i-1] * 2 % a0
    zero[i] = zero[i-1] * 2 % a1


ans = [0 for i in range(n)]
c1 = b%a1
c0 = b%a0
for i in range(n-1, -1, -1):
  if x[n-1-i] == '0':
    y = c1 + zero[i]
    # y = x %a1
    y %= a1
    print (ary[y]+1)
  else:
    if a0 != 0:
      y = c0 - one[i]
      y %= a0
      print (ary[y]+1)
    else:
      print (0)
# ans.reverse()
# for i in ans:
#   print (i)

Submission status: Runtime Error

Solution code:
N = int(input())
#N = 2*(10**5)
#X = randint(1, 2**(N+1)-1)
X = int(str(input()), 2)
#X = 2**(N+1)-1
X_bin = format(X, '0'+str(N)+'b')
popcount = [sum(map(int, X_bin)) - 1, sum(map(int, X_bin)) + 1]
mod = [X % popcount[0], X % popcount[1]]

ans = [0] * N
dp = [0] * 2 ** 18
for i in range(N):
    if X_bin[i] == '1':
        if X_bin.count('1') == 1:
            ans[i] = 0
            print(ans[i])
            continue
        n = mod[0] - (2 ** (N - 1 - i)) % popcount[0]
        if n == popcount[0]:
            ans[i] = 1
            print(ans[i])
            continue
        elif n < 0:
            n += popcount[0]
    else:
        n = mod[1] + (2 ** (N - 1 - i)) % popcount[1]
        if n == popcount[1]:
            ans[i] = 1
            print(ans[i])
            continue

    tmp = []
    ans[i] += 1
    while n != 0:
        if dp[n]:
            ans[i] += dp[n]
            break
        tmp.append(n)
        n_bin = format(n, '0' + str(N) + 'b')
        n = n % sum(map(int, n_bin))
        ans[i] += 1
    for j in range(len(tmp)):
        dp[tmp[j]] = ans[i] - 1 - j

    print(ans[i])

Submission status: Runtime Error

Solution code:
import copy
N = int(input())
X = input()
X2 = copy.deepcopy(X)
L = [0]*(2**N+10)

def f(n):
    global L
    k = 0
    if L[n] == 0:
        while n != 0:
            k += 1
            pop = str(bin(n)).count("1")
            n = n%pop
        L[n] = k
        return k
    else:
        return L[n]



for p in range(N):
    Xi = int(X,2) ^ 2**(N-p-1)  #XORで１つだけbit反転
    print(f(Xi))

Submission status: Runtime Error

Solution code:
N = int(input())
X = int(str(input()), 2)
X_bin = format(X, '0'+str(N)+'b')
popcount = [X_bin.count('1') - 1, X_bin.count('1') + 1]
mod = [X % popcount[0], X % popcount[1]]

ans = [0] * N
dp = [0] * 2 ** 18
for i in range(N):
    if X_bin[i] == '1':
        if X_bin.count('1') == 1:
            ans[i] = 0
            print(ans[i])
            continue
        n = mod[0] - (2 ** (N - 1 - i)) % popcount[0]
        if n == popcount[0]:
            ans[i] = 1
            print(ans[i])
            continue
        elif n < 0:
            n += popcount[0]
    else:
        n = mod[1] + (2 ** (N - 1 - i)) % popcount[1]
        if n == popcount[1]:
            ans[i] = 1
            print(ans[i])
            continue

    tmp = []
    ans[i] += 1
    while n != 0:
        if dp[n]:
            ans[i] += dp[n]
            break
        tmp.append(n)
        n = n % format(n, '0' + str(N) + 'b').count('1')
        ans[i] += 1
    for j in range(len(tmp)):
        dp[tmp[j]] = ans[i] - 1 - j

    print(ans[i])

Submission status: Runtime Error

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

F = S.count("1")
A = T % (F + 1)
B = T % (F - 1) if F != 0 else 0

def f(x):
	count = 0
	while x:
		x %= bin(x).count("1")
		count += 1
	return count

for i in range(N):
	if S[i] == "1":
		if F == 1:
			print(0)
			continue
		print(1 + f((B - (1 << 23 - i - 1) % (F - 1)) % (F - 1)))
	else:
		print(1 + f((A + (1 << 23 - i - 1) % (F + 1)) % (F + 1)))

Submission status: Runtime Error

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

F = S.count("1")
A = T % (F + 1)
B = T % (F - 1)

def f(x):
	count = 0
	while x:
		x %= bin(x).count("1")
		count += 1
	return count

for i in range(N):
	if S[i] == "0":
		print(1 + f((A + (1 << 23 - i - 1) % (F + 1)) % (F + 1)))
	else:
		print(1 + f((B - (1 << 23 - i - 1) % (F - 1)) % (F - 1)))

Submission status: Runtime Error

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

F = S.count("1")
A = T % (F + 1)
B = T % (F - 1)

def f(x):
	count = 0
	while x:
		x %= bin(x).count("1")
		count += 1
	return count

for i in range(N):
	if S[i] == "0":
		print(1 + f(A + (1 << 23 - i - 1) % (F + 1)))
	else:
		print(1 + f(B - (1 << 23 - i - 1) % (F - 1)))

Submission status: Runtime Error

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

ary = [None for i in range(200010)]
ary[0] = 0

def f(n):
  if ary[n] is not None:
    return ary[n]
  b = bin(n).count('1')
  r = 1 + f(n%b)
  ary[n] = r
  return ary[n]


for i in range(200010):
  f(i)

a1 = a + 1
a0 = a - 1

ans = [0 for i in range(n)]
for i, j in enumerate(reversed(list(x))):
  if j == '0':
    x = b + pow(2,i,a1)
    # y = x %a1
    x %= a1
    ans[i] = ary[x]+1
  else:
    x = b - pow(2,i,a0)
    # y = x %a0
    x %= a0
    ans[i] = ary[x]+1
ans.reverse()
for i in ans:
  print (i)

Submission status: Runtime Error

Solution code:
def f(n):
    ret = 1
    while True:
        if n == 0:
            break
        n %= bin(n).count('1')
        ret += 1
    return ret

if __name__ == "__main__":
    n = int(input())
    x = input()
    cnt = x.count('1')

    if cnt == 1:
        for x in X[:-1]:
            if x == '0':
                print(1)
            else:
                print(0)
        if X[-1] == '1':
            print(0)
        else:
            print(2)
        exit()

    xNum = 0
    for k in x:
        xNum <<= 1
        if k == '1':
            xNum += 1

    p = xNum % (cnt + 1)
    m = xNum % (cnt - 1)

    for i in range(n):
        if x[i] == '0':
            if (p + (pow(2, n - i - 1, cnt + 1))) % (cnt + 1) == 0:
                print(1)
            else:
                print(f(p + (pow(2, n - i - 1, cnt + 1)) % (cnt + 1)))
        else:
            if (m - (pow(2, n - i - 1, cnt - 1))) % (cnt - 1) == 0:
                print(1)
            else:
                print(f(m - (pow(2, n - i - 1, cnt - 1)) % (cnt - 1)))

Submission status: Runtime Error

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

ary = [None for i in range(200010)]
ary[0] = 0

def f(n):
  if ary[n] is not None:
    return ary[n]
  b = bin(n).count('1')
  r = 1 + f(n%b)
  ary[n] = r
  return ary[n]


for i in range(200010):
  f(i)

a1 = a + 1
a0 = a - 1

ans = [0 for i in range(n)]
for i, j in enumerate(reversed(list(x))):
  if j == '0':
    x = b + pow(2,i)
    y = x %a1
    ans[i] = ary[y]+1
  else:
    x = b - pow(2,i)
    y = x %a0
    ans[i] = ary[y]+1
ans.reverse()
for i in ans:
  print (i)

Submission status: Runtime Error

Solution code:

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

#%%

def popcount(n):
    temp = bin(n)[2:]
    return temp.count("1")

pop_memo = [0] * 220000
for i in range(220000):
    pop_memo[i] = popcount(i)

pop_origin = X.count("1")
pop_one = pop_origin - 1
pop_zero = pop_origin + 1

f_cnt = [0] * 220000
for i in range(1, 220000):
    f_cnt[i] = f_cnt[i % pop_memo[i]] + 1

#pow_cnt = [0] * N
#for i in range(N):
#    pow_cnt[i] = pow(2, i)
#pow_cnt.reverse()

X_int = int(X, 2)
for i in range(N):
    if X[i] == "1":
        temp = X_int - pow(2, N - i - 1)
        n = temp % pop_one
        print(f_cnt[n] + 1)

    elif X[i] == "0":
        temp = X_int + pow(2, N - i - 1)
        n = temp % pop_zero
        print(f_cnt[n] + 1)

Submission status: Runtime Error

Solution code:

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

#%%

def popcount(n):
    temp = bin(n)[2:]
    return temp.count("1")

pop_memo = [0] * 220000
for i in range(220000):
    pop_memo[i] = popcount(i)

pop_origin = X.count("1")
pop_one = pop_origin - 1
pop_zero = pop_origin + 1

f_cnt = [0] * 220000
for i in range(1, 220000):
    f_cnt[i] = f_cnt[i % pop_memo[i]] + 1

#pow_cnt = [0] * N
#for i in range(N):
#    pow_cnt[i] = pow(2, i)
#pow_cnt.reverse()

X_int = int(X, 2)
for i in range(N):
    if X[i] == "1":
        temp = X_int - pow(2, N - i - 1)
        n = temp % pop_one
        print(f_cnt[n] + 1)

    elif X[i] == "0":
        temp = X_int + pow(N - i - 1)
        n = temp % pop_zero
        print(f_cnt[n] + 1)

Submission status: Runtime Error

Solution code:

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

#%%

def popcount(n):
    temp = bin(n)[2:]
    return temp.count("1")

def f(n):
    cnt = 0
    while n != 0:
        n = n % pop_memo[n]
        cnt += 1

    return cnt

pop_memo = [0] * 220000
for i in range(220000):
    pop_memo[i] = popcount(i)

pop_origin = popcount(int(X, 2))
pop_one = pop_origin - 1
pop_zero = pop_origin + 1

f_cnt = [0] * 220000
for i in range(1, 220000):
    f_cnt[i] = f_cnt[i % pop_memo[i]] + 1

pow_cnt = [0] * N
for i in range(N):
    pow_cnt[i] = pow(2, i)
pow_cnt.reverse()

for i in range(N):
    if X[i] == "1":
        tem = int(X, 2) - pow_cnt[i]
        n = tem % pop_one
        print(f_cnt[n] + 1)

    elif X[i] == "0":
        tem = int(X, 2) + pow_cnt[i]
        n = tem % pop_zero
        print(f_cnt[n] + 1)

Submission status: Runtime Error

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


def f(n):
    if n == 0:
        return 1
    p = n % (bin(n).count('1'))
    return f(p) + 1


def main(input, print):
    N = int(input())
    X = list(map(int, list(input())))
    ans = [0] * N

    pcnt = 0
    for i in range(N):
        if X[i] == 1:
            pcnt += 1
    for is_up in range(2):
        current_pcnt = pcnt
        if is_up:
            current_pcnt -= 1
        else:
            current_pcnt += 1
        if current_pcnt <= 0:
            continue
        total = 0
        for i in range(N):
            total = (total*2) % current_pcnt
            total += X[i]
        current_mask = 1
        for i in reversed(range(N)):
            if(X[i] == is_up):
                current_total = total
                if is_up:
                    current_total = (current_total-current_mask+current_pcnt) % current_pcnt
                else:
                    current_total = (current_total+current_mask) % current_pcnt
                ans[i] = f(current_total)
            current_mask = current_mask * 2 % current_pcnt

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


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Submission status: Runtime Error

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

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

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

x = int(X, 2)
pc_x = popcount(x)
if pc_x == 0:
    x_d = x
else:
    x_d = x%pc_x

for i in range(1, N+1):
    flag = Flag[i]
    pc_y = pc_x + flag

    y_d = (x_d + flag*2**(N-1))%pc_y
    
#    print(Y[i], pc_y, y_d)
    
    count = 1
    while y_d != 0:
        y_d = y_d%popcount(y_d)
        count += 1
    print(count)

Submission status: Runtime Error

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

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

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

x = int(X, 2)
pc_x = popcount(x)
x_d = x%pc_x

Y_d = [[] for _ in range(N+1)]
for i in range(1, N+1):
    y = Y[i]
    pc_y = pc_x + Flag[i]
    y_d = y%pc_y
    
    count = 1
    while y_d != 0:
        y_d = y_d%bin(y_d).count('1')
        count += 1
    print(count)