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 functools import lru_cache
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


@lru_cache(maxsize=None)
def F(n):
    if n == 0:
        return 0
    return F(n % pop_count(n)) + 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] = F(m) + 1

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

Submission status: Time Limit Exceeded

Solution code:
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)
        m10 += pow(2, i, pc - 1)


memo = [-1] * 200005


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


def F(n):
    if memo[n] != -1:
        return memo[n]
    if n == 0:
        return 1
    memo[n] = F(n % pop_count(n)) + 1
    return memo[n]


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] = F(m)

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

Submission status: Time Limit Exceeded

Solution code:
import copy
 
# 二進数のビット数
digit_n = int(input())
# 二進数
bit_num = list(input())
# 元の二進数に含まれる1の個数を算出
org_num_1 = bit_num.count('1')
# 二進数の各ビットを反転した二進数を格納する配列を初期化
xor_list = []
# 各ビットを反転した二進数を作成
for i in range(digit_n):
    xor_list = copy.copy(bit_num)
    bit_i = 1^int(bit_num[i])
    xor_list[i] = str(bit_i)
    # 割る数を二進数に出現する1の数で初期化
    div_num_1 = org_num_1 + (-1)**(1 + bit_i)
    # 各ビットを反転した二進数を二進数に含まれている1の個数で割った剰余に置き換えて、剰余が0になるまでの操作回数を出力
    # 割る数を二進数表記の文字列に変換
    sam_num = "0b"+''.join(xor_list)
    #剰余を格納する変数に反転した二進数を文字列から数値に変換した値をセットして初期化
    surplus = int(sam_num,0)
    # 操作回数を格納する変数に0をセットして初期化
    l_count = 0
    while(surplus != 0):
        l_count += 1
        surplus = surplus % div_num_1
        div_num_1 = bin(surplus).count('1')
    print(l_count)

Submission status: Time Limit Exceeded

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

Count = X.count('1')


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

for i in range(N):
    if X[i] == '0':
        print(f(int(X,2)+2**(N-1-i)))
    else:
        print(f(int(X,2)-2**(N-1-i)))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    X = input()

    cnt_init = X.count("1")
    x_init = int(X, 2)
    for i in range(n):
        if X[i] == "0":
            cnt = cnt_init + 1
            x = (x_init + pow(2, (n - i - 1), cnt)) % cnt
            res = 1
        else:
            cnt = cnt_init - 1
            if cnt != 0:
                x = (x_init - pow(2, (n - i - 1), cnt)) % cnt
                res = 1
            else:
                x = 0
                res = 0

        while x:
            cnt = bin(x).count("1")
            x %= cnt
            res += 1
        print(res)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    X = input()

    cnt_init = X.count("1")
    for i in range(n):
        if X[i] == "0":
            cnt = cnt_init + 1
            x = (int(X, 2) + pow(2, (n - i - 1), cnt)) % cnt
            res = 1
        else:
            cnt = cnt_init - 1
            if cnt != 0:
                x = (int(X, 2) - pow(2, (n - i - 1), cnt)) % cnt
                res = 1
            else:
                x = 0
                res = 0

        while x:
            cnt = bin(x).count("1")
            x %= cnt
            res += 1
        print(res)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

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

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

def f(n):
  i = 0
  while True:
    if (n > 0):
      n = int(n % popcount(n))
    else:
      break
    
    i += 1
    if n == 0:
      break
  
  return(i)

for i in range(len(X)):
  Xd = []

  if X[i] == '1':
    Xd = X[:i] + '0' + X[i+1:]
  else:
    Xd = X[:i] + '1' + X[i+1:]

  print("{}".format(f(int(Xd, 2))))

Submission status: Time Limit Exceeded

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

def popcount(n):
  count = 0
  bin_n = bin(n)[2:]
  for i in range(len(bin_n)):
    if bin_n[i] == '1':
      count += 1
  
  return(count)

