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:
from collections import deque
N = int(input())
X = str(input())
X = list(X)
motokosu = X.count("1")
only = float("inf")
if motokosu == 1:
  for i in range(N):
    if X[i] == "1":
      only = i
      break
#print(motosuji,motokosu)
MAX = 2*pow(10,5)+10
base = [0 for _ in range(MAX)] #0から19までの答えを保存
for i in range(MAX):
  now = i
  temp = 0
  while now != 0:
    ones = 0
    tnow = now*1
    for t in range(len(bin(now))-2):
      if (now>>t)&1 == 1:
        ones += 1
    #print(i,ones,now)
    now = now%ones
    #print(now,base[now])
    base[i] = base[now] + 1
    break
    #temp += 1
  #base[i] = temp
#print(base)
A = []
pkosu = motokosu+1
mkosu = motokosu-1
P = deque([])
M = deque([])
ptemp = 1; mtemp = 1
for i in range(N):
  P.appendleft(ptemp%pkosu)
  ptemp = ptemp*2%pkosu
  if mkosu < 1:
    M.appendleft(0)
  else:
    M.appendleft(mtemp%mkosu)
    mtemp = mtemp*2%mkosu
#print(P,M,pkosu,mkosu)
pmotosuji = 0; mmotosuji = 0
for i in range(N):
  if X[i] == "1":
    pmotosuji = (pmotosuji+P[i])%pkosu
    if mkosu < 1:
      continue
    mmotosuji = (mmotosuji+M[i])%mkosu
for i in range(N): #i桁目を入れ替える
  if only == i:
    print(0)
    continue
  if X[i] == "0": #その桁が0なら1にする
    kosu = motokosu + 1
    suji = (pmotosuji + P[i])%kosu
  else: #その桁が1なら0にする
    kosu = motokosu - 1
    if kosu == 0:
      suji = -1
    else:
      suji = (mmotosuji - M[i])%kosu
    
  #print(suji,kosu)
  #if suji == 0:
  #  ans = 0
  if suji == -1:
    ans = 1
  else:
    nxt = suji%kosu
    ans = 1+base[nxt]
  #A.append(ans)
  print(ans)

#print(*A,sep="\n")
#print(2**17)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
X = str(input())
motosuji = int(X,2)
X = list(X)
motokosu = X.count("1")
only = float("inf")
if motokosu == 1:
  for i in range(N):
    if X[i] == "1":
      only = i
      break
#print(motosuji,motokosu)
MAX = 2*pow(10,5)+10
base = [0 for _ in range(MAX)] #0から19までの答えを保存
for i in range(MAX):
  now = i
  temp = 0
  while now != 0:
    ones = 0
    tnow = now*1
    for t in range(len(bin(now))-2):
      if (now>>t)&1 == 1:
        ones += 1
    #print(i,ones,now)
    now = now%ones
    #print(now,base[now])
    base[i] = base[now] + 1
    break
    #temp += 1
  #base[i] = temp
#print(base)
A = []
pkosu = motokosu+1
mkosu = motokosu-1
P = deque([])
M = deque([])
ptemp = 1; mtemp = 1
for i in range(N):
  P.appendleft(ptemp%pkosu)
  ptemp = ptemp*2%pkosu
  if mkosu < 1:
    M.appendleft(0)
  else:
    M.appendleft(mtemp%mkosu)
    mtemp = mtemp*2%mkosu
#print(P,M,pkosu,mkosu)
for i in range(N): #i桁目を入れ替える
  if only == i:
    print(0)
    continue
  if X[i] == "0": #その桁が0なら1にする
    kosu = motokosu + 1
    suji = (motosuji + P[i])%kosu
  else: #その桁が1なら0にする
    kosu = motokosu - 1
    if kosu == 0:
      suji = -1
    else:
      suji = (motosuji - M[i])%kosu
    
  #print(suji,kosu)
  #if suji == 0:
  #  ans = 0
  if suji == -1:
    ans = 1
  else:
    nxt = suji%kosu
    ans = 1+base[nxt]
  #A.append(ans)
  print(ans)

