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 sys
read = sys.stdin.read
#readlines = sys.stdin.readlines
from collections import defaultdict

def main():
    def from10to2(p):
        res = []
        while p:
            p, t = divmod(p, 2)
            res.append(str(t))
        return "".join(res[::-1])

    def from2to10(p):
        res = 0
        num2 = 1
        for c in p[::-1]:
            if c == '1':
                res += num2
            num2 *= 2
        return res

    def f(p):
        if p == 0:
            return 0
        elif d1[p] > 0:
            return d1[p]
        else:
            ppop = from10to2(p).count('1')
            p2 = p % ppop
            fp = f(p2) + 1
            d1[p] = fp
            return fp

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

    numof1 = x.count('1')
    bin2 = [0] * n
    num2 = 1
    for i1 in range(1, n+1):
        bin2[-i1] = num2
        num2 = (num2 * 2) % numof1

    xas10 = from2to10(x)
    xas10 = xas10 % numof1
    d1 = defaultdict(int)
    d1[0] = 0
    for j1 in range(n):
        if x[j1] == '1':
            print(f(xas10 - bin2[j1]) + 1)
        else:
            print(f(xas10 + bin2[j1]) + 1)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.read
#readlines = sys.stdin.readlines
from collections import defaultdict

def main():
    def from10to2(p):
        res = []
        while p:
            p, t = divmod(p, 2)
            res.append(str(t))
        return "".join(res[::-1])

    def from2to10(p):
        res = 0
        num2 = 1
        for c in p[::-1]:
            if c == '1':
                res += num2
            num2 *= 2
        return res

    def f(p):
        if p == 0:
            return 0
        elif d1[p] > 0:
            return d1[p]
        else:
            ppop = from10to2(p).count('1')
            p2 = p % ppop
            fp = f(p2) + 1
            d1[p] = fp
            return fp

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

    bin2 = [0] * n
    num2 = 1
    for i1 in range(1, n+1):
        bin2[-i1] = num2
        num2 *= 2
    numof1 = x.count('1')
    xas10 = from2to10(x)
    d1 = defaultdict(int)
    d1[0] = 0
    for j1 in range(n):
        if x[j1] == '1':
            print(f((xas10 - bin2[j1]) % (numof1 - 1)) + 1)
        else:
            print(f((xas10 + bin2[j1]) % (numof1 + 1)) + 1)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
sn = input()
sr = ''.join(list(reversed(sn)))
sint = int(sn, 2)
spop = sn.count('1')

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



m1 = sint % (spop + 1)
m2 = 0 if spop <= 1 else sint % (spop - 1)

a = [0] * n
for i in range(n):
    if sr[i] == '0':
        d = pow(2, i, spop + 1)
        m = (m1 + d) % (spop + 1)
    else:
        d = pow(2, i, spop - 1)
        m = (m2 - d + spop - 1) % (spop - 1)
    a[i] = f(m) + 1

for ans in reversed(a):
    print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
sn = input()
sr = ''.join(list(reversed(sn)))
sint = int(sn, 2)
spop = sn.count('1')

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



m1 = sint % (spop + 1)
m2 = sint % (spop - 1)

a = [0] * n
for i in range(n):
    if sr[i] == '0':
        d = pow(2, i, spop + 1)
        m = (m1 + d) % (spop + 1)
    else:
        d = pow(2, i, spop - 1)
        m = (m2 - d + spop - 1) % (spop - 1)
    a[i] = f(m) + 1

for ans in reversed(a):
    print(ans)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10**8)

N = int(input())
X_ = input()
X = 0
for i, x in enumerate(X_[::-1]):
    X += 2 ** i * int(x)

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


def f(x):
    return x % bin(x).count('1')


def g(x):
    if Ans[x] != -1:
        return Ans[x]
    if f(x) == 0:
        Ans[x] = 1
        return 1
    y = g(f(x)) + 1
    Ans[x] = y
    return y


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

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10**100)

N = int(input())
X_ = input()
X = 0
for i, x in enumerate(X_[::-1]):
    X += 2 ** i * int(x)

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


def f(x):
    return x % bin(x).count('1')


def g(x):
    if Ans[x] != -1:
        return Ans[x]
    if f(x) == 0:
        Ans[x] = 1
        return 1
    y = g(f(x)) + 1
    Ans[x] = y
    return y


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

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10**8)