def f(n):
  i = 0
  while True:
    if (n > 0):
      n = n % popcount(n)
    else:
      break
    
    i += 1
    if n == 0:
      break
  
  return(i)

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

  if X[i] == '1':
    Xd = X[:i] + '0' + X[i+1:]
  else:
    Xd = X[:i] + '1' + X[i+1:]

  print("{}".format(f(int(Xd, 2))))

Submission status: Time Limit Exceeded

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

def popcount(x):
  return bin(x).count("1")
p=X.count('1')
pl=a%(p+1)
if popcount(a)!=1:
  mi=a%(p-1)

def f(x):
  if x==0:
    return 1
  else:
    return f(x%popcount(x))+1

for i in range(N):
  if X[i]=='0':
    b=pl
    b+=pow(2,N-i-1,p+1)
    b%=p+1
  else:
    if popcount(a)!=1:
      b=mi
      b-=pow(2,N-i-1,p-1)
      b%=p-1
    else:
      print(0)
      continue
  print(f(b))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input().strip()

d = sum(1 if x == '1' else 0 for x in s)

num, p = 0, 1
for x in reversed(s):
    if x == '1':
        num += p
    p <<= 1

def pct(x):
    res = 0
    while x:
        res += x & 1
        x >>= 1
    return res

def solve(x, cnt):
    res = 0
    while x:
        x %= cnt
        cnt = pct(x)
        res += 1
    return res

for x in s:
    p >>= 1
    if x == '1':
        print(solve(num ^ p, d - 1))
    else:
        print(solve(num ^ p, d + 1))

Submission status: Time Limit Exceeded

Solution code:
def popcount(x): #xは10進数の整数
    return bin(x).count('1')
ma = 2*10**5
dp = [0 for i in range (ma)]
for i in range (1, ma):
    dp[i] = dp[i % popcount(i)] + 1
def solve(N, x):
    p = popcount(int(x, 2))
    nowp_p = int(x, 2) % (p+1)
    if p-1 != 0: 
        nowp_m = int(x, 2) % (p-1)
    x = list(x)#list
    for i in range(N):
        if x[i] == '0':
            print(dp[(nowp_p + 2**(N-i-1)) % (p + 1)] + 1)
        elif x[i] == '1':
            if p == 1:
                print(0)
            else:
                print(dp[(nowp_m - 2**(N-i-1) + p - 1) % (p - 1)] + 1)
N = int(input())
x = input() #str
solve(N, x)

Submission status: Time Limit Exceeded

Solution code:
def popcount(x): #xは10進数の整数
    return bin(x).count('1')
def f(x): #xは10進数の整数
    if x == 0:
        return 0
    else:
        return f(x % popcount(x)) + 1
def solve(N, x):
    p = popcount(int(x, 2))
    nowp_p = int(x, 2) % (p+1)
    if p-1 != 0: 
        nowp_m = int(x, 2) % (p-1)
    x = list(x)#list
    for i in range(N):
        if x[i] == '0':
            print(f((nowp_p + 2**(N-i-1)) % (p + 1)) + 1)
        elif x[i] == '1':
            if p == 1:
                print(0)
            else:
                print(f((nowp_m - 2**(N-i-1) + p - 1) % (p - 1)) + 1)
N = int(input())
x = input() #str
solve(N, x)

Submission status: Time Limit Exceeded

Solution code:
from copy import *
def popcount(x): #xは10進数の整数
    return bin(x).count('1')
def f(x, p): #xは10進数の整数
    if x == 0:
        return 0
    else:
        return f(x % popcount(x), popcount(x)) + 1
def solve(N, x):
    p = popcount(int(x, 2))
    x = list(x)#list
    for i in range(N):
        y = copy(x)
        now_p = p
        if x[i] == '0':
            y[i] = '1'
            now_p += 1
        elif x[i] == '1':
            y[i] = '0'
            now_p -= 1
        print(f(int(''.join(y), 2), now_p))
N = int(input())
x = input() #str
solve(N, x)

Submission status: Time Limit Exceeded

