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: Wrong Answer

Solution code:
def examA():
    L, R, D = LI()
    ans = R//D - (L-1)//D
    print(ans)
    return

def examB():
    N = I()
    A = LI()
    ans = 0
    for i,a in enumerate(A):
        if i%2==0:
            if a%2==1:
                ans += 1
    print(ans)
    return

def examC():
    N = I()
    ans = [0]*N
    for x in range(1,101):
        for y in range(1,101):
            for z in range(1,101):
                cur = x**2 + y**2 + z**2 + x*y + y*z + x*z
                if cur<N+1:
                    ans[cur-1] += 1

    for v in ans:
        print(v)
    return

def examD():
    def cnt(num):
        c = 0
        while(num>0):
            num %= bin(num).count("1")
            c += 1
        return c
    N = I()
    X = SI()
    S_upper = [0]*N
    S_lower = [0]*N
    start_upper = 0
    start_lower = 0
    bit = 0
    ans = [0]*N
    for s in X:
        if s=="1":
            bit += 1
    if bit==1:
        b = 0
        for i in range(N):
            if X[i]=="1":
                ans[i] = 0
                b = i
            else:
                ans[i] = 1
        if b==N-1:
            for i in range(N-1):
                ans[i] += 1
        for v in ans:
            print(v)
        return
    elif bit==0:
        for v in ans:
            print(v+1)
        return

    for i in range(N):
        S_upper[i] = pow(2,N-i-1,bit+1)
        S_lower[i] = pow(2,N-i-1,bit-1)
        if X[i]=="1":
            start_upper += S_upper[i]
            start_lower += S_lower[i]
            start_upper %= (bit+1)
            start_lower %= (bit-1)

    for i in range(N):
        if X[i]=="0":
            cur = (start_upper + S_upper[i]) % (bit+1)
            ans[i] = cnt(cur)+1
        else:
            cur = (start_lower - S_lower[i]) % (bit+1)
            ans[i] = cnt(cur)+1
        #print(cur)

    for v in ans:
        print(v)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(2*10**6)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
S = list(map(int, list(input())[: -1]))
pp = sum(S)
if pp == 1:
  for i in range(N):
    if S[i]: print(0)
    else: print(1)
  exit(0)
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, max(1, pp - 1)) * S[i]
  Xm %= max(1, pp - 1)
#print(Xp, Xm)
rres = [0] * N
for i in range(N):
  res = 1
  if S[i]:
    X = (Xm - pow(2, i, max(1, pp - 1))) % max(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: Wrong Answer

Solution code:
n = int(input())
x = input()
d = [0] * n
t = x.count('1')
a = 0
b = 0

for i in range(n):
    d[i] = (a + pow(2, n - i - 1, t + 1)) % (t + 1)
if t == 1:
    for i in range(n):
        a *= 2
        if x[i] == '1':
            a += 1
        a %= t + 1
    for i in range(n):
        if x[i] == '1':
            print(0)
        else:
            p = d[i]
            ans = 1
            while p > 0:
                p %= bin(p).count('1')
                ans += 1
            print(ans)
else:
    for i in range(n):
        a *= 2
        b *= 2
        if x[i] == '1':
            a += 1
            b += 1
        a %= t + 1
        b %= t - 1
    for p in d:
        ans = 1
        while p > 0:
            p %= bin(p).count('1')
            ans += 1
        print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
S = list(map(int, list(input())[: -1]))
pp = sum(S)
if pp == 1:
  for i in range(N - 1): print(1)
  print(0)
  exit(0)
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, max(1, pp - 1)) * S[i]
  Xm %= max(1, pp - 1)