N = int(input())
X_ = input()
X = 0
for i, x in enumerate(X_[::-1]):
    X += 2 ** i * int(x)

Ans = [-1] * 2 ** N


def f(x):
    return x % bin(x).count('1')


def g(x):
    if Ans[x] != -1:
        return Ans[x]
    if f(x) == 0:
        Ans[x] = 1
        return 1
    y = g(f(x)) + 1
    Ans[x] = y
    return y


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

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10**6)

N = int(input())
X_ = input()
X = 0
for i, x in enumerate(X_[::-1]):
    X += 2 ** i * int(x)

Ans = [-1] * 2 ** N


def f(x):
    return x % bin(x).count('1')


def g(x):
    if Ans[x] != -1:
        return Ans[x]
    if f(x) == 0:
        Ans[x] = 1
        return 1
    y = g(f(x)) + 1
    Ans[x] = y
    return y


for i in range(N):
    x = int(X) ^ (1 << (N - i - 1))
    print(g(x))

Submission status: Runtime Error

Solution code:
# @uthor : Kaleab Asfaw
from sys import stdin, stdout
# Fast IO
def input():
	a = stdin.readline()
	if a[-1] == "\n": a = a[:-1]
	return a
def print(*argv, end="\n", sep=" "):
	n = len(argv)
	for i in range(n):
		if i == n-1: stdout.write(str(argv[i]))
		else: stdout.write(str(argv[i]) + sep)
	stdout.write(end)
# Others
mod = 10**9+7
def lcm(x, y): return (x * y) / (gcd(x, y))
def comb(lst, x):
	from itertools import combination as c
	return list(comb(lst, x))
def fact(x, mod=mod):
	ans = 1
	for i in range(1, x+1): ans = (ans * i) % mod
	return ans
def arr2D(n, m, default=0):
	lst = []
	for i in range(n): temp = [default] * m; lst.append(temp)
	return lst
def sortDictV(x): return {k: v for k, v in sorted(x.items(), key = lambda item : item[1])}
def smaller(lst, x): return bisect_left(lst, x) -1
def smallerEq(lst, x): return bisect_right(lst, x) -1

def CountBits(n):
  n = (n & 0x5555555555555555) + ((n & 0xAAAAAAAAAAAAAAAA) >> 1)
  n = (n & 0x3333333333333333) + ((n & 0xCCCCCCCCCCCCCCCC) >> 2)
  n = (n & 0x0F0F0F0F0F0F0F0F) + ((n & 0xF0F0F0F0F0F0F0F0) >> 4)
  n = (n & 0x00FF00FF00FF00FF) + ((n & 0xFF00FF00FF00FF00) >> 8)
  n = (n & 0x0000FFFF0000FFFF) + ((n & 0xFFFF0000FFFF0000) >> 16)
  n = (n & 0x00000000FFFFFFFF) + ((n & 0xFFFFFFFF00000000) >> 32) # This last & isn't strictly necessary.
  return n

def solve(n, lst):
	for i in range(n):
		num = int(("0b" + lst[:i] + str(1-int(lst[i])) + lst[i+1:]), 2)
		cnt = 0
		num1 = num
		while num1 != 0:
			c = CountBits(num1)
			num1 %= c
			cnt += 1
		print(cnt)



n = int(input())
lst = input()
solve(n, lst)

Submission status: Runtime Error

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

xl = list(x)
xl = [int(s) for s in xl]
m = sum(xl)
xi = int(x, 2)

ans = []
t = 1
d = {}
d[m+1] = xi % (m+1)
d[m-1] = xi % (m-1)
for i in range(n-1, -1, -1):
    if x[i] == '0':
        xx = (d[m+1] + t) % (m+1)
        
    else:
        xx = (d[m-1] - t) % (m-1)
    
    xxl = list(bin(xx)[2:])
    xxl = [int(s) for s in xxl]
    mm = sum(xxl)
    cnt = 1
    while xx:
        xx %= mm
        xxl = list(bin(xx)[2:])
        xxl = [int(s) for s in xxl]
        mm = sum(xxl)
        cnt += 1
    ans.append(cnt)
    t *= 2
ans.reverse()
for i in ans:
    print(i)

Submission status: Runtime Error

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし


N = I()
X = LI2()
X.reverse()

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