Solution code:
class S:
    def __init__(self, N):
        self.DP = [-1 for i in range(2**N)]
    def popcount(self, n):
        count = 0
        for i in range(n):
            if ((n >> i) & 1):
                count += 1
        return count
    def f(self, N, p):
        if N == 0:
            self.DP[0] = 0
            return 0
        elif self.DP[N] != -1:
            return self.DP[N]
        else:
            self.DP[N] = self.f(N % p, self.popcount(N % p)) + 1
            return self.DP[N]
    def solve(self, N, X):
        p = self.popcount(int(''.join(X), 2))
        q = p
        for i in range(N):
            x_i = X[i]
            if x_i == str(1):
                X[i] = str(0)
                p -= 1
            elif x_i == str(0):
                X[i] = str(1)
                p += 1
            print(self.f(int(''.join(X), 2), p))
            X[i] = x_i
            p = q
N  = int(input())
X = list(input())
s = S(N)
s.solve(N, X)

Submission status: Time Limit Exceeded

Solution code:
def popcount(n):
    count = 0
    for i in range(n):
        if ((n >> i) & 1):
            count += 1
    return count
def f(N, p):
    if N == 0:
        return 0
    else:
        return (f(N % p, popcount(N % p))+1)
def solve(N, X):
    p = popcount(int(''.join(X), 2))
    q = p
    for i in range(N):
        x_i = X[i]
        if x_i == str(1):
            X[i] = str(0)
            p -= 1
        elif x_i == str(0):
            X[i] = str(1)
            p += 1
        print(f(int(''.join(X), 2), p))
        X[i] = x_i
        p = q
N  = int(input())
X = list(input())
solve(N, X)

Submission status: Time Limit Exceeded

Solution code:
import copy

# 二進数のビット数
digit_n = int(input())
# 二進数
bit_num = list(input())

# 二進数の各ビットを反転した二進数を格納する配列を初期化
xor_list = ['0'] * digit_n
# 各ビットを反転した二進数を作成
for i in range(digit_n):
    xor_list = copy.copy(bit_num)
    xor_list[i] = str(1^int(bit_num[i]))
    # 各ビットを反転した二進数を二進数に含まれている1の個数で割った剰余に置き換えて、剰余が0になるまでの操作回数を出力
    sam_num = "0b"+''.join(xor_list)
    #剰余を格納する変数に反転した二進数を10進数に変換した数値をセットして初期化
    surplus = int(sam_num, 0)
    # 割る数を二進数に出現する1の数で初期化
    div = xor_list.count('1')
    # 操作回数を格納する変数を0で初期化
    l_count = 0
    while(surplus != 0):
        l_count += 1
        surplus = surplus % div
        div = str(bin(surplus)).count('1')
    print(l_count)

Submission status: Time Limit Exceeded

Solution code:
import copy

# 二進数のビット数
digit_n = int(input())
# 二進数
bit_num = list(input())

# 二進数の各ビットを反転した二進数を格納する配列を初期化
xor_list = [[0] * digit_n for i in range(digit_n)]
# 各ビットを反転した二進数を作成
for i in range(digit_n):
    xor_list[i] = copy.copy(bit_num)
    xor_list[i][i] = str(1^int(bit_num[i]))
    # 各ビットを反転した二進数を二進数に含まれている1の個数で割った剰余に置き換えて、剰余が0になるまでの操作回数を出力
    sam_num = "0b"+''.join(xor_list[i])
    #剰余を格納する変数に反転した二進数を10進数に変換した数値をセットして初期化
    surplus = int(sam_num, 0)
    # 割る数を二進数に出現する1の数で初期化
    div = xor_list[i].count('1')
    # 操作回数を格納する変数を0で初期化
    l_count = 0
    while(surplus != 0):
        l_count += 1
        surplus = surplus % div
        div = str(bin(surplus)).count('1')
    print(l_count)

Submission status: Time Limit Exceeded