#print(*A,sep="\n")
#print(2**17)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = str(input())
motosuji = int(X,2)
X = list(X)
motokosu = X.count("1")
#print(motosuji,motokosu)
MAX = 2*pow(10,5)+10
base = [0 for _ in range(MAX)] #0から19までの答えを保存
for i in range(MAX):
  now = i
  temp = 0
  while now != 0:
    ones = 0
    tnow = now*1
    for t in range(len(bin(now))-2):
      if (now>>t)&1 == 1:
        ones += 1
    #print(i,ones,now)
    now = now%ones
    #print(now,base[now])
    base[i] = base[now] + 1
    break
    #temp += 1
  #base[i] = temp
#print(base)
A = []
for i in range(N): #i桁目を入れ替える
  if X[i] == "0": #その桁が0なら1にする
    suji = motosuji + pow(2,N-1-i)
    kosu = motokosu + 1
  else: #その桁が1なら0にする
    suji = motosuji - pow(2,N-1-i)
    kosu = motokosu - 1
    
  #print(suji,kosu)
  if suji == 0:
    ans = 0
  else:
    nxt = suji%kosu
    ans = 1+base[nxt]
  #A.append(ans)
  print(ans)

#print(*A,sep="\n")
#print(2**17)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = str(input())
motosuji = int(X,2)
X = list(X)
motokosu = X.count("1")
#print(motosuji,motokosu)
MAX = 2*pow(10,5)+10
base = [0 for _ in range(MAX)] #0から19までの答えを保存
for i in range(MAX):
  now = i
  temp = 0
  while now != 0:
    ones = 0
    tnow = now*1
    for t in range(20):
      if (now>>t)&1 == 1:
        ones += 1
    #print(i,ones,now)
    now = now%ones
    #print(now,base[now])
    base[i] = base[now] + 1
    break
    #temp += 1
  #base[i] = temp
#print(base)
A = []
for i in range(N): #i桁目を入れ替える
  if X[i] == "0": #その桁が0なら1にする
    suji = motosuji + pow(2,N-1-i)
    kosu = motokosu + 1
  else: #その桁が1なら0にする
    suji = motosuji - pow(2,N-1-i)
    kosu = motokosu - 1
    
  #print(suji,kosu)
  if suji == 0:
    ans = 0
  else:
    nxt = suji%kosu
    ans = 1+base[nxt]
  #A.append(ans)
  print(ans)

#print(*A,sep="\n")

Submission status: Time Limit Exceeded

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


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

n = int(input())

X = input()
for i in range(n):
    r = '1' if X[i] == '0' else '0'
    x = X[:i] + r + X[i+1:]
    print(f(int(x, base=2)))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import copy

@lru_cache(maxsize=2*10000)
def popcount(n):
    str_bin = bin(n)
    return str_bin.count('1')
#popcount(n) を n を 2 進表記したときの 1 の個数とします。 例えば、popcount(3)=2,popcount(7)=3,popcount(0)=0 です。

#f(n) を、「n を popcount(n) で割ったあまりに置き換える」という操作を繰り返した際に n が 0 になるまでの操作回数とします
#(この問題の制約下で n が有限回の操作後に必ず 0 になることが証明できます)。
@lru_cache(maxsize=2*10000)
def f(n):
    if n == 0:
        return 0
    else:
        return 1 + f(n%popcount(n))

#2 進表記で N 桁の整数 X が与えられます。 
N = int(input())
X = list(input())

#1≤i≤N を満たす整数 i について、X の上から i 桁目のビットを反転した整数を Xi とします。
#f(X1),f(X2),…,f(XN) を求めてください。


for i in range(0,N):
    Xi = copy.copy(X) 

    if Xi[i] == "0":
        Xi[i] = "1"
    else:
        Xi[i] = "0"

    Xi = int(str(''.join(Xi)), 2) 
    print(f(Xi))

