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

Y = int(X, 2)
Z = list(map(int,list(X)))
X_1 = bin(Y).count("1")
X_1m = X_1-1
X_1p = X_1+1
Ym = Y%X_1m
Yp = Y%X_1p


temp = []
for i in range(200001):
    ans = 0
    while i > 0:
        i %= bin(i).count("1")
        ans += 1
    temp.append(ans)

temp2p = []
temp2m = []
ansp = 1
ansm = 1
for i in range(200001):
    ansp %= X_1p
    ansm %= X_1m
    temp2p.append(ansp)
    temp2m.append(ansm)
    ansp *= 2
    ansm *= 2    

for i in range(N):
    if Z[i]==0:
        Xi = Yp + temp2p[(N-i-1)]
        Xi %= X_1p
        print(1+temp[Xi])
    else:
        Xi = Ym + temp2m[(N-i-1)]
        Xi %= X_1m
        print(1+temp[Xi])

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(20):
        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:
n = int(input())
x = int(input(),2)
# b = int(2**(n-1))
pc = 0
d = []
c = x
for i in range(n):
    d.append(c&1)
    if c&1 == 1:
        pc += 1
    c=c>>1

mp =  x%(pc+1)
mm = x%(pc-1)
# print(x,pc,mp,mm)
for i in range(n):
    if d[-i-1]==0:
        m = 1
        temp = (mp+pow(2,n-i-1,pc+1)) % (pc+1)
    else:
        m = -1
        temp = (mm-pow(2,n-i-1,pc+1)) % (pc-1)
    # temppc = pc+m
    # temp = x^b
    ans = 1
    # print(temp,x,b)
    # print(temp,mp,pc,pow(2,n-i,pc+1))
    while temp:
        
        c = temp
        temppc = 0
        while c:
            if c&1 == 1:
                temppc += 1
            c=c>>1
        # print(temp)
        # print(i,temp,ans,temppc)
        # print(temp)
        # s = str(bin(temp))
        # print(temp,popcount(temp))
        if temppc == 0:
            break
        temp = temp % temppc
        ans += 1
        # c = temp
        # temppc = 0
        # while c:
        #     if c&1 == 1:
        #         temppc += 1
        #     c=c>>1
        # print(temp,s)
        # break
    # b=b>>1
    print(ans)

Submission status: Runtime Error

Solution code:
from functools import lru_cache

N = int(input())
X = input()
x = int(X, 2)
y = X.count('1')
if y == 0:
    x2 = 0
else:
    x2 = x % (y-1)
x1 = x % (y+1)

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

d = [0] * (2*10**5+5)
for i in range(2*10**5+5):
    d[i] = f(i)

