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()
popcount_x = x.count("1")
popcount_x1 = popcount_x + 1
popcount_x2 = popcount_x - 1


div1 = [0]*n
div2 = [0]*n
cur1 = 1
cur2 = 1
for i in range(n):
    cur1 %= popcount_x1
    cur2 %= popcount_x2
    div1[i] = cur1
    div2[i] = cur2
    cur1 *= 2
    cur2 *= 2


fn = [0]*n
for i in range(1,n):
    popcount = bin(i)[2:].count("1")
    fn[i] = fn[(i)%popcount] + 1

    
x_div1 = sum(int(x[i]) * div1[-i-1] for i in range(n)) % popcount_x1
x_div2 = sum(int(x[i]) * div2[-i-1] for i in range(n)) % popcount_x2

for i in range(n):
    if x[i] == "0": 
        xi_div = (x_div1 + div1[-i-1]) % popcount_x1
        print(fn[xi_div] + 1)
    else:
        xi_div = (x_div2 - div2[-i-1]) % popcount_x2
        print(fn[xi_div] + 1)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

def popcount(n):
    c = 0
    for i in range(64):
        c += (n >> i) & 1
    return c

N = int(input())
Xstr = input()

X = 0
for i in range(len(Xstr)):
    if(Xstr[i]=='1'):
        X = X*2+1
    else:
        X = X*2

p = popcount(X)
    
for i in range(len(Xstr)):
    if(Xstr[i] == '0'):
        T = X + (1<<(N-i-1))
        pp = p+1
    else:
        T = X - (1<<(N-i-1))
        pp = p-1

    
    ans = 1
    T = T % pp
    while(T>0):
        T = T % popcount(T)
        ans = ans+1
    print(ans)

Submission status: Runtime Error

Solution code:
import collections
n = int(raw_input())
x = int(raw_input(),2)
def f(x):
	cc=  collections.Counter(bin(x))
	
	if x % cc['1'] == 0:
		return 1
	return 1 + f(x % cc['1'])
for i in range(n)[::-1]:
	print f(x ^ (1 << i))

Submission status: Runtime Error

Solution code:
def find(x,ones):
    total = 0
    n = len(x)
    for i in range(n):
        total += int(x[i])*pow(2,n-i-1,ones)
        total %= ones

    return total

def solve(x,mod):
    x %= mod
    moves = 1
    while x != 0:
        x = x%(bin(x)[2:].count('1'))
        moves += 1

    return moves

def main():
    n = int(input())
    x = input()
    ones = x.count('1')
    less = find(x,ones-1)
    more = find(x,ones+1)
    for i in range(n):
        if x[i] == '0':
            print(solve(more+pow(2,n-i-1,ones+1),ones+1))
        else:
            print(solve(less-pow(2,n-i-1,ones-1),ones-1))


main()

Submission status: Runtime Error

Solution code:
import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def popcount(x):
    x = x - ((x >> 1) & 0x55555555)
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    return x & 0x0000007f

def solve():
    n = ni()
    X = list(map(int, list(ns())))
    p = sum(X)
    pl, ps = p+1, p-1
    g = [-1] * (n+1)
    g[0] = 0
    for i in range(1, n+1):
        g[i] = g[i % popcount(i)] + 1
    ql = qs = 0
    for x in X:
        ql = (ql * 2 + x) % pl
        qs = (qs * 2 + x) % ps
    vl = vs = 1
    ans = [0]*n
    for i in range(n-1, -1, -1):
        if X[i]:
            ans[i] = g[(qs-vs)%ps] + 1
        else:
            ans[i] = g[(ql+vl)%pl] + 1
        vs = vs * 2 % ps
        vl = vl * 2 % pl
    prn(ans)
    return

solve()

Submission status: Runtime Error

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

N = int(input())
S = input().rstrip()

num = S.count('1')

n1 = num + 1
n2 = num - 1

start1 = 0
start2 = 0
pow1 = [1]
pow2 = [1]
for i in range(N):
    s = int(S[-1-i])
    start1 = (start1 + pow1[-1] * s) % n1
    start2 = (start2 + pow2[-1] * s) % n2
    pow1.append(pow1[-1] * 2 % n1)
    pow2.append(pow2[-1] * 2 % n2)


def count(m):
    ret = 1
    while m != 0:
        k = bin(m).count("1")
        m %= k
        ret += 1
    return ret
    