Submission status: Time Limit Exceeded

Solution code:

from functools import lru_cache
import copy

@lru_cache(maxsize=2*10000)
def popcount(n):
    str_bin = bin(n)
    return str_bin.count('1')
#popcount(n) を n を 2 進表記したときの 1 の個数とします。 例えば、popcount(3)=2,popcount(7)=3,popcount(0)=0 です。

#f(n) を、「n を popcount(n) で割ったあまりに置き換える」という操作を繰り返した際に n が 0 になるまでの操作回数とします
#(この問題の制約下で n が有限回の操作後に必ず 0 になることが証明できます)。
@lru_cache(maxsize=2*10000)
def f(n):
    if n == 0:
        return 0
    else:
        return 1 + f(n%popcount(n))

#2 進表記で N 桁の整数 X が与えられます。 
N = int(input())
X = list(input())

#1≤i≤N を満たす整数 i について、X の上から i 桁目のビットを反転した整数を Xi とします。
#f(X1),f(X2),…,f(XN) を求めてください。


for i in range(0,N):
    Xi = copy.copy(X) 

    if Xi[i] == "0":
        Xi[i] = "1"
    else:
        Xi[i] = "0"

    Xi = int(str(''.join(Xi)), 2) 
    print(f(Xi))

Submission status: Time Limit Exceeded

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

def popcount(X):
  counter = 0
  for i in range(N):
    if X[i] == "1":
      counter += 1
  return counter

    
def converter(N,X):
  conv_counter = 0
  for i in range(N):
    conv_counter += int(X[i])*(2**((N-1)-i))
  return conv_counter

def decorder(N,X):
  #10進数のXをＮ桁の2進数に直す
  reslist = []
  for i in range(N):
    p = int(X) // 2**((N-1)-i)
    reslist.append(str(p))
    X = str(int(X) - p*(2**((N-1)-i)))
  #print("reslist",reslist)
  res = "".join(reslist)
  return res

def bit_change(X,P):
  LISTX = list(X)
  change_num = abs(int(X[P])-1)
  LISTX[P] = str(change_num)
  X = "".join(LISTX)
  return X


def main(N,X):
  for i in range(N):
    result = 0
    #二進数のBIT変換
    target = bit_change(X,i)
    #print("target",target)
    
    if converter(N,target) == 0:
      flag = 0
    else:
      flag = 1
    #print("flag:",flag)
    
    while flag == 1:
      result += 1
      pop_count = popcount(target)
      conv = converter(N,target)
      target_10 = conv % pop_count
      
      if target_10 == 0:
        flag = 0
        
      else:
        target = decorder(N,target_10)
	  
    print(result)
    
main(N,X)
    
#print(decorder(N,X))

Submission status: Time Limit Exceeded

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

def popcount(X):
  counter = 0
  for i in range(N):
    if X[i] == "1":
      counter += 1
  return counter

    
def converter(N,X):
  conv_counter = 0
  for i in range(N):
    conv_counter += int(X[i])*(2**((N-1)-i))
  return conv_counter

def decorder(N,X):
  #10進数のXをＮ桁の2進数に直す
  reslist = []
  for i in range(N):
    p = int(X) // 2**((N-1)-i)
    reslist.append(str(p))
    X = str(int(X) - p*(2**((N-1)-i)))
  #print("reslist",reslist)
  res = "".join(reslist)
  return res

def bit_change(X,P):
  LISTX = list(X)
  change_num = abs(int(X[P])-1)
  LISTX[P] = str(change_num)
  X = "".join(LISTX)
  return X


def main(N,X):
  for i in range(N):
    result = 0
    #二進数のBIT変換
    target = bit_change(X,i)
    #print("target",target)
    
    if converter(N,target) == 0:
      flag = 0
    else:
      flag = 1
    #print("flag:",flag)
    
    while flag == 1:
      result += 1
      pop_count = popcount(target)
      conv = converter(N,target)
      target_10 = conv % pop_count
      
      if target_10 == 0:
        flag = 0
        
      else:
        target = decorder(N,target_10)
	  
    print(result)
    