for i in range(N):
    if x >>(N - i - 1) & 1:
        # print(f(x-pow(2, N-i-1)))
        print(d[(x2 - pow(2, N - i - 1, y-1)) % (y-1)] + 1)
    else:
        # print(f(x+pow(2, N-i-1)))
        print(d[(x1 + pow(2, N - i - 1, y+1)) % (y+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

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)%jppp
  else:
    a=(jom-nijo%jppm)%jppm
  co=1
  while a!=0:
    co+=1
    a%=popcount(a)
  print(co)

Submission status: Runtime Error

Solution code:
def ppc(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 sol():
    n=int(input())
    x=input()
    chk=0
    for i,j in enumerate(x[::-1]):
        if j=="1":
            chk+=2**i
    c,d={},{}
    ans=[]
    for i,j in enumerate(x[::-1]):
        p=pow(2,i)
        if j=="1":
            t=chk-p
        else:
            t=chk+p
        s=t
        cnt=0
        while t:
            if t not in c:
                pc=ppc(t)
                c[t]=pc
            else:
                pc=c[t]
            t%=pc
            cnt+=1
            if t in d:
                cnt+=d[t]
                break
        if s not in d:
            d[s]=cnt
        ans.append(cnt)
    for i in ans[::-1]:
        print(i)

if __name__=="__main__":
    sol()

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
M = X.count("1")
for i in range(N):
  c = 1
  if X[i]=="0":
    R = X[:i]+"1"+X[i+1:]
    R = (int(R, 2))%(M+1)
  else:
    R = X[:i]+"0"+X[i+1:]
    R = (int(R, 2))%(M-1)
  while R>0:
    R = R%bin(R).count("1")
    c += 1
  print(c)

Submission status: Runtime Error

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

x_cnt = 0
for i, y in enumerate(x):
    if y == 1:
        x_cnt += 1

aa = x_cnt + 1
bb = x_cnt - 1

a = [1 % aa]
if bb > 0:
    b = [1 % bb]
else:
    b = [0]

for _ in range(n-1):
    a.append(a[-1]*2 % aa)
    b.append(b[-1]*2 % bb)

a = a[::-1]
b = b[::-1]

x_ps = 0
x_ng = 0
for i, val in enumerate(x):
    if val == 1:
        x_ps += a[i]
        x_ng += b[i]

for i in range(n):
    ans = 0
    if x[i] == 0:
        cnt = x_cnt + 1
        val = (x_ps + a[i]) % cnt
    else:
        cnt = x_cnt - 1
        if cnt == 0:
            print(ans)
            continue
        val = (x_ng - b[i]) % cnt
    ans += 1

    tmp = val
    cnt = 0
    while tmp > 0:
        if tmp & 1:
            cnt += 1
            tmp = (tmp-1) // 2
        else:
            tmp = tmp // 2

    if cnt == 0:
        print(ans)
        continue

    while val > 0:
        ans += 1
        val = val % cnt
        tmp = val % cnt
        cnt = 0
        while tmp > 0:
            if tmp & 1:
                cnt += 1
                tmp = (tmp-1) // 2
            else:
                tmp = tmp // 2
    print(ans)

Submission status: Runtime Error

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

n = int(input())
s = input()

popcnt = 0
for c in s:
    if c=='1':
        popcnt += 1

num = int(s, 2)
# print(num)
# print(num%(popcnt-1))
# print(num%(popcnt+1))

p_l = num%(popcnt-1)
p_h = num%(popcnt+1)

next = [-1]*n
for i in range(n):
    # print(s[i])
    if s[i]=='0':
        next[i] = (p_h + 2**(n-i-1)%(popcnt+1))%(popcnt+1)
    else:
        next[i] = (p_l - 2**(n-i-1)%(popcnt-1))%(popcnt-1)

# print(next)

d = {0:0}
for number in next:
    if number in d.keys():
        continue
    m = number
    tmp = 0
    while not m in d.keys():
        m = m%bin(m).count("1")
        tmp += 1
    d[number] = d[m]+tmp

for number in next:
    print(d[number]+1)

Submission status: Runtime Error

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


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

cache = [-1] * (2 * 10 ** 5 + 1)


def f(n):
    if cache[X] != -1:
        return cache[X]
    return f(n % popcount(n)) + 1

def g(n, m):
    if n < 60:
        return (1 << n) % m
    else:
        t = n // 2
        return g(t, m) * g(n - t, m) % m


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

c = X.count('1')
t1 = [0] * N
t2 = [0] * N
for i in range(N):
    n = N - 1 - i
    t1[i] = g(n, c - 1)
    t2[i] = g(n, c + 1)

x1, x2 = 0, 0
for i in range(N):
    if X[i] == '1':
        x1 += t1[i]
        x2 += t2[i]

result = []
for i in range(N):
    if X[i] == '1':
        n = x1 - t1[i]
        n %= c - 1
    elif X[i] == '0':
        n = x2 + t2[i]
        n %= c + 1
    result.append(f(n) + 1)
print(*result, sep='\n')

Submission status: Runtime Error

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

def popcount(n):
  return str(bin(n)).count("1")
def f(n):
  ans=0
  while True:
    n = n % popcount(n)
    ans += 1
    if n == 0:
      break
  return ans

for i in range(N):
  x = [k for k in copy.copy(X)]
  if x[i] == "0": x[i] = "1"
  else: x[i] = "0"
  s = "".join(x)
  print(f(int(str(s), 2)))

Submission status: Runtime Error

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

f = [0 for _ in range(len(x)+1)]
for i in range(1,len(x)+1):
  one_num = str(bin(i)).count("1")
  #print(i,one_num)
  if i%one_num == 0:
    f[i] = 1
  else:
    f[i] = f[i%one_num] + 1
base = str(int(x)).count("1")
x_num = int(x, 2)
#print(x_num)
for i in range(n):
  b = base
  #print(x[i])
  if x[i] == "0":
    b += 1
    t = x_num + 2**(n-i-1)
  else:
    b -= 1
    t = x_num - 2**(n-i-1)
  print(1+f[t%b])

Submission status: Runtime Error

Solution code:

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

MAX = 2*10**5+1
ppc = [0]*MAX

def popcount(n):
  if ppc[n]>0:
    ppc[n]  
  if n == 0:
    return 0
  b = bin(n).count('1')  
  tmp = n%b
  ppc[n] = popcount(tmp) + 1
  return ppc[n]

for i in range(2*10**5):
  popcount(i+1)
  
bit = int('0b'+x,0)
bn = x.count('1')
for i in range(n,0,-1):
  tmp = bit ^ (1 << (i-1))
  if bit & (1 << (i-1)):
    bt = bn-1
  else:
    bt = bn+1    
  print(ppc[tmp%bt]+1)

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 = int(X, 2) % (cnt + 1)
res1 = int(X, 2) % (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=int(input(),2)
bitn=bin(x).count("1")

a=2**n
for i in range(n):
    a//=2
    m=x^a
    ans=1
    b=bitn
    if m&a:
        b+=1
    else:
        b-=1
    while m%b!=0:
        m=m%b
        b=bin(m).count("1")
        ans+=1
    print(ans)

Submission status: Runtime Error

Solution code:
from sys import stdin
import sys
import itertools
import array
import textwrap
import math

N = int(input())
X = input()
temp = X.count("1")
t = [0, 0, 0]
t[0] = int(X, 2) % (temp-1)
# t[1] = int(X, 2) % (temp)
t[2] = int(X, 2) % (temp+1)
# print(X)
cnt = 0
# X = int(X, 2)
# print(X)
for i in range(N):
    if X[i] == "1":
        p = (1 << (N-i-1)) % (temp-1)
        a = (t[0]-p) % (temp-1)
    elif X[i] == "0":
        m = (1 << (N-i-1)) % (temp+1)
        a = (t[2]+m) % (temp+1)
    cnt = 1
    # print(a)
    while a > 0:
        a = a % str(bin(a)).count("1")
        # print(a)
        cnt += 1
    print(cnt)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000000)

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

c1 = x.count('1')
cc1 = int('0b' + x, 0) % (c1 - 1)
cc2 = int('0b' + x, 0) % (c1 + 1)

def f(n):
    ans = 0
    while n > 0:
        ans += 1
        n = n % bin(n).count('1')
    return ans

for i in range(n):
    if x[i] == '1':
        print(f((pow(2, n-i-1, c1-1) + cc1) % (c1 - 1)) + 1)
    else:
        print(f((pow(2, n-i-1, c1+1) + cc2) % (c1 + 1)) + 1)

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())
    *X, = map(int, input())

    memo = [-1] * 21

    def f(x):
        ret = 0
        while x > 0:
            x = x % bin(x)[2:].count('1')
            ret += 1
        return ret

    for x in range(21):
        memo[x] = f(x)

    cnt = X.count(1)

    pow2_0_1 = [1]
    pow2_1_0 = [1]

    t_0_1 = 1
    t_1_0 = 1
    for i in range(N):
        t_0_1 = t_0_1 * 2 % (cnt + 1)
        pow2_0_1.append(t_0_1)

        t_1_0 = t_1_0 * 2 % (cnt - 1)
        pow2_1_0.append(t_1_0)

    chg_0_1 = 0
    chg_1_0 = 0
    i = 0
    for d in reversed(X):
        if d:
            chg_0_1 = (chg_0_1 + pow2_0_1[i]) % (cnt + 1)
            chg_1_0 = (chg_1_0 + pow2_1_0[i]) % (cnt - 1)
        i += 1

    ans = []
    i = 0
    for d in reversed(X):
        if d:
            t = (chg_1_0 - pow2_1_0[i]) % (cnt - 1)
        else:
            t = (chg_0_1 + pow2_0_1[i]) % (cnt + 1)
        i += 1

        add_v = 1
        while t > 20 or memo[t] == -1:
            t = t % bin(t)[2:].count('1')
            add_v += 1
        ans.append(memo[t] + add_v)

    ans.reverse()

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


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
#
# sys.setrecursionlimit(10 ** 7)
#
# (int(x)-1 for x in input().split())
# rstrip()
#
# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)

from functools import lru_cache


bit = {}
@lru_cache(maxsize=None)
def popcount2(bits):
    if bits in bit:
        return bit[bits]
    ori_bit = bits
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555)
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333)
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f)
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff)
    ans = (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff)
    bit[ori_bit] = ans
    return ans