ans = []
for i in range(N):
    s = int(S[i])
    if s == 0:
        l = (start1 + pow1[-i-2]) % n1
        ans.append(count(l))
    else:
        l = (start2 - pow2[-i-2]) % n2
        ans.append(count(l))

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

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
S = list(map(int, list(input())[: -1]))
pp = sum(S)
Xp = 0
Xm = 0
S.reverse()
for i in range(N):
  Xp += pow(2, i, pp + 1) * S[i]
  Xp %= pp + 1
  Xm += pow(2, i, pp - 1) * S[i]
  Xm %= pp - 1
#print(Xp, Xm)
rres = [0] * N
for i in range(N):
  res = 1
  if S[i]:
    X = (Xm - pow(2, i, pp - 1)) % (pp - 1)
    while X:
      c = bin(X).count("1")
      X %= c
      res += 1
  else:
    X = (Xp + pow(2, i, pp + 1)) % (pp + 1)
    while X:
      c = bin(X).count("1")
      X %= c
      res += 1
  rres[i] = res
rres.reverse()
for r in rres: print(r)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
#pyrival orz
import os
import sys
from io import BytesIO, IOBase

"""
    for _ in range(int(input())):
    n,m=map(int,input().split())
    n=int(input())
    a = [int(x) for x in input().split()]
"""

def main():
    from functools import lru_cache

    @lru_cache(None)
    def solve(n):
        if n==0:
            return 0
        c=bin(n).count('1')
        return 1+solve(n%c)
    n=int(input())
    s=input()
    ct=s.count('1')
    p,g=1,0

    mod=1
    if ct>=1:
        mod*=ct-1
    mod*=ct+1
    for x in s:
        g*=2
        if x=='1':
            g+=1
        g%=mod

    s=s[::-1]
    ans=[0]*len(s)
    for i,x in enumerate(s):
        p%=mod
        if x=='1':
            if ct==1:
                p*=2
                continue
            else:
                ans[i]=1+solve((g-p)%(ct-1))
        else:
            ans[i]=1+solve((g+p)%(ct+1))
        p*=2
    ans=ans[::-1]
    for x in ans:
        print(x)
# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

original_pop_count = x.count('1')
one_pop_count = original_pop_count - 1
zero_pop_count = original_pop_count + 1

one_mod = 0
zero_mod = 0
for b in x:
    one_mod = (one_mod * 2 + int(b)) % one_pop_count
    zero_mod = (zero_mod * 2 + int(b)) % zero_pop_count


#f の前計算

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

#pow2 の前計算
one_pow2 = [1] * 220000
zero_pow2 = [1] * 220000
for i in range(1, 220000):
    one_pow2[i] = one_pow2[i-1] * 2 % one_pop_count
    zero_pow2[i] = zero_pow2[i-1] * 2 % zero_pop_count
    
# n-1, n-2, ,, 0
for i in range(n-1, -1, -1):
    if x[n-1-i] == '1':
        nxt = one_mod
        #todo
        nxt -= one_pow2[i]
        nxt %= one_pop_count
        print(f[nxt] + 1)
    if x[n-1-i] == '0':
        nxt = zero_mod
        #todo
        nxt += zero_pow2[i]
        nxt %= zero_pop_count
        print(f[nxt] + 1)

Submission status: Runtime Error

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    X = input().rstrip('\n')

    M = X.count("1")
    x_major = 0
    x_minor = 0
    for i in range(N):
        add = int(X[i])
        x_major = (x_major * 2 + add)%(M+1)
        x_minor = (x_minor * 2 + add)%(M-1)
    for i in range(N):
        if X[i] == "1":
            val = (x_minor - pow(2, N-i-1, M-1)) % (M-1)
        else:
            val = (x_major + pow(2, N-i-1, M+1)) % (M + 1)
        cnt = 1
        while val:
            val = val % bin(val).count("1")
            cnt += 1
        print(cnt)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def popcount(n):
    return str(bin(n)).count('1')
def f(n):
    if n==0:
        return 0
    else:
        return f(n%popcount(n))+1
N=int(input())
X=input()
K=X.count("1")
#k桁目がone,zeroのとき
ONE=0#K-1
ZERO=0#K+1
tmp1=1
tmp0=1
for i in range(N):
    if X[-i-1]=="1":
        ONE+=tmp1
        ONE%=(K-1)
        ZERO+=tmp0
        ZERO%=(K+1)
    tmp1*=2
    tmp1%=(K-1)
    tmp0*=2
    tmp0%=(K+1)