#print(Xp, Xm)
rres = [0] * N
for i in range(N):
  res = 1
  if S[i]:
    X = (Xm - pow(2, i, max(1, pp - 1))) % max(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: Wrong Answer

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")
    flg = 0
    if M == 1:
        flg = 1
    x_major = 0
    x_minor = 0
    for i in range(N):
        add = int(X[i])
        x_major = (x_major * 2 + add)%(M+1)
        if flg == 0:
            x_minor = (x_minor * 2 + add)%(M-1)
    for i in range(N):
        if X[i] == "1":
            if flg:
                print(1)
                continue
            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: Wrong Answer

Solution code:
def f(n):
  ans=0
  while n!=0:
    n%=(bin(n)[2:]).count("1")
    ans+=1
  return ans

n=int(input())
x=input()
pc=x.count("1")
if pc==0:exit(print(*[1]*n))
if pc==1:
  for i in x:
    if i=="1":print(0)
    else:print(1)
  exit()
nx=int(x,2)
pco=nx%(pc+1)
pcm=nx%(pc-1)
for i in range(n):
  if x[i]=="1":
    m=pow(2,n-i-1,pc-1)%(pc-1)
    print(1+f((pcm-m)%(pc-1)))
  else:
    m=pow(2,n-i-1,pc+1)%(pc+1)
    print(1+f((pco+m)%(pc+1)))

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.read
#readlines = sys.stdin.readlines
from collections import defaultdict
from copy import deepcopy
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())

    d1 = defaultdict(int)
    d1[0] = 0
    for i1 in range(n):
        tx = deepcopy(x)
        if tx[i1] == '1':
            tx[i1] = '0'
        else:
            tx[i1] = '1'
        t = from2to10(tx)
        print(f(t))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache


@lru_cache(None)
def solve(xx):
    mm = bin(xx).count('1')
    if mm == 0:
        return 0
    else:
        return 1 + solve(xx%mm)


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

m = x.count('1')
xi = int(x, 2)

ans = []
t = 1
d = {}
d[m+1] = xi % (m+1)
if 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)) % (m+1)
        
    elif m == 1:
        ans.append(0)
        continue
    else:
        xx = ((d[m-1] - t) % (m-1)) % (m-1)
    
    mm = bin(xx).count('1')
    ans.append(1 + solve(xx))
    t *= 2
ans = ans[::-1]
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache


@lru_cache(None)
def solve(xx):
    mm = bin(xx).count('1')
    if mm == 0:
        return 0
    else:
        return 1 + solve(xx%mm)


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

m = x.count('1')
xi = int(x, 2)

ans = []
t = 1
d = {}
d[m+1] = xi % (m+1)
if 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)) % (m+1)
        
    elif m == 1:
        ans.append(0)
        continue
    else:
        xx = ((d[m-1] - t) % (m-1)) % (m-1)
    
    mm = bin(xx).count('1')
    ans.append(1 + solve(xx))
    t *= 2
ans.reverse()
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

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

m = x.count('1')
xi = int(x, 2)

ans = []
t = 1
d = {}
d[m+1] = xi % (m+1)
if 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)) % (m+1)
        
    elif m == 1:
        ans.append(0)
        continue
    else:
        xx = ((d[m-1] - t) % (m-1)) % (m-1)
    
    mm = bin(xx).count('1')
    cnt = 1
    while xx:
        xx %= mm
        mm = bin(xx).count('1')
        cnt += 1
    ans.append(cnt)
    t *= 2
ans.reverse()
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

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)
if 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)) % (m+1)
        
    elif m == 1:
        ans.append(0)
        continue
    else:
        xx = ((d[m-1] - t) % (m-1)) % (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: Time Limit Exceeded

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
for i in range(n-1, -1, -1):
    if x[i] == '0':
        xx = xi + t
        mm =  m + 1
    else:
        xx = xi - t
        mm =  m - 1

    cnt = 0
    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: Time Limit Exceeded

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

@author: harurun
'''
from functools import lru_cache
@lru_cache(maxsize=None)
def f(Y):
  return bin(int(Y)).count("1")

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

  N=int(pin())
  X=pin()

  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:
      Y=Y%f(Y)
      cnt+=1
    print(cnt)
  return
main()

Submission status: Time Limit Exceeded

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

@author: harurun
'''
from functools import lru_cache
@lru_cache(maxsize=None)
def f(Y):
  return str(bin(int(Y))).count("1")

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

  N=int(pin())
  X=pin()

  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=f(Y)
      Y=Y%c
      cnt+=1
    print(cnt)
  return
main()

Submission status: Time Limit Exceeded

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:]
    if n==0:
        return cnt
    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: Time Limit Exceeded