memo = {0: 0}
@lru_cache(maxsize=None)
def rec(n):
    if n in memo:
        return memo[n]
    
    p = popcount2(n)
    new_n = n % p
    ans = rec(new_n) + 1
    memo[n] = ans
    return memo[n]


def submit():
    n = int(input())
    xs = input()
    x = int('0b' + xs, 0)

    # 前準備
    for i in range(1, 200000):
        rec(i)

    base_bit = 0
    for c in xs:
        if c == "1":
            base_bit += 1
    bit[x] = base_bit
    mask = 1 << (n - 1)
    for i in range(1, n + 1):
        if xs[i - 1] == "0":
            xi = x + mask
            bit[xi] = bit[x] + 1
        else:
            xi = x - mask
            bit[xi] = bit[x] - 1
        new_n = xi % bit[xi]
        print(memo[new_n] + 1)
        mask >>= 1


if __name__ == "__main__":
    submit()

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+1):
    p0[i + 1] = (p0[i] * 2) % (q + 1)
    if S[i] == 1:
        q0 += p0[i]
        q0 %= q + 1

for i in range(N+1):
    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(20):
        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:
def ppc(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    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 sol():
    n=int(input())
    x=input()
    chk=0
    for i,j in enumerate(x[::-1]):
        if j=="1":
            chk+=2**i
    c,d={},{}
    ans=[]
    for i,j in enumerate(x[::-1]):
        p=pow(2,i)
        if j=="1":
            t=chk-p
        else:
            t=chk+p
        s=t
        cnt=0
        while t:
            if t not in c:
                pc=ppc(t)
                c[t]=pc
            else:
                pc=c[t]
            t%=pc
            cnt+=1
            if t in d:
                cnt+=d[t]
                break
        if s not in d:
            d[s]=cnt
        ans.append(cnt)
    for i in ans[::-1]:
        print(i)

if __name__=="__main__":
    sol()

Submission status: Runtime Error

Solution code:
def toggle_nth_bit(num: int, n: int):
    return num ^ (1 << n)


N = int(input())
X = input()
f = 0
count = 1
ans = 0
fi = 0
for i in range(N-1, -1, -1):
    fi = toggle_nth_bit(int(X, 2), i)
    f = bin(toggle_nth_bit(int(X, 2), i))
    ans = fi % f.count("1")
    while ans != 0:
        count += 1
        if ans == 1:
            break
        ans = ans % bin(ans).count("1")

    print(count)
    count = 1

Submission status: Runtime Error

Solution code:
n=int(input())
xs=input()
xk=list(map(int,list(xs)))
xj=xk.count(1)

x=int(xs,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 i in range(n-1,-1,-1):
    xi=x^(1<<i)
    pxi=xj
    if xs[i]==0:
        pxi=pxi-1
    if xi==0:
        print(0)
    else:
#    print(xi,popcount(xi),xi%popcount(xi))
        icnt=0
        while xi>0:
            icnt+=1
            xi=xi%popcount(xi)
    print(icnt)

Submission status: Runtime Error

Solution code:
import sys
input = lambda:sys.stdin.readline().rstrip()
from collections import defaultdict
sys.setrecursionlimit(10**9)

def solve(k, cnt):  
    S = str(bin(k)).count("1") 
    L = k % S
    if L == 0:
        return 1
    cnt += solve(L,cnt)
    return cnt 

N = int(input())
P = input()
Df = int(P,2)
for i in range(N-1):
    cnt = 1
    if P[i] == "1":
        tmp = Df - 2**(N-i-1)
    else:
        tmp = Df + 2**(N-i-1)    
    #print(tmp, bin(tmp))
    print(solve(tmp,cnt))
    
cnt = 1
if P[-1] == "1":
    tmp = Df - 1
else:
    tmp = Df + 1
print(solve(tmp,cnt))
#print(solve(N,cnt))

Submission status: Runtime Error

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

fn = dict()

def f(n, count):
    binary = list(bin(n))[2:]
    popcount = 0
    for b in binary:
        if b == '1':
            popcount += 1
    count += 1
    if n%popcount == 0:
        return count
    else:
        if n in fn:
            return fn[n]
        else:
            x = f(n%popcount, count)
            fn[n] = x
            return x

for i in range(N):
    X_i = X[:]
    if X_i[i] == '1':
        X_i[i] = '0'
    else:
        X_i[i] = '1'
    X_i = ''.join(X_i)
    n = int(X_i, 2)
    ans = f(n, 0)
    fn[n] = ans
    print(ans)
# print(fn)

Submission status: Runtime Error

Solution code:
def NumberOf1(n):
  return bin(n & 0xffffffff).count('1')

n = int(input())
st = input()
for i in range(n):
  if int(st[i]) == 0:
    num = int(st[:i]+'1'+st[i+1:],2)
    count = 0
    while num:
        s = NumberOf1(num)
        num = num%s
        count+=1
    print(count)
  elif int(st[i]) == 1:
    num = int(st[:i]+'0'+st[i+1:],2)
    count = 0
    while num:
        s = NumberOf1(num)
        num = num%s
        count+=1
    print(count)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
def main():
    n = int(input())
    x = input()
    x = '0b'+x

    x = int(x,0)
    m = bin(x).count('1')
    # print(x)

    a = x%(m-1)
    b = x%(m+1)
    # exit()

    ans = dict()
    tmp_a = 1
    tmp_b = 1
    xx = [None] * n

    for i in range(n):
        if (x >> i) &1:
            y = (a - tmp_a)%(m-1)
        else:
            y = (b+tmp_b)%(m+1)
        tmp_a *= 2
        tmp_a %= (m-1)
        tmp_b *= 2
        tmp_b %= (m+1)
        # print(tmp_a,tmp_b)

        # z = x ^ (1<<i) 
        # t = z
        # z %= bin(z).count('1')
        # # y = z
        # # print(t,z,y)

        cnt = 1
        c = y
        while y != 0:
            # if y in ans.keys():
            #     cnt += ans[y]
            #     break
            cnt += 1
            y = solve(y)
        ans[c] = cnt
        xx[i] = cnt
    
    for i in range(n-1,-1,-1):
        print(xx[i])

def solve(n):
    m = bin(n).count('1')
    return n%m

main()

Submission status: Runtime Error

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return map(int, sys.stdin.readline().split())
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())


def FLIST(n):
    res = [1]
    for i in range(1, n+1):
        res.append(res[i-1]*i % DVSR)
    return res


N = II()
ST = input()
ST = ST[::-1]

# NUM1 =
# NUM2 =
popcnt = 0

for i in range(N):
    popcnt += ST[i] == '1'

NUM1 = 0
NUM2 = 0
pop_1 = popcnt-1
pop_2 = popcnt+1
for i in range(N):
    if ST[i] == '1':
        if pop_1 >= 0:
            NUM1 += pow(2, i, pop_1)
            NUM1 %= pop_1
        if pop_2 <= N:
            NUM2 += pow(2, i, pop_2)
            NUM2 %= pop_2

# print(pop_1, pop_2)
# print(NUM1, NUM2)

for i in range(N):
    cnt = 1
    i = N-i-1
    if ST[i] == '1':
        # print("A")
        value = NUM1 - pow(2, i, pop_1)
        value %= pop_1
        while value:
            value %= bin(value).count("1")
            cnt += 1
        print(cnt)
    else:
        # print("B")
        value = NUM2 + pow(2, i, pop_2)
        value %= pop_2
        while value:
            value %= bin(value).count("1")
            cnt += 1
        print(cnt)

Submission status: Runtime Error

Solution code:
pop_ans = {}
f_ans = {}

def popcount(n):
    cnt = 0
    if n in pop_ans:
        return pop_ans[n]
    while True:
        answer = divmod(n, 2)
        if answer[1] == 1:
            cnt += 1
        n = answer[0]
        if n == 0:
            break
    pop_ans[n] = cnt
    return cnt

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

def toggle_nth_bit(num: int, n: int):
    return num ^ (1 << n)

N = int(input())
X = input()
x10 = int(X,2)
for i in reversed(range(N)):
    n = toggle_nth_bit(x10, i)
    print(f(n))

Submission status: Runtime Error

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

memo = {}

if N == 1:
    print(1)
    exit()


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 count_one(num):
    if num in memo:
        return memo[num]
    else:
        v = popcount(num)
        memo[num] = v
        return v


one_count = 0
for x in X:
    if x == '1':
        one_count += 1

for i in range(N):
    #print(' i : ' + str(i))
    ans = 0
    tmp = one_count
    if X[i] == '1':
        X[i] = '0'
        tmp -= 1
    else:
        X[i] = '1'
        tmp += 1
    base_10 = int(''.join(X), 2)
    while True:
        base_10 %= tmp
        ans += 1
        if base_10 == 0:
            print(ans)
            if X[i] == '1':
                X[i] = '0'
            else:
                X[i] = '1'
            break
        tmp = count_one(base_10)
        # print(tmp)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000000)

n = int(input())
x = input()
xx = int(x, 2)
value = [0, 1]
count_1 = x.count('1')
for i in range(2, 2 * (10 ** 5) + 1):
    ans = 1
    i = i % bin(i).count('1')
    value.append(ans + value[i])

for i in range(n):
    ttt = xx & pow(2, n - i - 1)
    if ttt > 0:
        t = xx - pow(2, n - i - 1)
        point = count_1 - 1
    else:
        t = xx + pow(2, n - i - 1)
        point = count_1 + 1
    ans = 1
    t = (t % point)
    print(ans + value[t])

Submission status: Runtime Error

Solution code:
from numba import njit

@njit('i8(i8)', cache=True)
def popcount(n):
    a = 0
    while n:
        a += n % 2
        n //= 2
    return a

@njit('i8(i8)', cache=True)
def fun(n):
    ops = 0
    while n:
        bits = popcount(n)
        n %= bits
        ops += 1
    return ops

def funwrap(n, pc):
    if n == 0:
        return 0
    return 1 + fun(n % pc)

n = int(input())
xs = list(map(int, input()))

from functools import reduce
sm = reduce(lambda x,y: x*2+y, xs)
pc = xs.count(1)

for i in range(n):
    xs[i] ^= 1
    df = 1 if xs[i] == 1 else -1
    pc += df

    dn = 0#1 << (n - (i + 1))
    smi = sm + dn * df

    print(funwrap(smi, pc))

    xs[i] ^= 1
    pc -= df

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
import numba
from numba import njit
i8 = numba.int64

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8, ), cache=True)
def popcount(n):
    ret = 0
    while n:
        ret += n & 1
        n >>= 1
    return ret