A = [0]*(2*10**5+1)  # Ai = f(i)
for i in range(1,2*10**5+1):
    k = 0
    for j in range(18):
        if (i >> j) & 1:
            k += 1
    A[i] = A[i % k] + 1


r = sum(X)  # Xの各桁の和

if r >= 2:
    B = [1] + [0]*(N-1)  # Bi = 2**i mod (r-1)
    C = [1] + [0]*(N-1)  # Ci = 2**i mod (r+1)
    b,c = 0,0  # b,c = X mod (r-1),X mod (r+1)
    for i in range(1,N):
        B[i] = (B[i-1]*2) % (r-1)
        C[i] = (C[i-1]*2) % (r+1)
        if X[i] == 1:
            b += B[i]
            b %= r-1
            c += C[i]
            c %= r+1

    for i in range(N-1,-1,-1):
        if X[i] == 0:
            print(1+A[(c+C[i]) % (r-1)])
        else:
            print(1+A[(b-B[i]) % (r+1)])

else:
    C = [1] + [0]*(N-1)  # Ci = 2**i mod (r+1)
    c = 0  # c = X mod (r+1)
    for i in range(1,N):
        C[i] = (C[i-1]*2) % (r+1)
        if X[i] == 1:
            c += C[i]
            c %= r+1

    for i in range(N-1,-1,-1):
        if X[i] == 0:
            print(1+A[(c+C[i]) % (r-1)])
        else:
            print(0)

Submission status: Runtime Error

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし


N = I()
X = LI2()
X.reverse()

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

A = [0]*(2*10**5+1)  # Ai = f(i)
for i in range(1,2*10**5+1):
    k = 0
    for j in range(18):
        if (i >> j) & 1:
            k += 1
    A[i] = A[i % k] + 1


r = sum(X)  # Xの各桁の和

if r >= 2:
    B = [1] + [0]*(N-1)  # Bi = 2**i mod (r-1)
    C = [1] + [0]*(N-1)  # Ci = 2**i mod (r+1)
    b,c = 0,0  # b,c = X mod (r-1),X mod (r+1)
    for i in range(N):
        B[i] = (B[i-1]*2) % (r-1)
        C[i] = (C[i-1]*2) % (r+1)
        if X[i] == 1:
            b += B[i]
            b %= r-1
            c += C[i]
            c %= r+1

    for i in range(N-1,-1,-1):
        if X[i] == 0:
            print(1+A[(c+C[i]) % (r-1)])
        else:
            print(1+A[(b-B[i]) % (r+1)])

else:
    C = [1] + [0]*(N-1)  # Ci = 2**i mod (r+1)
    c = 0  # c = X mod (r+1)
    for i in range(N):
        C[i] = (C[i-1]*2) % (r+1)
        if X[i] == 1:
            c += C[i]
            c %= r+1

    for i in range(N-1,-1,-1):
        if X[i] == 0:
            print(1+A[(c+C[i]) % (r-1)])
        else:
            print(0)

Submission status: Runtime Error

Solution code:
def pc(x):
    cnt = 0
    for i in range(len(x)):
        if x[i]=="1":
            cnt += 1
    return cnt
def f(n,j):
    if n==0:
        return 0
    cnt = 1
    n = n%j
    y = bin(n)[2:]
    while n%pc(y)!=0:
        cnt += 1
        n = n%pc(y)
        y = bin(n)[2:]
    return cnt+1
N = int(input())
X = input().strip()
k = 0
for i in range(N):
    if X[i]=="1":
        k += 1
n = int(X,2)
for i in range(N):
    if X[i]=="0":
        m = n+2**(N-1-i)
        j = k+1
    else:
        m = n-2**(N-1-i)
        j = k-1
    print(f(m,j))

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
A = [A[i]-(i+1) for i in range(N)]
A = sorted(A)
C = {}
for i in range(N):
    a = A[i]
    if a not in C:
        C[a] = 0
    C[a] += 1
def f(x):
    if x==0:
        return 0
    cnt = 0
    for a in C:
        cnt += abs(x-a)*C[a]
    return cnt
l = A[0]
r = A[-1]
y1 = f(l)
while r>l:
    midl = (2*l+r)//3
    midr = (l+2*r)//3
    B = sorted([(l,f(l)),(midl,f(midl)),(midr,f(midr)),(r,f(r))],key=lambda x:x[1])
    x1,y1 = B[0]
    x2,y2 = B[1]
    if x1>x2:
        r = x1
        l = x2
    else:
        r = x2
        l = x1
