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

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

a = int(X, 2)
b = X.count("1")
k = 2 ** (N-1)

d = [0 for _ in range(b+2)]
for i in range(1, b+2):
    t = i
    cnt = 0
    while t > 0:
        if t % 2 == 1:
            cnt += 1
        t //= 2
    v = i % cnt
    d[i] = d[v] + 1

for i, ch in enumerate(X):
    if ch == "0":
        x = a + k
        y = b + 1
    else:
        x = a - k
        y = b - 1
    k //= 2

    if x == 0:
        print(0)
    else:
        print(d[x % y] + 1)

Submission status: Time Limit Exceeded

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

a = int(X, 2)
b = X.count("1")
k = 2 ** (N-1)

d = [0 for _ in range(b+2)]
for i in range(1, b+2):
    v = i % bin(i)[2:].count("1")
    d[i] = d[v] + 1

for i, ch in enumerate(X):
    if ch == "0":
        x = a + k
        y = b + 1
    else:
        x = a - k
        y = b - 1
    k //= 2

    if x == 0:
        print(0)
    else:
        print(d[x % y] + 1)

Submission status: Time Limit Exceeded

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

d = [0 for _ in range(N)]
for i in range(1, N):
    v = i % bin(i)[2:].count("1")
    d[i] = d[v] + 1

a = int(X, 2)
b = X.count("1")
k = 2 ** (N-1)

for i, ch in enumerate(X):
    if ch == "0":
        x = a + k
        y = b + 1
    else:
        x = a - k
        y = b - 1
    k //= 2

    if x == 0:
        print(0)
    else:
        print(d[x % y] + 1)

Submission status: Time Limit Exceeded

Solution code:
def mpow(a,b,m):
    ans=1
    while b >0 :
        if b&1:
            ans = (ans*a)%m
        a=(a*a)%m
        b=b>>1

    return ans

def calcmod(X,m,N):
    mod=0
    for i in range(N):
        if X&(1<<i) > 0:
            mod += mpow(2,i,m)
            mod%=m
    return mod

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


def findsteps(mm):
    cnt=0
    while mm !=0:
        cnt+=1
        mm=mm%popcount(mm)
    return cnt
N=int(input())
X=int(input(),2)

##we need to find X%(m-1) and X%(m+1)
m=popcount(X)
m1=m+1
m2=m-1
firstmod=calcmod(X,m1,N)
if m2 !=0:
    secondmod=calcmod(X,m2,N)
fans=[0 for i in range(N)]
k=0
for i in range(N-1,-1,-1):
    if X & (1<<i) >0:
        ##the bit was set
        ##we need to find X%(m-1) - (2^i)%(m-1)
        if m2 == 0:
            ans=0
        else:
            mm=secondmod - mpow(2,i,m2)
            if mm < 0:
                mm+=m2
            mm=mm%m2
            ans=1+findsteps(mm)
    else:
        mm = firstmod + mpow(2,i,m1)
        mm=mm%m1
        ans=1+findsteps(mm)
    fans[k] = ans
    k+=1
        ##the bit was not set
for i in fans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
def input_int():
    return map(int, input().split())

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

N=one_int()
S=one_str()

bit_count = S.count("1")
S_num = int(S,2)
S_min = S_num % (bit_count-1) if bit_count-1!=0 else 0
S_plu = S_num % (bit_count+1)




# calc_dict = {i:-1 for i in range(10000)}
# res_dict =  {i:-1 for i in range(10**4)}

# for i in range(1, 10000):
#     if calc_dict[i]==-1:
#         calc_dict[i] = bin(i).count("1")

#     res_dict[i] = i%calc_dict[i]+1

def mods(temp, count):
    count+=1
    if temp!=0:

#         if temp in res_dict:
#             return count+res_dict[temp]
        
#         if temp not in calc_dict:
#             calc_dict[temp]= bin(temp).count("1") 
        count = mods(temp%bin(temp).count("1") , count)

    return count

for i in range(N):
    if S[i]=="0":
        part = (2**(N-i-1))% (bit_count+1)
        num = (S_plu + part ) % (bit_count+1)
        print(mods(num, 0))
    else:
        if S_num == 2**(N-i-1):
            print(0)
            continue
        part = (2**(N-i-1))% (bit_count-1)
        num = (S_min - part)%(bit_count-1)
        print(mods(num, 0))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x=input()