@njit((i8, ), cache=True)
def f(n):
    t = 0
    while n:
        t += 1
        n %= popcount(n)
    return t

@njit((i8[:],), cache=True)
def main(X):

    popX = X.sum()
    MOD1 = popX + 1
    MOD2 = popX - 1
    if popX == 1:
        MOD2 = 1
    pow1 = np.ones_like(X)
    pow2 = np.ones_like(X)
    for n in range(1, len(X)):
        pow1[n] = 2 * pow1[n - 1] % MOD1
        pow2[n] = 2 * pow2[n - 1] % MOD2

    X1, X2 = 0, 0
    for x in X:
        X1 = (2 * X1 + x) % MOD1
        X2 = (2 * X2 + x) % MOD2

    ans = np.empty(N, np.int64)
    for i in range(N):
        x = X[N - 1 - i]
        if x == 0:
            nxt = (X1 + pow1[i]) % (popX + 1)
            ans[i] = 1 + f(nxt)
        elif x == 1:
            if popX == 1:
                ans[i] = 0
            else:
                nxt = (X2 - pow2[i]) % (popX - 1)
                ans[i] = 1 + f(nxt)
    return ans[::-1]

N = int(readline())
X = np.array(list(read().rstrip()), np.int64) - ord('0')
ans = main(X)
print('\n'.join(map(str, ans.tolist())))