Solution code:
def pc(x):
    cnt = 0
    for i in range(len(x)):
        if x[i]=="1":
            cnt += 1
    return cnt
def f(n):
    if n==0:
        return 0
    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: Time Limit Exceeded

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()

  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=str(bin(int(Y))).count("1")
      Y=Y%c
      cnt+=1
    print(cnt)
  return
main()

Submission status: Time Limit Exceeded

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={}

  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
      try :
        c=dp[Y-1]
      except:
        c=str(bin(int(Y))).count("1")
        dp[Y-1]=c
      Y=Y%c
      cnt+=1
    print(cnt)
  return
main()

Submission status: Time Limit Exceeded

Solution code:
def solve(x):
    cnt = 1
    while x > 0:
        x %= bin(x).count('1')
        cnt += 1
    return cnt

n = int(input())
x = input()
one = sum(map(int, list(x)))
num = int(x, 2)

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

Submission status: Time Limit Exceeded

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)
if one == 1:
    down = 0
else:
    down = num%(one-1)
z = 2**(n-1)
for i in range(n):
    if x[i] == '1':
        if one == 1:
            print(0)
            z //= 2
            continue
        s = down - z%(one-1)
        if s < 0:
            s += one-1
    else:
        s = (up + z%(one+1))%(one+1)
    print(solve(s))
    z //= 2

Submission status: Time Limit Exceeded

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)
if one == 1:
    down = 0
else:
    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: Time Limit Exceeded

Solution code:
def solve(st):
    num = int(st, 2)
    count = 0
    while num > 0:
        x = bin(num).count('1')
        num %= x
        count += 1
    return count

n = int(input())
x = list(input())
for i in range(n):
    y = x.copy()
    if y[i] == '1':
        y[i] = '0'
    else:
        y[i] = '1'
    print(solve(''.join(y)))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = list(input())
X = [int(x) for x in X]
popcnt = 0
for i in range(N):
    if X[i]:
        popcnt += 1

for i in range(N):
    if X[i]:#1->0
        mod = popcnt-1
    else:#0->1
        mod = popcnt+1

    if mod == 0:
        print(0)
        continue

    tmpX = X[:]
    tmpX[i] ^= 1

    Y = 0
    ans = 1
    for j in range(N):
        if tmpX[N-1-j]:
            Y += pow(2,j,mod)
            Y %= mod
    # print(Y,mod)
    if Y == 0:
        print(ans)
        continue
        
    while Y > 0:
        L = Y.bit_length()
        mod = 0
        for j in range(L):
            if Y>>j&1:
                mod += 1
        Y %= mod
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

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 = 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)
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
  if temp < MAX:
    ret = small[temp]
  else:
    nokori = temp%btemp
    ret = small[nokori] + 1 #最初の一回
  ans.append(ret)
print(*ans,sep="\n")

Submission status: Time Limit Exceeded

Solution code:
def f(n):
  if n==0:return 0
  else:return f(pc[n])+1
n=int(input())
x=input()
pc=[0]
m=2*10**5
for i in range(1,m+2):
  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

Submission status: Time Limit Exceeded

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

def main():
  n = int(input())
  x = input()
  c = x.count('1')
  # popcount(n)は高々c+1
  m = 10**6
  dp = [0]*(m+2)
  
  for i in range(1, m+2):
    dp[i] = dp[i % popcnt(i)] + 1
    
  if c == 1:
    for i in range(n):
      if x[i] == '0':
        xp = int(x, 2) % (c+1)
        print(dp[(xp + pow(2, n-i-1, c+1)) % (c+1)] + 1)
      else:
        print(0)
    exit()
  
  # 1が増えたときと減ったときのpopcount
  cp, cm = c+1, c-1
  xp, xm = int(x, 2) % cp, int(x, 2) % cm
  
  for i in range(n):
    if x[i] == '0':
      print(dp[(xp + pow(2, n-i-1, cp)) % cp] + 1)
    else:
      print(dp[(xm - pow(2, n-i-1, cm)) % cm] + 1)