for i in range(N):
    nextnumber=-1
    if X[i]=="1":
        nextnumber=(ONE-pow(2,N-i-1,K-1))%(K-1)
    else:
        nextnumber=(ZERO+pow(2,N-i-1,K+1))%(K+1)
    print(f(nextnumber)+1)

Submission status: Runtime Error

Solution code:
N=int(input())
x=input()
num=0
n=0
ans=[]
def twice(a):
    num=a
    b=0
    while a>0:
        b+=a%2
        a=a//2
    num=num%b
    return num
for i in range(N):
    num+=2**(N-i)*int(x[i])
    if x[i]=="1":
        n+=1
for i in range(N):
    Ans=0
    if x[i]=="0":
        n+=1
        A=2**(N-i)+num
        a=A%n
        Ans+=1
        while a>0:
            a=twice(a)
            Ans+=1
    else:
        n-=1
        A=num-2**(N-i)
        a=A%n
        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:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from scipy.sparse.csgraph import floyd_warshall
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations, combinations_with_replacement
from heapq import heappop, heappush, heapify
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def main():
    n = int(input())
    x = list(input())
    for i in range(n):
        x[i] = int(x[i])
    for i in range(n):
        y = copy.deepcopy(x)
        y[i] = 1-y[i]
        ans = 1
        while True:
            A = 0
            B = sum(y)
            for i in range(len(y)):
                A += y[i]*pow(2,len(y)-i-1)
            k = A%B
            if k == 0:
                break
            ans += 1
            yy = []
            while k != 0:
                yy.append(k%2)
                k //= 2
            yy.reverse()
            y = yy
        print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:

n = int(input())
s=input()
p=0
for i in range(n):
    if s[i]=='1':
        p+=2**(n-i-1)
for i in range(n):
    k=p
    if s[i]=='0':
        k+=2**(n-i-1)
    else:
        k-=2**(n-i-1)
    z=bin(k).count('1')
    l=1
    while k%z>0:
        k%=z
        z=bin(k).count('1')
        l+=1
    print(l)

Submission status: Runtime Error

Solution code:
n = int(input())
s = input()
su = s.count('1')
sun = int(s,2)

def f(m,n_):
    mod = m % n_
    if mod == 0:
        return 1
    return 1 + f(mod,bin(mod).count('1'))


for i in range(n):
    if s[i] == '0':
        print(f(sun+2**(n-1-i),su+1))
    else:
        print(f(sun-2**(n-1-i),su-1))

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
ones = X.count('1')
Xd = int(X, 2)

from functools import lru_cache

@lru_cache(maxsize=None)
def f(i):
	if i == 0: return 0

	return 1 + f(i % popcount(i))

def popcount(x):
      b=0
      while(x > 0):
          x &= x - 1
          b+=1
      return b

for i in range(N):
	div = ones + 1 if X[i] == '0' else ones - 1
	print(1 + f((Xd ^ (1 << (N-i-1))) % div))

Submission status: Runtime Error

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

cnt1 = x.count("1")
p_cnt = cnt1 + 1
m_cnt = cnt1 - 1
p_amari = val % (cnt1 + 1)
m_amari = val % (cnt1 - 1)


#p_mod = [0] * (n + 1)
#for i in range(n + 1):
#    p_mod[i] = pow(2, i, p_cnt)

#m_mod = [0] * (n + 1)
#for i in range(n + 1):
#    m_mod[i] = pow(2, i, m_cnt)


for i in range(n):
    ans = 0
    if x[i] == "0":
        # pになる
        amari = p_amari + pow(2, n - i - 1, p_cnt)
        amari %= p_cnt
        ans += 1
    elif x[i] == "1":
        # mになる
        amari = m_amari - pow(2, n - i - 1, m_cnt)
        amari %= m_cnt
        ans += 1
    while amari != 0:
        amari %= bin(amari).count("1")
        ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.buffer.readline()[:-1]
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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

N = INT()
X = input()
X = int(X, 2)
for i in range(N):
    Y = X^(1<<(N-i-1))
    cnt = 0
    while Y:
        Y = Y%popcount(Y)
        cnt += 1
    print(cnt)