Submission status: Runtime Error

Solution code:
N=int(input())
Xl=list(map(int,list(input())))
#X=int(input())
#print(Xl)

def func(x):
  cnt=0
  while x>0:
    num1=0
    xcopy=x
    while xcopy:
      if xcopy&1:
        num1+=1
      xcopy>>=1
      
    #print(x,num1)
    x=x%num1
    cnt+=1
  return cnt

func_dic={}
for i in range(N+1):
  func_dic[i]=func(i)
#print(func_dic)

num1_X=Xl.count(1)
#print(num1_X)

mod_nminus=0
mod_nplus=0
for i in range(N):
  mod_nminus*=2
  mod_nplus*=2
  if Xl[i]==1:
    mod_nminus+=1
    mod_nplus+=1

  mod_nminus%=num1_X-1
  mod_nplus%=num1_X+1
#print(mod_nminus,mod_nplus)

answer_list=[]
modpow_plus=1
modpow_minus=1
for i in reversed(range(N)):
  if Xl[i]==0:
    mod=(mod_nplus+modpow_plus)%(num1_X+1)
    answer_list.append(func_dic[mod]+1)
  else:
    if num1_X-1==0:
      answer_list.append(0)
    else:
      mod=(mod_nminus-modpow_minus)%(num1_X-1)
      answer_list.append(func_dic[mod]+1)
  
  modpow_plus*=2  
  modpow_plus%=num1_X+1
  if num1_X-1>0:
    modpow_minus*=2
    modpow_minus%=num1_X-1
  