print(y1)

Submission status: Runtime Error

Solution code:
def pc(x):
    cnt = 0
    for i in range(len(x)):
        if x[i]=="1":
            cnt += 1
    return cnt
def f(n):
    y = bin(n)[2:]
    cnt = 0
    while n%pc(y)!=0:
        cnt += 1
        n = n%pc(y)
        y = bin(n)[2:]
    return cnt+1
N = int(input())
X = input().strip()
n = int(X,2)
for i in range(N):
    if X[i]=="0":
        m = n+2**(N-1-i)
    else:
        m = n-2**(N-1-i)
    print(f(m))

Submission status: Runtime Error

Solution code:
'''
Created on 2020/09/03
 
@author: harurun
'''
def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write
 
  N=int(pin())
  X=pin()
  dp=[-1]*(3**(N+1))
 
  for i in range(N):
    u="1"
    if X[i]=="1":
      u="0"
    S=""
    try:
      S=X[:i]+u+X[i+1:]
    except:
      S=X[:i]+u
    Y=int(S,2)
    cnt=0
    while Y>0:
      c=1
      if dp[Y-1]==-1:
        c=str(bin(int(Y))).count("1")
        dp[Y-1]=c
      else:
        c=dp[Y-1]
      Y=Y%c
      cnt+=1
    print(cnt)
  return
main()

Submission status: Runtime Error

Solution code:
'''
Created on 2020/09/03

@author: harurun
'''
def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write

  N=int(pin())
  X=pin()
  dp=[-1]*(2**(N+1))

  for i in range(N):
    u="1"
    if X[i]=="1":
      u="0"
    S=""
    try:
      S=X[:i]+u+X[i+1:]
    except:
      S=X[:i]+u
    Y=int(S,2)
    cnt=0
    while Y>0:
      c=1
      if dp[Y-1]==-1:
        c=str(bin(int(Y))).count("1")
        dp[Y-1]=c
      else:
        c=dp[Y-1]
      Y=Y%c
      cnt+=1
    print(cnt)
  return
main()

Submission status: Runtime Error

Solution code:
'''
Created on 2020/09/03

@author: harurun
'''
def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write

  N=int(pin())
  X=pin()
  dp=[-1]*(2**N)

  for i in range(N):
    u="1"
    if X[i]=="1":
      u="0"
    S=X[:i]+u
    if i!=N-1:
      S+=X[i+1:]
    Y=int(S,2)
    cnt=0
    while Y>0:
      c=1
      if dp[Y-1]==-1:
        c=str(bin(int(Y))).count("1")
        dp[Y-1]=c
      else:
        c=dp[Y-1]
      Y=Y%c
      cnt+=1
    print(cnt)
  return 
main()

Submission status: Runtime Error

Solution code:
from functools import lru_cache


def popcnt(x):
    return bin(x).count("1")


@lru_cache(maxsize=None)
def rec(n):
    if n == 0:
        return 0
    else:
        return rec(n % popcnt(n)) + 1


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

# 事前計算
cnt = popcnt(arr)
init_big = x % (cnt + 1)
if cnt == 1:
    init_small = 0
else:
    init_small = x % (cnt - 1)

# 差分計算
result = []
for i in range(n):
    if not (x >> i) & 1:
        result.append((init_big + pow(2, i, cnt + 1)) % (cnt + 1))
    elif arr == 1 << i or cnt - 1 == 0:
        result.append(0)
    else:
        result.append((init_small - pow(2, i, cnt - 1)) % (cnt - 1))

ans = []
for x in result[::-1]:
    ans.append(rec(x) + 1)

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

Submission status: Runtime Error

Solution code:
n=int(input())
x=list(map(int,list(input())))
def popcount(x):
  ret=0
  while x:
    if x%2==1:ret+=1
    x//=2
  return ret
def f(x):
  ret=0
  while x:
    x%=popcount(x)
    ret+=1
  return ret
from collections import Counter
xpop=Counter(x)[1]
xint_mi,xint_pl=0,0
for i,y in enumerate(x):
  xint_mi+=(pow(2,n-i-1,xpop-1)*y)%(xpop-1)
  xint_mi%=(xpop-1)
  xint_pl+=(pow(2,n-i-1,xpop+1)*y)%(xpop+1)
  xint_pl%=(xpop+1)