Solution code:
import copy
#テスト出力 test = 1
test = 0
# 二進数のビット数
digit_n = int(input())
# 二進数
bit_num = list(input())
if test == 1:
    print(''.join(bit_num))

# 二進数の各ビットを反転した二進数を格納する配列を初期化
xor_list = [[0] * digit_n for i in range(digit_n)]
# 各ビットを反転した二進数を作成
for i in range(digit_n):
    xor_list[i] = copy.copy(bit_num)
    xor_list[i][i] = str(1^int(bit_num[i]))
    # 各ビットを反転した二進数を二進数に含まれている1の個数で割った剰余に置き換えて、剰余が0になるまでの操作回数を出力
    sam_num = "0b"+''.join(xor_list[i])
    #剰余を格納する変数に反転した二進数を10進数に変換した数値をセットして初期化
    surplus = int(sam_num, 0)
    # 割る数を二進数に出現する1の数で初期化
    div = xor_list[i].count('1')
    # 操作回数を格納する変数を0で初期化
    l_count = 0
    if test == 1:
        print("sam_num="+str(sam_num)+", surplus="+str(surplus))
    while(surplus != 0):
        l_count += 1
        surplus = surplus % div
        div = str(bin(surplus)).count('1')
    print(l_count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input().rstrip())
x = input().rstrip()
ans = [0 for _ in range(n)]
temp_list = [0 for _ in range(n)]
m_list = [0 for _ in range(n)]
d_sum = 1
for i in range(n):
  if int(x[-1-i]) == 1:
    for j in range(n):
      if j != i:
        temp_list[-1-j] += d_sum
        m_list[-1-j] += 1
  else:
    temp_list[-1-i] += d_sum
    m_list[-1-i] += 1
  d_sum *=2
for i in range(n):
  while True:
    if temp_list[i] != 0:
      temp_list[i] %= m_list[i]
      ans[i] += 1
      c = 0
      temp = temp_list[i]
      while True:
        if temp != 0:
          c += temp%2
          temp //= 2
        else:
          break
      m_list[i] = c
    else:
      break

for i in range(n):
  print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = input()
ncnt = X.count('1')

for i in range(N):
    tmp = X
    tmpcnt = ncnt
    cnt = 0
    if tmp[i] == '0':
        tmp = tmp[:i] + '1' + tmp[i + 1:]
        tmpcnt += 1
    else:
        tmp = tmp[:i] + '0' + tmp[i + 1:]
        tmpcnt -= 1
    f = int(tmp, 2)
    while True:
        if f == 0:
            break

        m, d = divmod(f, tmpcnt)
        cnt += 1
        f = d
        tmpcnt = bin(f).count('1')
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def dtb(n):  return bin(n).count("1")



t=int(input());rpta=[]
main=list(input())
original=main.copy()

for i in range(t):

    count=0
    main=original.copy()
    if(main[i]=='0'): main[i]='1'
    else: main[i]='0'

    temp=int("".join(main),2)
        
    while(temp!=0):
        momento=dtb(temp)
        temp=temp%momento
        count=count+1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
def dtb(n):  
    sum_1=0
    bin_rep=bin(n)[2:]
    for i in bin_rep:
        sum_1=sum_1+int(i)
    return sum_1 


t=int(input());rpta=[]
main=list(input())
original=main.copy()

for i in range(t):

    count=0
    main=original.copy()
    if(main[i]=='0'): main[i]='1'
    else: main[i]='0'

    temp=int("".join(main),2)
        
    while(temp!=0):
        momento=dtb(temp)
        temp=temp%momento
        count=count+1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
def dtb(n):  return bin(n).replace("0b", "")  

t=int(input());rpta=[]
main=list(input())
original=main.copy()

for i in range(t):

    count=0
    main=original.copy()
    if(main[i]=='0'): main[i]='1'
    else: main[i]='0'

    temp=int("".join(main),2)
        
    while(temp!=0):
        momento=dtb(temp);number_ones=0
        for i in momento:
            if(i=='1'): number_ones=number_ones+1
        temp=temp%number_ones
        count=count+1
    print(count)