def popcnt(n):
  ans = 0
  while n:
      ans += n % 2
      n //= 2
  return ans

  
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

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

def main():
  n = int(input())
  x = input()
  c = x.count('1')
  # popcount(n)は高々c+1
  m = 10**6
  dp = [0]*(m+2)
  
  for i in range(1, m+2):
    dp[i] = dp[i % popcnt(i)] + 1
    
  if c == 1:
    for i in range(n):
      if x[i] == '0':
        xp = int(x, 2) % (c+1)
        print(dp[(xp + pow(2, n-i-1, c+1)) % (c+1)] + 1)
      else:
        print(0)
    exit()
  
  # 1が増えたときと減ったときのpopcount
  cp, cm = c+1, c-1
  xp, xm = int(x, 2) % cp, int(x, 2) % cm
  
  for i in range(n):
    if x[i] == '0':
      print(dp[(xp + pow(2, n-i-1, cp)) % cp] + 1)
    else:
      print(dp[(xm - pow(2, n-i-1, cm)) % cm] + 1)


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

  
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

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

def main():
  n = int(input())
  x = input()
  c = x.count('1')
  # popcount(n)は高々c+1
  dp = [0]*(c+2)
  
  for i in range(1, c+2):
    dp[i] = dp[i % popcnt(i)] + 1
    
  if c == 1:
    for i in range(n):
      if x[i] == '0':
        xp = int(x, 2) % (c+1)
        print(dp[(xp + pow(2, n-i-1, c+1)) % (c+1)] + 1)
      else:
        print(0)
    exit()
  
  # 1が増えたときと減ったときのpopcount
  cp, cm = c+1, c-1
  xp, xm = int(x, 2) % cp, int(x, 2) % cm
  
  for i in range(n):
    if x[i] == '0':
      print(dp[(xp + pow(2, n-i-1, cp)) % cp] + 1)
    else:
      print(dp[(xm - pow(2, n-i-1, cm)) % cm] + 1)


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

  
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
X = input()
X_10 = int(X, 2)
popcount_X = X.count("1")
popcount_X_plus = popcount_X + 1
popcount_X_minus = popcount_X - 1
f_plus = X_10 % popcount_X_plus
f_minus = X_10 % popcount_X_minus if popcount_X_minus != 0 else 0

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

def f(n):
  if n == 0:
    return 0
  return n % popcount(n)

for i in range(N):
  j = N - (i + 1)
  n = 0
  ans = 1
  
  if X[i] == '0':
    n = (f_plus + (2**j % popcount_X_plus)) % popcount_X_plus
#    n = (f_plus + pow(2, j, popcount_X_plus)) % popcount_X_plus
  else:
    if popcount_X_minus == 0:
      print(0)
      continue
    else:
      n = (f_minus - (2**j % popcount_X_minus) + popcount_X_minus) % popcount_X_minus
#      n = (f_minus - pow(2, j, popcount_X_minus) + popcount_X_minus) % popcount_X_minus
  
  while n > 0:
    n = f(n)
    ans += 1
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve():
  N = int(input())
  X = input()
  bl = X.count('1')
  bitp = 0
  for i in range(N):
    bitp += int(X[i])*pow(2,N-1-i)
    bitp %= bl+1
  bitm = 0
  if bl>1:
    for i in range(N):
      bitm += int(X[i])*pow(2,N-1-i)
      bitm %= bl-1
  
  ans = [0]*N
  dp = [0]*(N+1)
  for i in range(1,N+1):
    dp[i] = dp[i%(bin(i).count('1'))]+1
  for i in range(N):
    if X[i]=='1':
      bit1 = bitm - pow(2,N-1-i)
      bl1 = bl-1
      if bl1==0:
        ans[i] = 0
        continue
    else:
      bit1 = bitp + pow(2,N-1-i)
      bl1 = bl+1
    ans[i] = dp[bit1%bl1]+1
  return ans
print(*solve(),sep='\n')

Submission status: Time Limit Exceeded