for i,y in enumerate(x):
  if y:
    yint=xint_mi-pow(2,n-i-1,xpop-1)
    ypop=xpop-1
    yint%=ypop
  else:
    yint=xint_pl+pow(2,n-i-1,xpop+1)
    ypop=xpop+1
    yint%=ypop
  #print(yint,ypop)
  print(f(yint)+1)

Submission status: Runtime Error

Solution code:
n=int(input())
x=list(map(int,list(input())))
def popcount(x):
  ret=0
  while x:
    if x%2==1:ret+=1
    x//=2
  return ret
def f(x):
  ret=0
  while x:
    x%=popcount(x)
    ret+=1
  return ret
from collections import Counter
xpop=Counter(x)[1]

xint_mi=sum([(pow(2,n-i-1,xpop-1)*y)%(xpop-1) for i,y in enumerate(x)])
xint_pl=sum([(pow(2,n-i-1,xpop+1)*y)%(xpop+1) for i,y in enumerate(x)])

for i,y in enumerate(x):
  if y:
    yint=xint_mi-pow(2,n-i-1,xpop-1)
    ypop=xpop-1
    yint%=ypop
  else:
    yint=xint_pl+pow(2,n-i-1,xpop+1)
    ypop=xpop+1
    yint%=ypop
  #print(yint,ypop)
  print(f(yint)+1)

Submission status: Runtime Error

Solution code:
n=int(input())
x=list(map(int,list(input())))
def popcount(x):
  ret=0
  while x:
    if x%2==1:ret+=1
    x//=2
  return ret
def f(x):
  ret=0
  while x:
    x%=popcount(x)
    ret+=1
  return ret
from collections import Counter
xpop=Counter(x)[1]

xint_mi=sum([(pow(2,n-i-1,xpop-1,xpop-1)*y)%(xpop-1) for i,y in enumerate(x)])
xint_pl=sum([(pow(2,n-i-1,xpop+1,xpop+1)*y)%(xpop+1) for i,y in enumerate(x)])

for i,y in enumerate(x):
  if y:
    yint=xint_mi-pow(2,n-i-1)
    ypop=xpop-1
    yint%=ypop
  else:
    yint=xint_pl+pow(2,n-i-1)
    ypop=xpop+1
    yint%=ypop
  #print(yint,ypop)
  print(f(yint)+1)

Submission status: Runtime Error

Solution code:
n=int(input())
x=list(map(int,list(input())))
def popcount(x):
  ret=0
  while x:
    if x%2==1:ret+=1
    x//=2
  return ret
def f(x):
  ret=0
  while x:
    x%=popcount(x)
    ret+=1
  return ret
from collections import Counter
xpop=Counter(x)[1]

xint_mi=sum([(pow(2,n-i-1,xpop-1)*y)%(xpop-1) for i,y in enumerate(x)])
xint_pl=sum([(pow(2,n-i-1,xpop+1)*y)%(xpop+1) for i,y in enumerate(x)])

for i,y in enumerate(x):
  if y:
    yint=xint_mi-pow(2,n-i-1)
    ypop=xpop-1
    yint%=ypop
  else:
    yint=xint_pl+pow(2,n-i-1)
    ypop=xpop+1
    yint%=ypop
  #print(yint,ypop)
  print(f(yint)+1)

Submission status: Runtime Error

Solution code:
n=int(input())
x=list(map(int,list(input())))
def popcount(x):
  ret=0
  while x:
    if x%2==1:ret+=1
    x//=2
  return ret
def f(x):
  ret=0
  while x:
    x%=popcount(x)
    ret+=1
  return ret
from collections import Counter
xpop=Counter(x)[1]
xint=sum([pow(2,n-i-1)*y for i,y in enumerate(x)])
for i,y in enumerate(x):
  if y:
    yint=xint-pow(2,n-i-1)
    ypop=xpop-1
  else:
    yint=xint+pow(2,n-i-1)
    ypop=xpop+1
  #print(yint,ypop)
  yint%=ypop
  print(f(yint)+1)

Submission status: Runtime Error

Solution code:
def solve(x):
    cnt = 1
    while x > 0:
        count = 0
        y = x
        while y > 0:
            count += (y%2==1)
            y >>= 1
        x %= count
        cnt += 1
    return cnt