Submission status: Time Limit Exceeded

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

X_int = int(X_bin, 2)  # bin => int


def calc_bin_cnt(next_int):
    if next_int == 0:
        return 0
    next_bin = bin(next_int)[2:]
    # popcount
    cnt = 0
    for i in next_bin:
        if i == '1':
            cnt += 1
    return cnt


def calc_ans(next_int, cnt=None):
    if next_int == 0:
        return 0
    if cnt is None:
        cnt = calc_bin_cnt(next_int)
    next_int = next_int % cnt
    if next_int > 0:
        ans = calc_ans(next_int) + 1
    else:
        ans = 1
    return ans


X_cnt = calc_bin_cnt(X_int)
for i in range(N):
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1)), X_cnt-1))
    else:
        print(calc_ans(X_int + (2**(N-i-1)), X_cnt+1))

Submission status: Time Limit Exceeded

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

X_int = int(X_bin, 2)  # bin => int


def calc_bin_cnt(next_int):
    if next_int == 0:
        return 0
    next_bin = bin(next_int)[2:]
    # popcount
    cnt = 0
    for i in next_bin:
        if i == '1':
            cnt += 1
    return cnt


def calc_ans(next_int, cnt=None):
    if next_int == 0:
        return 0
    if cnt is None:
        cnt = calc_bin_cnt(next_int)
    next_int = next_int % cnt
    if next_int > 0:
        ans = calc_ans(next_int) + 1
    else:
        ans = 1
    return ans


#X_cnt = calc_bin_cnt(X_int)
X_cnt = X_bin.count('1')
for i in range(N):
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1)), X_cnt-1))
    else:
        print(calc_ans(X_int + (2**(N-i-1)), X_cnt+1))

Submission status: Time Limit Exceeded

Solution code:
import math


N = int(input())
X_bin = input()

X_int = int(X_bin, 2)  # bin => int


def calc_bin_cnt(next_int):
    return bin(next_int).count('1')
    if next_int == 0:
        return 0
    '''
    next_bin = bin(next_int)[2:]
    # popcount
    cnt = 0
    for i in next_bin:
        if i == '1':
            cnt += 1
    '''
    cnt = 0
    n = int(math.log2(next_int))
    for i in range(n, -1, -1):
        if next_int >= 2**i:
            next_int -= 2**i
            cnt += 1
    return cnt


def calc_ans(next_int, cnt=None):
    if next_int == 0:
        return 0
    if cnt is None:
        cnt = calc_bin_cnt(next_int)
    next_int = next_int % cnt
    if next_int > 0:
        ans = calc_ans(next_int) + 1
    else:
        ans = 1
    return ans


#X_cnt = calc_bin_cnt(X_int)
X_cnt = X_bin.count('1')
for i in range(N):
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1)), X_cnt-1))
    else:
        print(calc_ans(X_int + (2**(N-i-1)), X_cnt+1))

Submission status: Time Limit Exceeded

Solution code:
import math


N = int(input())
X_bin = input()

X_int = int(X_bin, 2)  # bin => int


def calc_bin_cnt(next_int):
    return bin(next_int).count('1')
    if next_int == 0:
        return 0
    '''
    next_bin = bin(next_int)[2:]
    # popcount
    cnt = 0
    for i in next_bin:
        if i == '1':
            cnt += 1
    '''
    cnt = 0
    n = int(math.log2(next_int))
    for i in range(n, -1, -1):
        if next_int >= 2**i:
            next_int -= 2**i
            cnt += 1
    return cnt


def calc_ans(next_int, cnt=None):
    if next_int == 0:
        return 0
    if cnt is None:
        cnt = calc_bin_cnt(next_int)
    next_int = next_int % cnt
    if next_int > 0:
        ans = calc_ans(next_int) + 1
    else:
        ans = 1
    return ans