for i in reversed(range(N)):
  print(answer_list[i])

Submission status: Runtime Error

Solution code:
N = int(input())
#X = list(map(int, input().split()))
X = input()
#mapの処理 二進数の処理

#dp-problem
#fを帰納的に求める関数

#Xを求める
#反転してたす関数

dp = [-1] * (2**N)
dp[0] = 0

dp_c = [-1] * (2**N )
dp_c[0] = 0
dp_c[1] = 1
dp_c[2] = 1

##ボトムアップにするかどうか...
##ボトムダウンで行こう...
##dpはいつ0になるか

def count(a):
    if dp_c[a] == -1:
        dp_c[a] = a%2 + count(a//2)
    return dp_c[a]

def f(a,b):
    i = a
    j = b
    if j == 0:
        return 0
    if dp[i] == -1:
        if(dp[i%j] != -1):
            dp[i] = dp[i%j] + 1
        else:
            k = count(i%j)
            dp[i] = 1 + f(i%j,k)
    return dp[a]


for i in range(N):
    a = (int(X[i])+1)%2
    x = 0
    cou = 0
    for j in range(N):
        if j != i:
            x += int(X[j])*2**(N-1-j)
            if int(X[j]) == 1:
                cou += 1
        else:
            x += a*2**(N-1-j)
            if a == 1:
                cou += 1
    print(f(x,cou))