cntm=0
cntp=0
fn=0
xi=[0]*n
ans=[0]*n
for i in range(n):
    if x[i]=="1":
        fn+=1
for i in reversed(range(n)):
    if x[i]=="1":
        cntp+=pow(2,n-i-1,fn+1)
        cntp%=fn+1
        if fn>1:
            cntm+=pow(2,n-i-1,fn-1)
            cntm%=fn-1
for i in reversed(range(n)):
    if x[i]=="1":
        if fn>1:
            xi[i]=(cntm-pow(2,n-i-1,fn-1))%(fn-1)
            ans[i]+=1
    else:
        xi[i]=(cntp+pow(2,n-i-1,fn+1))%(fn+1)
        ans[i]+=1
#print(xi)
for i in range(n):
    num=xi[i]
    while num>0:
        cnt=0
        for j in range(31):
            if (num>>j)&1:
                cnt+=1
        num%=cnt
        ans[i]+=1
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
def mpow(a,b,m):
    ans=1
    while b >0 :
        if b&1:
            ans = (ans*a)%m
        a=(a*a)%m
        b=b>>1

    return ans

def calcmod(X,m,N):
    mod=0
    for i in range(N+1):
        if X&(1<<i) > 0:
            mod += mpow(2,i,m)
            mod%=m
    return mod   
def popcount(m):
    return bin(m).count("1")


def findsteps(mm):
    cnt=0
    while mm !=0:
        cnt+=1
        mm=mm%popcount(mm)
    return cnt
N=int(input())
X=int(input(),2)

##we need to find X%(m-1) and X%(m+1)
m=popcount(X)
m1=m+1
m2=m-1
firstmod=calcmod(X,m1,N)
if m2 !=0:
    secondmod=calcmod(X,m2,N)
fans=[]
for i in range(N-1,-1,-1):
    if X & (1<<i) >0:
        ##the bit was set
        ##we need to find X%(m-1) - (2^i)%(m-1)
        if m2 == 0:
            ans=0
        else:
            mm=secondmod - mpow(2,i,m2)
            if mm < 0:
                mm+=m2
            mm=mm%m2
            ans=1+findsteps(mm)
    else:
        mm = firstmod + mpow(2,i,m1)
        mm=mm%m1
        ans=1+findsteps(mm)
    fans.append(ans)
        ##the bit was not set
for i in fans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
memo = {0:0, 1:1, 2:1}
def calc(x):
  global memo
  if x in memo:
    return memo[x]
  c = bin(x).count('1')
  y = x % c
  res = calc(y) + 1
  memo[x] = res
  return res

for i in range(3, 2*10**5+1):
  calc(i)

N = int(input())
X = input()
c = X.count('1')
X_int = int(X, 2)
Xmodp = X_int % (c+1)
Xmodm = X_int % (c-1) if c > 1 else 0

ans = []
digit = 1 << (N - 1)
for x in X:
  if x == '0':
    ans.append(
      memo[(Xmodp + digit%(c+1)) % (c+1)] + 1
    )
  else:
    if c == 1:
      ans.append(0)
    else:
      ans.append(
        memo[(Xmodm - digit%(c-1)) % (c-1)] + 1
      )  
  digit >>= 1

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

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

n=int(input())
xs=input()
xj=xs.count("1")

x=int(xs,2)
xip=x%(xj+1)
if xj!=1:
    xim=x%(xj-1)