X_cnt = calc_bin_cnt(X_int)
for i in range(N):
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1)), X_cnt-1))
    else:
        print(calc_ans(X_int + (2**(N-i-1)), X_cnt+1))

Submission status: Time Limit Exceeded

Solution code:
import math


N = int(input())
X_bin = input()

X_int = int(X_bin, 2)  # bin => int


def calc_bin_cnt(next_int):
    if next_int == 0:
        return 0
    '''
    next_bin = bin(next_int)[2:]
    # popcount
    cnt = 0
    for i in next_bin:
        if i == '1':
            cnt += 1
    '''
    cnt = 0
    n = int(math.log2(next_int))
    for i in range(n, -1, -1):
        if next_int >= 2**i:
            next_int -= 2**i
            cnt += 1
    return cnt


def calc_ans(next_int, cnt=None):
    if next_int == 0:
        return 0
    if cnt is None:
        cnt = calc_bin_cnt(next_int)
    next_int = next_int % cnt
    if next_int > 0:
        ans = calc_ans(next_int) + 1
    else:
        ans = 1
    return ans


X_cnt = calc_bin_cnt(X_int)
for i in range(N):
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1)), X_cnt-1))
    else:
        print(calc_ans(X_int + (2**(N-i-1)), X_cnt+1))

Submission status: Time Limit Exceeded

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

X_int = int(X_bin, 2)  # bin => int


def calc_bin_cnt(next_int):
    '''
    next_bin = bin(next_int)[2:]
    # popcount
    cnt = 0
    for i in next_bin:
        if i == '1':
            cnt += 1
    '''
    cnt = bin(next_int).count('1')
    return cnt


def calc_ans(next_int, cnt=None):
    if next_int == 0:
        return 0
    if cnt is None:
        cnt = calc_bin_cnt(next_int)
    next_int = next_int % cnt
    if next_int > 0:
        ans = calc_ans(next_int) + 1
    else:
        ans = 1
    return ans


X_cnt = calc_bin_cnt(X_int)
for i in range(N):
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1)), X_cnt-1))
    else:
        print(calc_ans(X_int + (2**(N-i-1)), X_cnt+1))

Submission status: Time Limit Exceeded

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

def popcount(x):
  return bin(x).count("1")
  
for i in reversed(range(N)):
  mask=1<<i
  p=X^mask
  cnt=0
  while p>0:
    p=p%popcount(p)
    cnt+=1
  print(cnt)

Submission status: Time Limit Exceeded

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

def popcount(x):
  return bin(x).count("1")
  
for i in reversed(range(N)):
  mask=1<<i
  p=X^mask
  cnt=0
  while p>0:
    p=p%popcount(p)
    cnt+=1
  print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
#N, K = (int(i) for i in input().split())
#B = [int(x) for x in input().split()]
#A = [[int(i) for i in input().split()] for i in range(N)]


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


def f(x, cur):
    #print(x, cur)
    cnt = cur
    tmp = x
    while tmp:
        tmp = tmp%my_popcount(tmp)
        cnt +=1
    return cnt


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

Xint = int(X, 2)
popcountX = X.count("1")
#print("test", Xint, popcountX)
plus = Xint%(popcountX+1)
minus = 0
if popcountX != 1:
    minus = Xint%(popcountX-1)

X = list(X)
for i in range(N):
    if X[i] == "0":
        #print("arg", Xint%(popcountX+1), (2**(N-1-i))%(popcountX+1))
        print(f((plus + (2**(N-1-i))%(popcountX+1))%(popcountX+1), 1))
    else:
        if popcountX == 1:
            print(0)
        else:
            print(f((minus - (2**(N-1-i))%(popcountX-1))%(popcountX-1), 1))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
#N, K = (int(i) for i in input().split())
#B = [int(x) for x in input().split()]
#A = [[int(i) for i in input().split()] for i in range(N)]


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


def f(x, cur):
    #print(x, cur)
    if x == 0:
        return cur
    return f(x%my_popcount(x), cur+1)

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