n = int(input())
x = input()
one = x.count('1')
num = int(x, 2)

up = num%(one+1)
down = num%(one-1)

for i in range(n):
    if x[i] == '1':
        if one == 1:
            print(0)
            continue
        s = down - (2**(n-i-1))%(one-1)
        if s < 0:
            s += one-1
    else:
        s = (up + (2**(n-i-1))%(one+1))%(one+1)
    print(solve(s))

Submission status: Runtime Error

Solution code:
N=int(input())
X=input()
num_X = int(X, base=2)
pop_x = X.count("1")
mod1 = pop_x - 1
mod0 = pop_x + 1
res1 = num_X % (mod1)
res0 = num_X % (mod0)

# pops = [0]*(N+20)
for i in range(N):
    tmp = 0
    if X[i] == "0":
        # +
        tmp = (res0 + pow(2, N-i-1, mod0))%mod0
    else:
        tmp = (res1 - pow(2, N-i-1, mod1))%mod1
    
    if tmp == 0:
        print(1)
        continue
    cnt = 1
    while tmp != 0:
        pop = bin(tmp).count("1")
        tmp %= pop
        cnt += 1
    print(cnt)

Submission status: Runtime Error

Solution code:
N=int(input())
X=input()
num_X = int(X, base=2)
pop_x = X.count("1")
mod1 = pop_x - 1
mod0 = pop_x + 1
res1 = num_X % (mod1)
res0 = num_X % (mod0)

pops = [0]*(N+20)
for i in range(N):
    tmp = 0
    if X[i] == "0":
        # +
        tmp = (res0 + pow(2, N-i-1, mod0))%mod0
    else:
        tmp = (res1 - pow(2, N-i-1, mod1))%mod1
    
    if tmp == 0:
        print(1)
        continue
    cnt = 1
    while tmp != 0:
        if not pops[tmp]:
            pop = bin(tmp).count("1")
            pops[tmp] = pop
        else:
            pop = pops[tmp]

        tmp %= pop
        cnt += 1
    print(cnt)

Submission status: Runtime Error

Solution code:
N=int(input())
X=input()
num_X = int(X, base=2)
pop_xi = [0]*N
pop_x = X.count("1")
X_pop_res = [0]*N

mod1 = pop_x - 1
mod0 = pop_x + 1
res1 = num_X % (mod1)
res0 = num_X % (mod0)

# for i in range(N):
#     if X[i]=="1":
#         pop_xi[i] = mod1
#         X_pop_res[i] = res1
#     else:
#         pop_xi[i] = mod0
#         X_pop_res[i] = res0
pops = [0]*(N+20)
for i in range(N):
    tmp = 0
    if X[i] == "0":
        # +
        tmp = (res0 + pow(2, N-i-1, mod0))%mod0
    else:
        tmp = (res1 - pow(2, N-i-1, mod1))%mod1
    
    if tmp == 0:
        print(1)
        continue
    cnt = 1
    while tmp != 0:
        if not pops[tmp]:
            pop = bin(tmp).count("1")
        else:
            pop = pops[tmp]

        tmp %= pop
        cnt += 1
    print(cnt)

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
N=int(input())
X=list(input())

ones=X.count("1")
high=ones+1
low=ones-1

mod_h=[1]
mod_l=[1]
for i in range(N-1):
    mod_h.append((mod_h[-1]*2)%high)
    mod_l.append((mod_l[-1]*2)%low)

mod_h=mod_h[::-1]
mod_l=mod_l[::-1]

ans_high=0
for i in range(N):
    if X[i] == "1":
        ans_high+=mod_h[i]
ans_high%=high

ans_low=0
for i in range(N):
    if X[i] == "1":
        ans_low+=mod_l[i]
ans_low%=low
        
for i in range(N):
    if X[i]=="0":
        ans=ans_high
        #high_root
        """
        temp=X[:]
        temp[i]="1"
        for j in range(len(temp)):
            if temp[j] == "1":
                ans+=mod_h[j]
        """
        ans+=mod_h[i]
        ans%=high
    else:
        ans=ans_low
        """
        temp=X[:]
        temp[i]="0"
        for j in range(len(temp)):
            if temp[j] == "1":
                ans+=mod_l[j]
        """
        ans-=mod_l[i]
        ans%=low
    
    count=1
    while ans!=0:
        ans=ans%(bin(ans).count("1"))
        count+=1
    
    print(count)

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
N=int(input())
X=list(input())