Solution code:
def solve():
  N = int(input())
  X = input()
  bl = X.count('1')
  bit = 0
  for i in range(N):
    bit += int(X[i])<<(N-1-i)
  ans = [0]*N
  dp = [0]*(N+1)
  for i in range(1,N+1):
    dp[i] = dp[i%(bin(i).count('1'))]+1
  for i in range(N):
    if X[i]=='1':
      bit1 = bit - (1<<(N-1-i))
      bl1 = bl-1
      if bl1==0:
        ans[i] = 0
        continue
    else:
      bit1 = bit + (1<<(N-1-i))
      bl1 = bl+1
    ans[i] = dp[bit1%bl1]+1
  return ans
print(*solve(),sep='\n')

Submission status: Time Limit Exceeded

Solution code:
def solve():
  N = int(input())
  X = input()
  bl = X.count('1')
  bit = 0
  for i in range(N):
    bit += int(X[i])*pow(2,N-1-i)
  ans = [0]*N
  dp = [0]*(N+1)
  for i in range(1,N+1):
    dp[i] = dp[i%(bin(i).count('1'))]+1
  for i in range(N):
    if X[i]=='1':
      bit1 = bit - pow(2,N-1-i)
      bl1 = bl-1
      if bl1==0:
        ans[i] = 0
        continue
    else:
      bit1 = bit + pow(2,N-1-i)
      bl1 = bl+1
    ans[i] = dp[bit1%bl1]+1
  return ans
print(*solve(),sep='\n')

Submission status: Time Limit Exceeded

Solution code:
def solve():
  N = int(input())
  X = input()
  bl = X.count('1')
  bit = 0
  for i in range(N):
    bit += int(X[i])*pow(2,N-1-i)
  ans = [0]*N
  dp = [0]*(N+1)
  for i in range(1,N+1):
    dp[i] = dp[i%sum(map(int,list(bin(i)[2:])))]+1
  for i in range(N):
    if X[i]=='1':
      bit1 = bit - pow(2,N-1-i)
      bl1 = bl-1
      if bl1==0:
        ans[i] = 0
        continue
    else:
      bit1 = bit + pow(2,N-1-i)
      bl1 = bl+1
    ans[i] = dp[bit1%bl1]+1
  return ans
print(*solve(),sep='\n')

Submission status: Time Limit Exceeded

Solution code:
def solve():
  N = int(input())
  X = input()
  bl = X.count('1')
  bit = 0
  for i in range(N):
    bit += int(X[i])<<(N-1-i)
  ans = [0]*N
  dp = [0]*(N+1)
  for i in range(1,N+1):
    dp[i] = dp[i%sum(map(int,list(bin(i)[2:])))]+1
  for i in range(N):
    if X[i]=='1':
      bit1 = bit - (1<<(N-1-i))
      bl1 = bl-1
      if bl1==0:
        ans[i] = 0
        continue
    else:
      bit1 = bit + (1<<(N-1-i))
      bl1 = bl+1
    ans[i] = dp[bit1%bl1]+1
  return ans
print(*solve(),sep='\n')

Submission status: Time Limit Exceeded

Solution code:
def solve():
  N = int(input())
  X = input()
  bl = X.count('1')
  bit = 0
  for i in range(N):
    bit += int(X[i])<<(N-1-i)
  ans = [0]*N
  dp = [0]*(N+1)
  for i in range(1,N+1):
    dp[i] = dp[i%(bin(i).count('1'))]+1
  for i in range(N):
    if X[i]=='1':
      bit1 = bit - (1<<(N-1-i))
      bl1 = bl-1
      if bl1==0:
        ans[i] = 0
        continue
    else:
      bit1 = bit + (1<<(N-1-i))
      bl1 = bl+1
    ans[i] = dp[bit1%bl1]+1
  return ans
print(*solve(),sep='\n')

Submission status: Time Limit Exceeded

Solution code:
def binaryToDecimal(n): 
    return int(n,2)  

def decimalToBinary(n): 
    return bin(n).replace("0b","") 

def popCount(a):
    
    count = 0
    while(a!=0):
        bi = decimalToBinary(a)
        count_1 = bi.count('1')
        a = a%count_1
        count+=1
    return count