def popcount(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

i1=1<<n
for i in range(n-1,-1,-1):
    i1=i1>>1
    if xs[n-1-i]=="0":
        pxi=xj+1
        xi=(xip+i1%pxi)%pxi
    elif xj==1:
        print(0)
        continue
    else:
        pxi=xj-1
        xi=(xim-i1%pxi)%pxi
    xi=xi%pxi
    if xi==0:
        print(1)
        continue
    icnt=1
    while xi>0:
#        print("i",i,"xi",xi,"icnt",icnt)
        icnt+=1
#        xi=xi%(bin(xi).count("1"))
        xi=xi%popcount(xi)
    print(icnt)

Submission status: Time Limit Exceeded

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

S=sum(X)

def bd(X):
    ans=0
    for n in reversed(range(len(X))):
        ans+=2**(len(X)-1-n)*X[n]
    return ans

def db(N):
    s=[]
    div=N
    fin=False
    while fin==False:
        mod=div%2
        div=div//2
        s.append(mod)
        if div==0:
            fin=True
    return s[::-1]

def rec(X,dec,S):
    n=dec
    if dp.get(n)!=None or n==0:
        return dp[n]
    else:
        n%=S
        X=db(n)
        S=sum(X)
        return rec(X,n,S)+1

d=bd(X)
dp={}
dp[0]=0
dp[1]=1

for n in range(N):
    if X[n]==0:
        X[n]=1
        d+=2**(N-1-n)
        S+=1
        tmp=rec(X,d,S)
        dp[d]=tmp
        X[n]=0
        d-=2**(N-1-n)
        S-=1
    else:
        X[n]=0
        d-=2**(N-1-n)
        S-=1
        tmp=rec(X,d,S)
        dp[d]=tmp
        X[n]=1
        d+=2**(N-1-n)
        S+=1
    print(tmp)

Submission status: Time Limit Exceeded

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

memo = {0:0, 1:1, 2:1}
def calc(x):
  global memo
  if x in memo:
    return memo[x]
  c = bin(x).count('1')
  y = x % c
  res = calc(y) + 1
  memo[x] = res
  return res

for i in range(3, 2*10**5+1):
  calc(i)

N = int(input())
X = input()
c = X.count('1')
X_int = int(X, 2)
Xmodp = X_int % (c+1)
Xmodm = X_int % (c-1) if c > 1 else 0

ans = []
digit = 1 << (N - 1)
for x in X:
  if x == '0':
    ans.append(
      calc((Xmodp + digit%(c+1)) % (c+1)) + 1
    )
  else:
    if c == 1:
      ans.append(0)
    else:
      ans.append(
        calc((Xmodm - digit%(c-1)) % (c-1)) + 1
      )  
  digit >>= 1

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

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(200000)

def input_int():
    return map(int, input().split())

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

N=one_int()
S=one_str()

bit_count = S.count("1")
S_min = int(S,2) % (bit_count-1) if bit_count-1!=0 else 0
S_plu = int(S,2) % (bit_count+1)
S_num = int(S,2)



# calc_dict = {i:-1 for i in range(100000)}
# res_dict =  {i:-1 for i in range(2*(10**5))}

# for i in range(1, 100000):
#     if calc_dict[i]==-1:
#         calc_dict[i] = bin(i).count("1")

#     res_dict[i] = i%calc_dict[i]+1

def mods(temp, count):
    count+=1
    if temp!=0:

#         if temp in res_dict:
#             print(count, temp, res_dict[temp])
#             print("come")
#             print()
#             return count+res_dict[temp]
        
#         if calc_dict[temp]==-1:
        bits = bin(temp).count("1")            
        count = mods(temp%bits, count)

    return count

for i in range(N):
    if S[i]=="0":
        part = (2**(N-i-1))% (bit_count+1)
        num = (S_plu + part ) % (bit_count+1)
        print(mods(num, 0))
    else:
        if S_num == 2**(N-i-1):
            print(0)
            continue
        part = (2**(N-i-1))% (bit_count-1)
        num = (S_min - part)%(bit_count-1)
        print(mods(num, 0))

Submission status: Time Limit Exceeded

Solution code:
def input_int():
    return map(int, input().split())

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

N=one_int()
S=one_str()

bit_count = S.count("1")
S_min = int(S,2) % (bit_count-1) if bit_count-1!=0 else 0
S_plu = int(S,2) % (bit_count+1)
S_num = int(S,2)



# calc_dict = {i:-1 for i in range(100000)}
# res_dict =  {i:-1 for i in range(2*(10**5))}

# for i in range(1, 100000):
#     if calc_dict[i]==-1:
#         calc_dict[i] = bin(i).count("1")

#     res_dict[i] = i%calc_dict[i]+1

def mods(temp, count):
    count+=1
    while temp!=0:

#         if temp in res_dict:
#             print(count, temp, res_dict[temp])
#             print("come")
#             print()
#             return count+res_dict[temp]
        
#         if calc_dict[temp]==-1:
        bits = bin(temp).count("1")
            
        temp = temp%bits
        count+=1

    return count

for i in range(N):
    if S[i]=="0":
        part = (2**(N-i-1))% (bit_count+1)
        num = (S_plu + part ) % (bit_count+1)
        print(mods(num, 0))
    else:
        if S_num == 2**(N-i-1):
            print(0)
            continue
        part = (2**(N-i-1))% (bit_count-1)
        num = (S_min - part)%(bit_count-1)
        print(mods(num, 0))

Submission status: Time Limit Exceeded

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

for s in input():
    X <<= 1
    if s == '1':
        X += 1
        C += 1

def f(n, c):
    if n == 0:
        return 0
    n %= c

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

ans = [f(X ^ (1 << i), C + (1 if (X & (1 << i) == 0) else -1)) for i in range(N)]
print(*ans[::-1], sep='\n')

Submission status: Time Limit Exceeded

Solution code:
# D Anything Goes to Zero

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

ori_cnt = x.count("1")
for i in range(n):
  xi = int(x, 2)
  if x[i] == "1":
    new_cnt = ori_cnt - 1
  elif x[i] == "0":
    new_cnt = ori_cnt + 1
  xi = xi ^ (1 << n-i-1)
  if xi == 0:
    print(0)
  else:
    xi = xi % new_cnt
    ans = 1
    while xi != 0:
      xi = xi % bin(xi).count("1")
      ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def popcount(x):
    ans = 0   
    while x > 0:
        if x & 1:
            ans += 1
        x >>= 1
    return ans
              
def f(x, pc, memo=None):
    if memo and (x, pc) in memo:
        return memo[(x, pc)]
    r = x % pc
    if memo:  
        memo[(x, pc)] = r
    return r  
              
N = int(input())
X = input()   
              
x = int(X, 2) 
              
memo = {}     
pc_x = X.count('1')
              
for i in range(N):
    if X[i] == '1':
        pc = pc_x - 1
    else:     
        pc = pc_x + 1
    if pc == 0:
        print('0')
        continue
    f_x = f(x, pc, memo)
    f_res = f(pow(2, (N-i-1), pc), pc, memo)
    if X[i] == '1':
        f_i = f_x - f_res
    else:     
        f_i = f_x + f_res
    f_i = (f_i + 2 * pc) % pc
    ans = 1   
    while f_i > 0:
        ans += 1
        pc = popcount(f_i)
        f_i = f(f_i, pc)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def popcount(x):
    ans = 0   
    while x > 0:
        if x & 1:
            ans += 1
        x >>= 1
    return ans
              
def f(x, pc, memo=None):
    if memo and (x, pc) in memo:
        return memo[(x, pc)]
    r = x % pc
    if memo:  
        memo[(x, pc)] = r
    return r  
              
N = int(input())
X = input()   
              
x = int(X, 2) 
              
memo = {}     
pc_x = X.count('1')
              
for i in range(N):
    if X[i] == '1':
        pc = pc_x - 1
    else:     
        pc = pc_x + 1
    if pc == 0:
        print('0')
        continue
    f_x = f(x, pc, memo)
    f_res = f(1<<(N-i-1), pc, memo)
    if X[i] == '1':
        f_i = f_x - f_res
    else:     
        f_i = f_x + f_res
    f_i = (f_i + 2 * pc) % pc
    ans = 1   
    while f_i > 0:
        ans += 1
        pc = popcount(f_i)
        f_i = f(f_i, pc)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def popcount(x):
    ans = 0   
    while x > 0:
        if x & 1:
            ans += 1
        x >>= 1
    return ans
              
def f(x, pc, memo=None):
    if memo and (x, pc) in memo:
        return memo[(x, pc)]
    r = x % pc
    if memo:  
        memo[(x, pc)] = r
    return r  
              
N = int(input())
X = input()   
              
x = int(X, 2) 
              
memo = {}     
pc_x = popcount(x)
              
for i in range(N):
    if X[i] == '1':
        pc = pc_x - 1
    else:     
        pc = pc_x + 1
    if pc == 0:
        print('0')
        continue
    f_x = f(x, pc, memo)
    f_res = f(1<<(N-i-1), pc, memo)
    if X[i] == '1':
        f_i = f_x - f_res
    else:     
        f_i = f_x + f_res
    f_i = (f_i + 2 * pc) % pc
    ans = 1   
    while f_i > 0:
        ans += 1
        pc = popcount(f_i)
        f_i = f(f_i, pc)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
M = 1

while M < N:
    M <<= 1

mask = []
K = M
while K // 2 > 0:
    s = (1 << (K // 2)) - 1
    m = 0
    for _ in range(M // K):
        m <<= K
        m += s
    mask.append(m)
    K >>= 1
mask = mask[::-1]

def popcnt(n):
    for i, m in enumerate(mask):
        n = (n & m) + ((n >> (1 << i)) & m)
    return n

def f(n):
    ret = 0
    while n > 0:
        ret += 1
        n %= popcnt(n)
    return ret

X = 0
for s in input():
    X <<= 1
    if s == '1':
        X += 1

ans = [f(X ^ (1 << i)) for i in range(N)]
print(*ans[::-1], sep='\n')

Submission status: Time Limit Exceeded

Solution code:
def popcount(x):
    ans = 0   
    while x > 0:
        if x & 1:
            ans += 1
        x >>= 1
    return ans
              
def f(x, pc, memo):
    if (x, pc) in memo:
        return memo[(x, pc)]
    r = x % pc
    memo[(x, pc)] = r
    return r  
              
N = int(input())
X = input()   
              
x = int(X, 2) 
              
memo = {}     
pc_x = popcount(x)
              
for i in range(N):
    if X[i] == '1':
        pc = pc_x - 1
    else:     
        pc = pc_x + 1
    if pc == 0:
        print('0')
        continue
    f_x = f(x, pc, memo)
    f_res = f(1<<(N-i-1), pc, memo)
    if X[i] == '1':
        f_i = f_x - f_res
    else:     
        f_i = f_x + f_res
    f_i = (f_i + 2 * pc) % pc
    ans = 1   
    while f_i > 0:
        ans += 1
        pc = popcount(f_i)
        f_i = f(f_i, pc, memo)
    print(ans)

Submission status: Time Limit Exceeded

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

b = 0 #10進数
c = 0 #1の数
ans = [0] * n

for i in range(len(x)):
#    print(x[i],x[:i],x[i + 1 :])
    if x[i] == "1":
        x = x[:i] + "0" + x[i + 1 :]
    else:
        x = x[:i] + "1" + x[i + 1 :]
    b = int(x, 2)
    c = x.count("1")
#    print(x,b,c)
    while b > 0:
        b = b % c
        ans[i] += 1
        c = bin(b).count("1")
#        print(b, c)
    if x[i] == "1":
        x = x[:i] + "0" + x[i + 1 :]
    else:
        x = x[:i] + "1" + x[i + 1 :]

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

n=int(input())
xs=input()
xj=xs.count("1")

x=int(xs,2)
xip=x%(xj+1)
if xj!=1:
    xim=x%(xj-1)

i1=1<<n
for i in range(n-1,-1,-1):
    i1=i1>>1
#    xi=x^i1
#    if xi==0:
#        print(0)
#        continue
    if xs[n-1-i]=="0":
        pxi=xj+1
        xi=(xip+i1%pxi)%pxi
    elif xj==1:
        print(0)
        continue
    else:
        pxi=xj-1
        xi=(xim-i1%pxi)%pxi
    xi=xi%pxi
    if xi==0:
        print(1)
        continue
    icnt=1
    while xi>0:
#        print("i",i,"xi",xi,"icnt",icnt)
        icnt+=1
        xi=xi%(bin(xi).count("1"))
    print(icnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

n=int(input())
xs=input()
xj=xs.count("1")

x=int(xs,2)
xip=x%(xj+1)
if xj!=1:
    xim=x%(xj-1)

i1=1<<n
for i in range(n-1,-1,-1):
    i1=i1>>1
    xi=x^i1
    if xi==0:
        print(0)
        continue
    if xs[n-1-i]=="0":
        pxi=xj+1
        xi=(xip+i1%pxi)%pxi
    elif xj==1:
        print(0)
        continue
    else:
        pxi=xj-1
        xi=(xim-i1%pxi)%pxi
    xi=xi%pxi
    if xi==0:
        print(1)
        continue
    icnt=1
    while xi>0:
#        print("i",i,"xi",xi,"icnt",icnt)
        icnt+=1
        xi=xi%(bin(xi).count("1"))
    print(icnt)

Submission status: Time Limit Exceeded

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

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

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

pops = popcount(x)
x_pop_p = x%(pops + 1)
try:
    x_pop_m = x%(pops - 1)
except:
    x_pop_m = 0
for i in reversed(range(0,n)):
    bit = x^(1<<i)
    if bit == 0:
        print(0)
        continue
    if x&(1<<i):
        tmp = (x_pop_m - pow(2,i,(pops - 1)))%(pops - 1)
    else:
        tmp = (x_pop_p + pow(2,i,(pops + 1))) % (pops + 1)
    if tmp == 0:
        print(1)
        continue
    cnt = 2
    if tmp == 0:
        print(cnt-1)
        continue
    tmp = tmp % popcount(tmp)
    while tmp > 0:
        cnt += 1
        if tmp == 0:
            print(cnt-1)
            continue
        tmp %= popcount(tmp)
    print(cnt)

Submission status: Time Limit Exceeded

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

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

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

pops = popcount(x)
x_pop_p = x%(pops + 1)
try:
    x_pop_m = x%(pops - 1)
except:
    x_pop_m = 0
#print(x_pop_p)
#print(x_pop_m)
#print()
for i in reversed(range(0,n)):
    bit = x^(1<<i)
    #print(bin(bit))
    #print(bit)
    #print(popcount(bit))
    if bit == 0:
        print(0)
        continue
    if x&(1<<i):
        tmp = (x_pop_m - pow(2,i,(pops - 1)))%(pops - 1)
    else:
        tmp = (x_pop_p + pow(2,i,(pops + 1))) % (pops + 1)
    #print(tmp)
    if tmp == 0:
        print(1)
        continue
    cnt = 2
    tmp_pop = popcount(tmp)
    if tmp_pop == 0:
        print(cnt-1)
        continue
    tmp = tmp % tmp_pop
    while tmp > 0:
        cnt += 1
        tmp_pop = popcount(tmp)
        if tmp_pop == 0:
            print(cnt-1)
            continue
        tmp %= tmp_pop
    print(cnt)
    #print()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = str(input())
count = X.count("1")
num, nump, numm = 0, 0, 0
now, nowp, nowm = 1, 1, 1

if count == 0:
  for i in range(N):
    print("1")
    quit()
elif count == 1:
  while True:
    a = 1
  if X[-1] == "1":
    for i in range(N):
      if i != N - 1:
        print("2")
      else:
        print("1")
  else:
    for i in range(N):
      print("1")
  quit()
  

xx = [0] * N
x_plus = [0] * N
x_minus = [0] * N
for i in range(1, N + 1):
  if i != 1:
    now *= 2
    nowp *= 2
    
    now %= count
    nowp %= (count + 1)
    

    nowm *= 2
    nowm %= (count - 1)
  
  else:
    now %= count
    nowp %= (count + 1)
    nowm %= (count - 1) 
  xx[i - 1] = now
  x_plus[i - 1] = nowp
  x_minus[i - 1] = nowm
  if X[-i] == "1":
    num += now
    num %= count
    nump += nowp
    nump %= count + 1
    numm += nowm
    numm %= count - 1
    
#print(num, xx, x_plus, x_minus)    

nextn = [0] * N
#ans = [1] * N
for i in range(N):
    if X[i] == "0":
      a = nump + x_plus[N - 1 - i]
      b = count + 1
      #print(a, b)
      nextn[i] = a % b
    else:
      #if count == 2:
      #  nextn[i] = 0
      #else:
        a = numm - x_minus[N - 1 - i]
        b = count - 1
        nextn[i] = a % b
        
#print(nextn)    
for i in range(N):
  if nextn[i] == 0:
    print("1")
  else:
    nownow = nextn[i]
    ans = 1
    while nownow != 0:
      alpha = bin(nownow)[2:]
      beta = str(alpha).count("1")
      nownow %= beta
      ans += 1
    print(ans)

Submission status: Time Limit Exceeded

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

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

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

pops = popcount(x)
x_pop_p = x%(pops + 1)
try:
    x_pop_m = x%(pops - 1)
except:
    x_pop_m = 0
#print(x_pop_p)
#print(x_pop_m)
#print()
pows_of_2 = [0]*(n)
pows_of_2[0] = 1
for i in range(1,n):
    pows_of_2[i] = pows_of_2[i-1] * 2
for i in reversed(range(0,n)):
    bit = x^(1<<i)
    #print(bin(bit))
    #print(bit)
    #print(popcount(bit))
    if bit == 0:
        print(0)
        continue
    if x&(1<<i):
        tmp = (x_pop_m - pows_of_2[i])%(pops - 1)
    else:
        tmp = (x_pop_p + pows_of_2[i]) % (pops + 1)
    #print(tmp)
    if tmp == 0:
        print(1)
        continue
    cnt = 2
    tmp_pop = popcount(tmp)
    if tmp_pop == 0:
        print(cnt-1)
        continue
    tmp = tmp % tmp_pop
    while tmp > 0:
        cnt += 1
        tmp_pop = popcount(tmp)
        if tmp_pop == 0:
            print(cnt-1)
            continue
        tmp %= tmp_pop
    print(cnt)
    #print()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

n=int(input())
xs=input()
xj=xs.count("1")

x=int(xs,2)
#xip=x%(xj+1)
#xim=x%(xj-1)

i1=1<<n
for i in range(n-1,-1,-1):
    i1=i1>>1
    xi=x^i1
    if xi==0:
        print(0)
        continue
    if xs[n-1-i]=="0":
        pxi=xj+1
#        xi=(xip+i1%pxi)%pxi
#        xi=(xip+i1)%pxi
    else:
        pxi=xj-1
#        xi=(xim-i1%pxi)%pxi
#        xi=(xim-i1)%pxi
    xi=xi%pxi
    if xi==0:
        print(1)
        continue
    icnt=1
    while xi>0:
#        print("i",i,"xi",xi,"icnt",icnt)
        icnt+=1
        xi=xi%(bin(xi).count("1"))
    print(icnt)

Submission status: Time Limit Exceeded

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

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

pops = popcount(x)
x_pop_p = x%(pops + 1)
try:
    x_pop_m = x%(pops - 1)
except:
    x_pop_m = 0
#print(x_pop_p)
#print(x_pop_m)
#print()
pows_of_2 = [0]*(n)
pows_of_2[0] = 1
for i in range(1,n):
    pows_of_2[i] = pows_of_2[i-1] * 2
for i in reversed(range(0,n)):
    bit = x^(1<<i)
    #print(bin(bit))
    #print(bit)
    #print(popcount(bit))
    if bit == 0:
        print(0)
        continue
    if x&(1<<i):
        tmp = (x_pop_m - pows_of_2[i])%(pops - 1)
    else:
        tmp = (x_pop_p + pows_of_2[i]) % (pops + 1)
    #print(tmp)
    if tmp == 0:
        print(1)
        continue
    cnt = 2
    tmp_pop = popcount(tmp)
    if tmp_pop == 0:
        print(cnt-1)
        continue
    tmp = tmp % tmp_pop
    while tmp > 0:
        cnt += 1
        tmp_pop = popcount(tmp)
        if tmp_pop == 0:
            print(cnt-1)
            continue
        tmp %= tmp_pop
    print(cnt)
    #print()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
b = int(input(), 2)

pct_b = bin(b).count("1")

def popcount(d):
  return (pct_b + 1) if (b >> d) & 1 == 0 else(pct_b - 1)

def f(b, pct):
  if(pct == 0):
    return 0
  
  b0 = b % pct
  if(b0 == 0):
  	return 1
  
  return 1 + f(b0, bin(b0).count("1"))
  

for i in range(n - 1, -1, -1):
  pb = b ^ (1 << i)
  pct = popcount(i)
  print(f(pb, pct))

Submission status: Time Limit Exceeded

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

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

pops = popcount(x)
x_pop_p = x%(pops + 1)
try:
    x_pop_m = x%(pops - 1)
except:
    x_pop_m = 0
#print(x_pop_p)
#print(x_pop_m)
#print()
for i in reversed(range(0,n)):
    bit = x^(1<<i)
    #print(bin(bit))
    #print(bit)
    #print(popcount(bit))
    if bit == 0:
        print(0)
        continue
    if x&(1<<i):
        tmp = (x_pop_m - pow(2,i))%(pops - 1)
    else:
        tmp = (x_pop_p + pow(2,i)) % (pops + 1)
    #print(tmp)
    if tmp == 0:
        print(1)
        continue
    cnt = 2
    tmp_pop = popcount(tmp)
    if tmp_pop == 0:
        print(cnt-1)
        continue
    tmp = tmp % tmp_pop
    while tmp > 0:
        cnt += 1
        tmp_pop = popcount(tmp)
        if tmp_pop == 0:
            print(cnt-1)
            continue
        tmp %= tmp_pop
    print(cnt)
    #print()

Submission status: Time Limit Exceeded

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

def f(n, initial):
  if not n:
    return 0
  n = n % initial
  ans = 1
  while n:
    popcount = bin(n).count('1')
    n = n % popcount
    ans += 1
  return ans

z = int(x, 2)
z_pc = bin(z).count('1')
for i in range(n):
  y = z ^ (1 << (n - i - 1))
  print(f(y, z_pc + (-1 if x[i] == '1' else 1)))

Submission status: Time Limit Exceeded

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

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

pops = popcount(x)
x_pop_p = x%(pops + 1)
try:
    x_pop_m = x%(pops - 1)
except:
    x_pop_m = 0
#print(x_pop_p)
#print(x_pop_m)
#print()
for i in reversed(range(0,n)):
    bit = x^(1<<i)
    #print(bin(bit))
    #print(bit)
    #print(popcount(bit))
    if bit == 0:
        print(0)
        continue
    if x&(1<<i):
        tmp = (x_pop_m - 2**i)%(pops - 1)
    else:
        tmp = (x_pop_p + 2 ** i) % (pops + 1)
    #print(tmp)
    if tmp == 0:
        print(1)
        continue
    cnt = 2
    tmp_pop = popcount(tmp)
    if tmp_pop == 0:
        print(cnt-1)
        continue
    tmp = tmp % tmp_pop
    while tmp > 0:
        cnt += 1
        tmp_pop = popcount(tmp)
        if tmp_pop == 0:
            print(cnt-1)
            continue
        tmp %= tmp_pop
    print(cnt)
    #print()

Submission status: Time Limit Exceeded

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

POPCOUNT_TABLE16 = [0] * 2**16
for index in range(len(POPCOUNT_TABLE16)):
  POPCOUNT_TABLE16[index] = (index & 1) + POPCOUNT_TABLE16[index >> 1]

def popcnt5(v):
  ans = 0
  while v:
    ans += POPCOUNT_TABLE16[v & 0xffff]
    v >>= 16
  return ans

def f(n):
  ans = 0
  while n:
    popcount = popcnt5(n)
    n = n % popcount
    ans += 1
  return ans

z = int(x, 2)
for i in range(n):
  y = z ^ (1 << (n - i - 1))
  print(f(y))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = input()
x = int(a,2)
c1 = a.count("1")

poplis = {0:0}
countlis = {0:0}

for i in range(1,210000):
    poplis[i] = poplis[i//2] + (i % 2)
    p = i % poplis[i]
    countlis[i] = countlis[p] + 1

for i in range(n):

    if a[i] == "0":
        c2 = c1 + 1
        ans = x + 2 ** (n - 1 - i)
    else:
        c2 = c1 - 1
        ans = x - 2 ** (n - 1 - i)
    if c2 > 0:
        ans = ans % c2
        ans = countlis[ans] + 1
    else:
        ans = 0

    print(ans)

Submission status: Time Limit Exceeded

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


def main():
    N = int(input())
    X = input()

    X_int = int(X, 2)

    pcount_X = popcount(X_int)
    pcount_X_pls1 = pcount_X + 1
    pcount_X_mns1 = pcount_X - 1

    for i,bit in enumerate(X):
        bit = int(bit)
        if bit == 0:
            pcount_Xi = pcount_X_pls1
        else:
            pcount_Xi = pcount_X_mns1
            if pcount_Xi == 0:
                print(0)
                continue

        n = ((X_int % pcount_Xi) + pow(2, N-i-1, pcount_Xi) * (-1)**bit) % pcount_Xi

        ans = 1
        while n > 0:
            ans += 1
            n %= popcount(n)
        print(ans)
        
main()

Submission status: Time Limit Exceeded

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

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

z = int(x, 2)
for i in range(n):
  y = z ^ (1 << (n - i - 1))
  print(f(y))