Xint = int(X, 2)
popcountX = X.count("1")
#print("test", Xint, popcountX)
plus = Xint%(popcountX+1)
minus = 0
if popcountX != 1:
    minus = Xint%(popcountX-1)

X = list(X)
for i in range(N):
    if X[i] == "0":
        #print("arg", Xint%(popcountX+1), (2**(N-1-i))%(popcountX+1))
        print(f((plus + (2**(N-1-i))%(popcountX+1))%(popcountX+1), 1))
    else:
        if popcountX == 1:
            print(0)
        else:
            print(f((minus - (2**(N-1-i))%(popcountX-1))%(popcountX-1), 1))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
#N, K = (int(i) for i in input().split())
#B = [int(x) for x in input().split()]
#A = [[int(i) for i in input().split()] for i in range(N)]


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


def f(x, cur):
    #print(x, cur)
    if x == 0:
        return cur
    return f(x%my_popcount(x), cur+1)

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

Xint = int(X, 2)
popcountX = X.count("1")
#print("test", Xint, popcountX)
plus = Xint%(popcountX+1)
minus = 0
if popcountX != 1:
    minus = Xint%(popcountX-1)

for i in range(N):
    if X[i] == "0":
        #print("arg", Xint%(popcountX+1), (2**(N-1-i))%(popcountX+1))
        print(f((plus + (2**(N-1-i))%(popcountX+1))%(popcountX+1), 1))
    else:
        if popcountX == 1:
            print(0)
        else:
            print(f((minus - (2**(N-1-i))%(popcountX-1))%(popcountX-1), 1))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
#N, K = (int(i) for i in input().split())
#B = [int(x) for x in input().split()]
#A = [[int(i) for i in input().split()] for i in range(N)]


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


def f(x, cur):
    #print(x, cur)
    if x == 0:
        return cur
    return f(x%my_popcount(x), cur+1)

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

Xint = int(X, 2)
popcountX = X.count("1")
#print("test", Xint, popcountX)

for i in range(N):
    if X[i] == "0":
        #print("arg", Xint%(popcountX+1), (2**(N-1-i))%(popcountX+1))
        print(f((Xint%(popcountX+1) + (2**(N-1-i))%(popcountX+1))%(popcountX+1), 1))
    else:
        if popcountX == 1:
            print(0)
        else:
            print(f((Xint%(popcountX-1) - (2**(N-1-i))%(popcountX-1))%(popcountX-1), 1))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
import math
import copy


def minu_int(i):
    return -1*int(i)


def zz():
    return list(map(int, sys.stdin.readline().split()))


def z():
    return int(sys.stdin.readline())


def S():
    return sys.stdin.readline()


def C(line):
    return [sys.stdin.readline() for _ in range(line)]


def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]


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


N = z()
X = S()

for i in range(N):
    x = int(X, 2)
    if(X[i] == '0'):
        x += pow(2, N-i-1)
    else:
        x -= pow(2, N-i-1)
    # print(bin(x))
    ans = 0
    while x != 0:
        x = x % pop_count(x)
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
#N, K = (int(i) for i in input().split())
#B = [int(x) for x in input().split()]
#A = [[int(i) for i in input().split()] for i in range(N)]


def my_popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f

def f(x, cur):
    #print(x, cur)
    if x == 0:
        return cur
    return f(x%my_popcount(x), cur+1)

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

Xint = int(X, 2)
popcountX = X.count("1")
#print("test", Xint, popcountX)

for i in range(N):
    if X[i] == "0":
        #print("arg", Xint%(popcountX+1), (2**(N-1-i))%(popcountX+1))
        print(f((Xint%(popcountX+1) + (2**(N-1-i))%(popcountX+1))%(popcountX+1), 1))
    else:
        if popcountX == 1:
            print(0)
        else:
            print(f((Xint%(popcountX-1) - (2**(N-1-i))%(popcountX-1))%(popcountX-1), 1))