n = int(input())
li = input()
for i in range(n):
    s=li
    z = '0'
    if s[i]=='0':
        z='1'
    s = s[:i]+z+s[i+1:]
    a = binaryToDecimal(s)
    print(popCount(a))

Submission status: Time Limit Exceeded

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

binans=0
for i in range(n):
  if x[i]=='1':
    binans+=2**(n-i-1)
  
bincount=x.count('1')

def popcount(s):
  cnt=0
  while s!=0:
    if s%2==1:
      cnt+=1
    s//=2
  
  return cnt

def f(s):
  ans=0
  while s!=0:
    ans+=1
    s=s%popcount(s)
    
  return ans

for i in range(n):
  if x[i]=='0':
    xxx=binans+2**(n-i-1)
    bincount+=1
    
  else:
    xxx=binans-2**(n-i-1)
    bincount-=1
  
  print(f(xxx))

Submission status: Time Limit Exceeded

Solution code:
from sys import exit
from collections import defaultdict
n,x = open(0).read().split()
n = int(n)
x = int(x, 2)
x = x^(2**(n-1))

d = defaultdict(int)
d[0] = 0
def calc(m):
    if m not in d:
        nxt = m % bin(m).count('1')
        d[m] = calc(nxt) + 1
    return d[m]

if n == 1:
    print(calc(x))
    exit()

mask = 3 << (n-2)

while 1:
    print(calc(x))
    x ^= mask
    if mask < 3:
        break
    mask //= 2

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

N = int(input())
X = input()
pc = X.count('1')


if pc == 0:
    print(*[1]*N, sep='\n')
    exit()
elif pc == 1:
    if int(X, 2) == 1:
        for i in range(N-1):
            print(2)
        print(0)
        exit()
    else:
        for i in range(N):
            if i == N-1:
                print(2)
            elif X[i] == '0':
                print(1)
            else:
                print(0)
        exit()

mod_plus_1, mod_minus_1 = 0, 0
for i in range(N):
    mod_plus_1 = (mod_plus_1*2+int(X[i])) % (pc+1)
    mod_minus_1 = (mod_minus_1*2+int(X[i])) % (pc-1)


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


for i in range(N):
    if X[i] == '0':
        x = mod_plus_1 + 2**(N-1-i) % (pc+1)
        x %= (pc+1)
    else:
        x = mod_minus_1 - 2**(N-1-i) % (pc-1)
        x %= (pc-1)

    if x == 0:
        print(1)
    else:
        print(f(x)+1)

Submission status: Time Limit Exceeded

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

N = int(input())
X = input()
pc = X.count("1")

if pc == 1:
    if X[-1] == "0":
        for i, s in enumerate(X):
            if i == N - 1:
                print(2)
            elif s == "0":
                print(1)
            else:
                print(0)
    else:
        ans = [2] * (N - 1) + [0]
        print(*ans, sep="\n")
    exit()


m01 = 0
m10 = 0
for i, s in enumerate(X[::-1]):
    if s == "1":
        m01 += pow(2, i, pc + 1)
        m01 %= pc + 1
        m10 += pow(2, i, pc - 1)
        m10 %= pc - 1


def pop_count(T):
    T = (T & 0x55555555) + ((T >> 1) & 0x55555555)
    T = (T & 0x33333333) + ((T >> 2) & 0x33333333)
    T = (T & 0x0F0F0F0F) + ((T >> 4) & 0x0F0F0F0F)
    T = (T & 0x00FF00FF) + ((T >> 8) & 0x00FF00FF)
    T = (T & 0x0000FFFF) + ((T >> 16) & 0x0000FFFF)
    return T


memo = [0] * (N + 10)
for i in range(1, N + 10):
    p = pop_count(i)
    memo[i] = memo[i % p] + 1


ans = [0] * N
for i, s in enumerate(X[::-1]):
    if s == "0":
        m = m01
        m += 1 << i
        m %= pc + 1
    else:
        m = m10
        m -= 1 << i
        m %= pc - 1
    ans[i] = memo[m] + 1

print(*ans[::-1], sep="\n")