main(N,X)
    
#print(decorder(N,X))

Submission status: Time Limit Exceeded

Solution code:
def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c
    
N = int(input())
P = input()
I = P.count("1")
Df = int(P,2)
Ans = [0] * (N+1)
#print(solve(N,cnt))

for i in range(1, N+1):
    p = popcnt(i)
    tmp = i % p
    Ans[i] = Ans[tmp] +1 
#print("Ans = ", Ans)

for i in range(N-1):
    if P[i] == "1":
        tmp = Df - pow(2,N-i-1)
        cur = I - 1
    else:
        tmp = Df + pow(2,N-i-1)
        cur = I + 1 
    if cur == 0:
        print(0)
        continue
    print(Ans[tmp%cur]+1)

if P[N-1] == "1":
    tmp = Df - 1
    cur = I - 1
else:
    tmp = Df + 1
    cur = I + 1
if cur == 0:
    print(0)
else:
    print(Ans[tmp%cur]+1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
P = input()
I = P.count("1")
Df = int(P,2)
Ans = [0] * (N+1)
#print(solve(N,cnt))

for i in range(1, N+1):
    p = format(i,"b").count("1")
    tmp = i % p
    Ans[i] = Ans[tmp] +1 
#print("Ans = ", Ans)

for i in range(N-1):
    if P[i] == "1":
        tmp = Df - 2**(N-i-1)
        cur = I - 1
    else:
        tmp = Df + 2**(N-i-1)
        cur = I + 1 
    if cur == 0:
        print(0)
        continue
    print(Ans[tmp%cur]+1)

if P[N-1] == "1":
    tmp = Df - 1
    cur = I - 1
else:
    tmp = Df + 1
    cur = I + 1
if cur == 0:
    print(0)
else:
    print(Ans[tmp%cur]+1)

Submission status: Time Limit Exceeded

Solution code:
def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c
    
N = int(input())
P = input()
I = P.count("1")
Df = int(P,2)
Ans = [0] * (N+1)
#print(solve(N,cnt))

for i in range(1, N+1):
    p = popcnt(i)
    tmp = i % p
    Ans[i] = Ans[tmp] +1 
#print("Ans = ", Ans)

for i in range(N-1):
    if P[i] == "1":
        tmp = Df - 2**(N-i-1)
        cur = I - 1
    else:
        tmp = Df + 2**(N-i-1)
        cur = I + 1 
    if cur == 0:
        print(0)
        continue
    print(Ans[tmp%cur]+1)

if P[N-1] == "1":
    tmp = Df - 1
    cur = I - 1
else:
    tmp = Df + 1
    cur = I + 1
if cur == 0:
    print(0)
else:
    print(Ans[tmp%cur]+1)

Submission status: Time Limit Exceeded

Solution code:
# D - Anything Goes to Zero
def conv_decimal(X):
  global N
  global powers
  global popcount_x
  
  pow = 1
  sum = 0
  
  for i in range(N - 1, -1, -1):
    if i < N - 1:
      pow *= 2
    
    if X[i] == '1':
      sum += pow
      popcount_x += 1
    
    powers.append(pow)
  
  return sum


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

from collections import deque
powers = deque()

# Xの"1"の数をカウント
popcount_x = 0

# 2進数を10進数に変換
decimal_x = conv_decimal(X)

for i in range(N):
  pow = powers.pop()
  
  if X[i] == '0':
    n = decimal_x + pow
    popcount = popcount_x + 1
  else:
    n = decimal_x - pow
    popcount = popcount_x - 1
  
  count = 0

  while popcount > 0:
    n %= popcount
    count += 1
    
    binary = bin(n)
    popcount = binary.count('1')
  
  print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = input()
x2 = int(x, 2)
c = x.count('1')

for i, ii in enumerate(x):
    k = 1 << (n-i-1)
    if int(ii):
        y = x2 - k
        c1 = c-1
    else:
        y = x2 + k
        c1 = c+1
    if y == 0:
        print(0)
        continue
    surplus = y % c1
    cnt = 1

    while surplus:
        surplus %= bin(surplus).count('1')
        cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = input()
x2 = int(x, 2)
c = x.count('1')

for i in range(n):
    k = 1 << (n-i-1)
    if int(x[i]):
        y = x2 - k
        c1 = c-1
    else:
        y = x2 + k
        c1 = c+1
    if y == 0:
        print(0)
        continue

    surplus = y % c1
    cnt = 1
    while surplus:
        surplus %= bin(surplus).count('1')
        cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = input()
c = x.count('1')

for i in range(n):
    if int(x[i]):
        y = x[:i] + '0' + x[i+1:]
        c1 = c-1
    else:
        y = x[:i] + '1' + x[i+1:]
        c1 = c+1
    if y.count('1') == 0:
        print(0)
        continue
    surplus = int(y, 2) % c1
    cnt = 1
    while surplus:
        surplus %= bin(surplus).count('1')
        cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

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

for i in range(n):
    if int(x[i]):
        y = x[:i] + '0' + x[i+1:]
    else:
        y = x[:i] + '1' + x[i+1:]
    if y.count('1') == 0:
        print(0)
        continue
    surplus = int(y, 2) % (y.count('1'))
    cnt = 1
    while surplus:
        surplus %= bin(surplus).count('1')
        cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = int(input(), 2)
#print("X :{}".format(X))

def popcount(n):
    ret = 0
    while(n!=0):
        if(n&1 == 1):
            ret += 1
        n=n>>1
    
    return ret
    
def func_f(n, px_0):
    #print("n:{}, px_0:{}".format(n, px_0))
    count = 0
    if n == 0:
        return 0
    
    temp = n % px_0
    count += 1

    while(temp != 0):
        temp = temp % popcount(temp)
        count += 1
        
    return count

px = popcount(int(X))
#print("px:{}".format(px))

for i in range(1, N+1):
    #print(bin(X))
    #print(bin(1 << (N-i)))
    a = 1 << (N-i)
    temp_x = X ^ a
    #print("temp_x:{} aaa:{}".format(temp_x, ((X >> (N-i)) & 1)))
    if ((X >> (N-i)) & 1) == 1:
        print(func_f(temp_x, px-1))
    else:
        print(func_f(temp_x, px+1))

Submission status: Time Limit Exceeded

Solution code:
### 解答
def popcount(X):
  pc = 0
  while X>0:
    pc += X%2
    X = X//2
  return pc

N = int(input())
B = input()
X = int(B, 2)

pcx = popcount(X)
pc0to1 = pcx + 1
pc1to0 = pcx - 1
if pc0to1 > 0:
  r0to1 = X%pc0to1
if pc1to0 > 0:
  r1to0 = X%pc1to0

for i in range(N):
  b = B[i]
  if b == "0":
    pc = pc0to1
  else:
    pc = pc1to0
  if pc == 0:
    print(0)
    continue

  if b == "0":
    x = r0to1 + 2**(N-i-1)%pc
  else:
    x = r1to0 - 2**(N-i-1)%pc
  x = x%pc

  ans = 1
  while x > 0:
    pc = popcount(x)
    x = x%pc
    ans += 1
  print(ans)

Submission status: Time Limit Exceeded

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

def popcount(number):
    bi = bin(number)
    count = 0
    for i in bi[2:]:
        if int(i) == 1:
            count += 1
    return(number%count)

for i in range(N):
    x = X[0:i] + str((int(X[i])+1)%2) + X[i+1:]
    x = int(x,2)
    co = 0
    while True:
        if x == 0:
            break
        x = popcount(x)
        co += 1
    print(co)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random,resource

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    s = S()
    t = int(s, 2)

    m = {}
    m[0] = 0
    def f(i):
        if i in m:
            return m[i]

        c = 0
        ii = i
        while ii > 0:
            c += ii % 2
            ii //= 2

        t = i % c
        m[i] = f(t) + 1
        return m[i]

    c = len([_ for _ in s if _ == '1'])
    r = []
    k = 2 ** (n-1)
    for i in range(n):
        if t == k:
            r.append(0)
        elif s[i] == '1':
            r.append(f((t - k) % (c-1)) + 1)
        else:
            r.append(f((t + k) % (c+1)) + 1)
        k //= 2

    return JA(r, "\n")


print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random,resource

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    s = S()

    m = {}
    m[0] = 0
    def f(i):
        if i in m:
            return m[i]

        c = 0
        ii = i
        while ii > 0:
            c += ii % 2
            ii //= 2

        t = i % c
        m[i] = f(t) + 1
        return m[i]

    c = len([_ for _ in s if _ == '1'])
    r = []
    for i in range(n):
        if s[i] == '1':
            r.append(f(int("".join(s[:i] + '0' + s[i+1:]), 2)))
        else:
            r.append(f(int("".join(s[:i] + '1' + s[i+1:]), 2)))

    return JA(r, "\n")


print(main())

Submission status: Time Limit Exceeded

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

def pc(x):
    return format(x, 'b').count('1')

N = int(input())
X = input()
Xn = int(X,2)
p = pc(Xn)
X = list(X)

Xp = Xn%(p+1)
if p==1:
    Xm = 0
else:
    Xm = Xn%(p-1)

def f(i):
    if p==1 and X[i]=='1':
        #Xi == 0 > POPcount ==0
        return 0
    else:
        if X[i]=='1':
            # p->p-1
            pn = p-1
            ret = Xm - pow(2, N-1-i)%pn
        else:
            # p->p+1
            pn = p+1
            ret = Xp + pow(2, N-1-i)%pn
        ret %= pn
        cnt = 1
        while ret > 0:
            ret %= pc(ret)
            cnt += 1
        return cnt

def main():
    for i in range(N):
        ret = f(i)
        print(ret)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#20200711_D
N =  int(input())
X = input()
line = []
counter = 0
def popcount(n): #2進数を与えて1の数を10進数で返す
    return n.count("1")
popX =  popcount(X)

if popX != 1:
    line.append(int(X,2) % (popX -1))
else:
    line.append(1)
    
line.append(int(X,2) % (popX +1))
# print('int(X,2', int(X,2))
# print('line = ' , line)


for i in range(N):
    #print('i=' + str(i))
    counter = 0
    
    if X[i] == '0':
        Xi = '0b' + X[:i] + '1' + X[i+1:]
        s = 1
    else:
        Xi = '0b'  + X[:i] + '0' + X[i+1:]
        s = 0
    #print('Xi =' + Xi , 's = ' + str(s))
    
    if int(Xi, 0) == 0:
        print(counter)
    else:
        if s == 0:
            Xi = (line[0] - (2**(N-i-1) % (popX -1)))%(popX-1)
        else:
            Xi = (line[1] + (2**(N-i-1) % (popX +1)))%(popX+1)
        counter += 1
        #print(Xi)
    
        while Xi >0:
            Xi = Xi % popcount(bin(Xi))
            
            counter +=1
    
        #print( 'counter = ' + str(counter))
        print(counter)

Submission status: Time Limit Exceeded

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


def f(n):
    if n == 0:
        return 0
    else:
        return 1+f(n % popcount(n))
N = int(input())
X = input()
for n in range(N):
    tmp = list(X)
    if tmp[n]=='0':
        tmp[n] = '1'
    else:
        tmp[n] = '0'
    tmp = ''.join(tmp)
    print(f(int(tmp,2)))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = str(input())
num_X = int(X,2)

bit_caunt = 0
for i in range(N):
    if X[i] == '1':
        bit_caunt += 1

        
bit = [0]*(N+1)
bit[1] = 1
for i in range(1,N+1):
    p = 2**i
    if p > N:
        break
    bit[p] = 1
    for j in range(p+1,2*p):
        if j > N:
            break
        bit[j] = bit[j-p] + 1




b = num_X % (bit_caunt+1)
if bit_caunt != 1:
    c = num_X % (bit_caunt-1)

for i in range(N):
    ans = 0
    if X[i] == '1':
        re_X = num_X - 2**(N-1-i)
        if re_X != 0:
            pop = bit_caunt - 1
            re_X = (c - 2**(N-1-i)%pop)%pop
            ans += 1
    else:
        re_X = num_X + 2**(N-1-i)
        if re_X != 0:
            pop = bit_caunt + 1
            re_X = (b + 2**(N-1-i)%pop)%pop
            ans += 1
         
    while re_X != 0:
        pop = bit[re_X]
        re_X %= pop
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = str(input())
num_X = int(X,2)
bit_caunt = 0
for i in range(N):
    if X[i] == '1':
        bit_caunt += 1

bit = [0]*N
for i in range(N):
    bit[i] = bin(i).count('1')



b = num_X % (bit_caunt+1)
if bit_caunt != 1:
    c = num_X % (bit_caunt-1)

for i in range(N):
    ans = 0
    if X[i] == '1':
        re_X = num_X - 2**(N-1-i)
        if re_X != 0:
            pop = bit_caunt - 1
            re_X = (c - 2**(N-1-i)%pop)%pop
            ans += 1
    else:
        re_X = num_X + 2**(N-1-i)
        if re_X != 0:
            pop = bit_caunt + 1
            re_X = (b + 2**(N-1-i)%pop)%pop
            ans += 1
         
    while re_X != 0:
        pop = bit[re_X]
        re_X %= pop
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
#関数リスト
import sys
from collections import defaultdict
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def bin2dec(target):
    out = 0
    index = 0
    while target > 0:
        out += (target % 10) * 2**index
        target //= 10
        index += 1
    return out

n = I()
x = I()

#２進数にした際の桁数
keta = defaultdict(int)
keta[1] = 1
keta[2] = 1
for i in range(2, n+1):
    keta[i] = (i & 1) + keta[i>>1]

#操作回数
d = defaultdict(int)
d[1] = 1
d[2] = 1
d[3] = 2
for i in range(2, n+1):
    amari = i % keta[i]
    d[i] = d[amari] + 1

num = bin2dec(x)
K = 0
for i in range(n):
    if (num >> i) & 1 == 1:
        K += 1

for i in range(n-1,-1,-1):
    temp1 = num >> i
    temp2 = num
    #bit反転
    if temp1 & 1 == 0:
        temp2 += 2**i
        if temp2 != 0:
            print(d[temp2 % (K+1)]+1)
        else:
            print(0)
    else:
        temp2 += 2**i - 2**(i+1)
        if temp2 != 0:
            print(d[temp2 % (K-1)]+1)
        else:
            print(0)

Submission status: Time Limit Exceeded

Solution code:
def popcount(n):
    #整数nを2進数表現の文字列に変えて、文字列メソッドで"1"の数をカウント
    return bin(n).count("1")

def f(n):
    #「n を popcount(n) で割ったあまりに置き換える」という操作を繰り返した際に
    # n が 0 になるまでの操作回数
    counter = 0
    if n == 0:
        return 0
    while n != 0:
        n = n % popcount(int(n))
        counter += 1
    return counter

def main():
    n = int(input())
    x = input()
    digit = len(x)
    default_popcount = popcount(int(x,2)) #Xの最初のpopcount
    digit_weight = 2 ** digit

    for i,c in enumerate(x):
        digit_weight = digit_weight // 2
        if c == "1":
            #'1'を1個反転させる→"1"の数が1減る
            temp_popcount = default_popcount - 1
            temp_x = int(x,2) - digit_weight
            #print(bin(temp_x))
            if temp_popcount == 0:
                print(0)
                continue
            temp_x %= temp_popcount
            print(f(temp_x) + 1)
        else:
            temp_popcount = default_popcount + 1
            temp_x = int(x,2) + digit_weight
            #print(bin(temp_x))
            if temp_popcount == 0:
                print(0)
                continue
            temp_x %= temp_popcount
            print(f(temp_x) + 1)





if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def popcount(n):
    #整数nを2進数表現の文字列に変えて、文字列メソッドで"1"の数をカウント
    return bin(n).count("1")

def f(n):
    #「n を popcount(n) で割ったあまりに置き換える」という操作を繰り返した際に
    # n が 0 になるまでの操作回数
    counter = 0
    if n == 0:
        return 0
    while n != 0:
        n = n % popcount(int(n))
        counter += 1
    return counter

def main():
    n = int(input())
    x = input()
    digit = len(x)
    default_popcount = popcount(int(x,2)) #Xの最初のpopcount
    print()

    for i,c in enumerate(x):
        digit_weight = 2 ** ((digit - i) -1)
        if c == "1":
            #'1'を1個反転させる→"1"の数が1減る
            temp_popcount = default_popcount - 1
            temp_x = int(x,2) - digit_weight
            #print(bin(temp_x))
            if temp_popcount == 0:
                print(0)
                continue
            temp_x %= temp_popcount
            print(f(temp_x) + 1)
        else:
            temp_popcount = default_popcount + 1
            temp_x = int(x,2) + digit_weight
            #print(bin(temp_x))
            if temp_popcount == 0:
                print(0)
                continue
            temp_x %= temp_popcount
            print(f(temp_x) + 1)





if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = input()
c = x.count("1")


for i in range(n):
    a = int(x[i])
    if a == 1:
        a = 0
        cc = c - 1
    else:
        a = 1
        cc = c + 1
    ref = int(x[:i] + str(a) + x[i + 1:], 2)
    cnt = 0
    if cc != 0:
        ref = ref%cc
        cnt += 1
    while ref > 0:
        bitcnt = bin(ref).count("1")
        ref = ref%bitcnt
        cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = str(input())
num_X = int(X,2)
bit_caunt = 0
for i in range(N):
    if X[i] == '1':
        bit_caunt += 1


b = num_X % (bit_caunt+1)
if bit_caunt != 1:
    c = num_X % (bit_caunt-1)

for i in range(N):
    ans = 0
    if X[i] == '1':
        re_X = num_X - 2**(N-1-i)
        if re_X != 0:
            pop = bit_caunt - 1
            re_X = (c - 2**(N-1-i)%pop)%pop
            ans += 1
    else:
        re_X = num_X + 2**(N-1-i)
        if re_X != 0:
            pop = bit_caunt + 1
            re_X = (b + 2**(N-1-i)%pop)%pop
            ans += 1
         
    while re_X != 0:
        pop = bin(re_X).count('1')
        re_X %= pop
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = str(input())
num_X = int(X,2)
bit_caunt = 0
for i in range(N):
    if X[i] == '1':
        bit_caunt += 1

for i in range(N):
    if X[i] == '1':
        re_X = num_X - 2**(N-1-i)
        pop = bit_caunt - 1
    else:
        re_X = num_X + 2**(N-1-i)
        pop = bit_caunt + 1
    ans = 0
    if re_X != 0:
        re_X %= pop
        ans += 1     
    while re_X != 0:
        pop = bin(re_X).count('1')
        re_X %= pop
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

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

def popcount(n):
    bin_num = bin(n)
    one = 0
    for c in bin_num:
        if c == "1":
            one += 1
    return one

def zero(n, popcount):
    if n == 0:
        return 0
    n %= popcount(n)
    return 1+zero(n,popcount)

l = []


for i in range(len(X)):
    tmp = [ e for e in X]
    if tmp[i] == "1":
        tmp[i] = "0"
    elif tmp[i] == "0":
        tmp[i] = "1"
    tmp = "".join(tmp)
    n = int(tmp, 2)
    l.append(zero(n, popcount))

tmp = "001"
n = int(tmp, 2)

for e in l:
    print(e)