ones=X.count("1")
high=ones+1
low=ones-1

mod_h=[1]
mod_l=[1]
for i in range(N-1):
    mod_h.append((mod_h[-1]*2)%high)
    mod_l.append((mod_l[-1]*2)%low)

mod_h=mod_h[::-1]
mod_l=mod_l[::-1]
X_10=sum([2**i*int(X[N-i-1]) for i in range(N)])

for i in range(N):
    ans=X_10
    if X[i]=="0":
        #high_root
        """
        temp=X[:]
        temp[i]="1"
        for j in range(len(temp)):
            if temp[j] == "1":
                ans+=mod_h[j]
        """
        ans+=mod_h[i]
        ans%=high
    else:
        """
        temp=X[:]
        temp[i]="0"
        for j in range(len(temp)):
            if temp[j] == "1":
                ans+=mod_l[j]
        """
        ans-=mod_l[i]
        ans%=low
    
    count=1
    while ans!=0:
        ans=ans%(bin(ans).count("1"))
        count+=1
    
    print(count)

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
N=int(input())
X=list(input())

ones=X.count("1")
high=ones+1
low=ones-1

mod_h=[1]
mod_l=[1]
for i in range(N-1):
    mod_h.append((mod_h[-1]*2)%high)
    mod_l.append((mod_l[-1]*2)%low)

mod_h=mod_h[::-1]
mod_l=mod_l[::-1]

for i in range(N):
    ans=0
    if X[i]=="0":
        #high_root
        temp=X[:]
        temp[i]="1"
        for j in range(len(temp)):
            if temp[j] == "1":
                ans+=mod_h[j]
        ans%=high
    else:
        temp=X[:]
        temp[i]="0"
        for j in range(len(temp)):
            if temp[j] == "1":
                ans+=mod_l[j]
        ans%=low
    
    count=1
    """
    while ans!=0:
        ans=ans%(bin(ans).count("1"))
        count+=1
    """
    print(count)

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
N=int(input())
X=list(input())

ones=X.count("1")
high=ones+1
low=ones-1

mod_h=[1]
mod_l=[1]
for i in range(N-1):
    mod_h.append((mod_h[-1]*2)%high)
    mod_l.append((mod_l[-1]*2)%low)

mod_h=mod_h[::-1]
mod_l=mod_l[::-1]

for i in range(N):
    ans=0
    if X[i]=="0":
        #high_root
        temp=X[:]
        temp[i]="1"
        for j in range(len(temp)):
            if temp[j] == "1":
                ans+=mod_h[j]
        ans%=high
    else:
        temp=X[:]
        temp[i]="0"
        for j in range(len(temp)):
            if temp[j] == "1":
                ans+=mod_l[j]
        ans%=low
    """
    count=1
    while ans!=0:
        ans=ans%(bin(ans).count("1"))
        count+=1
    """
    print(count)

Submission status: Runtime Error

Solution code:
N = int(input())
S = str(input())
X = [];Bit = 0;Num = 0
for i in range(N):
  if S[i] == "1":
    Bit += 1
    Num += pow(2,N-1-i)
  X.append(int(S[i]))
#print(X)
#print(Num)
MAX = 2*pow(10,5)+10
small = [-1 for _ in range(MAX)]
small[0] = 0; small[1] = 1; small[2] = 1; small[3] = 2
for i in range(4,MAX):
  ret = 0; target = i*1
  while i > 0:
    cnt = 0
    for j in range(i.bit_length()):
      if (i>>j)&1 == 1:
        cnt += 1
    i = i%cnt
    #print(i,target,cnt)
    ret += 1
    if small[i] != -1:
      ret += small[i]
      break

  small[target] = ret
#print(small)
Numm = Num%(Bit-1)
Nump = Num%(Bit+1)
#print(Num)
ans = []
for i in range(N):
  keta = N-1-i
  if X[i] == 1:
    btemp = Bit -1
    temp = (Numm - pow(2,keta,btemp))%btemp
  else:
    btemp = Bit +1
    temp = (Nump + pow(2,keta,btemp))%btemp
  ret = small[temp] + 1 #最初の一回
  ans.append(ret)
print(*ans,sep="\n")

Submission status: Runtime Error

Solution code:
N = int(input())
S = str(input())
X = [];Bit = 0
for i in range(N):
  if S[i] == "1":
    Bit += 1
  X.append(int(S[i]))
#print(X)
MAX = 21
small = [-1 for _ in range(MAX)]
small[0] = 0; small[1] = 1; small[2] = 1; small[3] = 2
for i in range(4,MAX):
  ret = 0; target = i*1
  while i > 0:
    cnt = 0
    for j in range(i.bit_length()):
      if (i>>j)&1 == 1:
        cnt += 1
    i = i%cnt
    #print(i,target,cnt)
    ret += 1
    if small[i] != -1:
      ret += small[i]
      break

  small[target] = ret
#print(small)
Num = int(S, 2)
#print(Num)
ans = []
for i in range(N):
  keta = N-1-i
  if X[i] == 1:
    temp = Num - pow(2,keta)
    btemp = Bit -1 
  else:
    temp = Num + pow(2,keta)
    btemp = Bit + 1
  nokori = temp%btemp
  ret = small[nokori] + 1 #最初の一回
  ans.append(ret)
print(*ans,sep="\n")

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


N = I()
X = LI2()
X.reverse()


def popcount(n):
    res = 0
    m = n.bit_length()
    for i in range(m):
        res += (n >> i) & 1
    return res


F = [0]*(2*10**5)
for i in range(1,2*10**5):
    F[i] = 1 + F[i % popcount(i)]

a = sum(X)
b = a-1
c = a+1
if a == 1:
    A, C = [1], [1]  # 2冪をa,b,cで割った余り
    xa, xc = 0, 0  # Xをa,b,cで割った余り
    for i in range(N):
        if X[i] == 1:
            xa += A[-1]
            xc += C[-1]
            xa %= a
            xc %= c
        A.append((2 * A[-1]) % a)
        C.append((2 * C[-1]) % c)

    ANS = []
    for i in range(N):
        if X[i] == 1:
            ANS.append(0)
        else:
            ANS.append(1 + F[(xc + C[i]) % c])

    ANS.reverse()
    print(*ANS, sep='\n')
    exit()

A,B,C = [1],[1],[1]  # 2冪をa,b,cで割った余り
xa,xb,xc = 0,0,0  # Xをa,b,cで割った余り
for i in range(N):
    if X[i] == 1:
        xa += A[-1]
        xb += B[-1]
        xc += C[-1]
        xa %= a
        xb %= b
        xc %= c
    A.append((2*A[-1])%a)
    B.append((2*B[-1])%b)
    C.append((2*C[-1])%c)

ANS = []
for i in range(N):
    if X[i] == 1:
        ANS.append(1 + F[(xb-B[i]) % b])
    else:
        ANS.append(1 + F[(xc+C[i]) % c])

ANS.reverse()
print(*ANS,sep='\n')

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
N=int(input())
X=list(input())

ones=X.count("1")
high=ones+1
low=ones-1

mod_h=[1]
mod_l=[1]
for i in range(N-1):
    mod_h.append((mod_h[-1]*2)%high)
    mod_l.append((mod_l[-1]*2)%low)

mod_h=mod_h[::-1]
mod_l=mod_l[::-1]

for i in range(N):
    ans=0
    if X[i]=="0":
        #high_root
        temp=X[:]
        temp[i]="1"
        for j in range(len(temp)):
            if temp[j] == "1":
                ans+=mod_h[j]
        ans%=high
    else:
        temp=X[:]
        temp[i]="0"
        for j in range(len(temp)):
            if temp[j] == "1":
                ans+=mod_l[j]
        ans%=low
    
    count=1
    while ans!=0:
        ans=ans%(bin(ans).count("1"))
        count+=1
    
    print(count)

Submission status: Runtime Error

Solution code:
def f(n):
  if n==0:return 0
  else:return f(pc[n])+1
n=int(input())
x=input()
pc=[0]
m=10**5
for i in range(1,m+1):
  cnt=0
  j=i
  while i:
    cnt+=i%2
    i//=2
  pc+=[j%cnt]
cnt=x.count('1')
ix=int(x,2)
d=2**(n-1)
for i in range(n):
  if x[i]=='0':print(f((ix+d)%(cnt+1))+1)
  else:
    if ix-d>m:print(f((ix-d)%(cnt-1))+1)
    else:print(f(ix-d))
  d//=2