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:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    mem = defaultdict(lambda : None)
    mem[0] = 0
    cnt = [0]
    for _ in range(18):
        cnt = [x+i for i in range(2) for x in cnt]
    def dfs(x):
        if mem[x] is not None:
            return mem[x]
        p = cnt[x]
        res = dfs(x%p)+1
        mem[x] = res
        return res

    ans = [dfs(i) for i in range(200001)]
    n = I()
    x = list(map(int, input()))
    cnt_x = sum(x)
    s = 0
    p = 1
    l = [0]*n
    for i in range(n)[::-1]:
        xi = x[i]
        if xi:
            l[i] = p
        p <<= 1
    cnt_p = cnt_x+1
    rp = [li%cnt_p for li in l]
    sp = sum(rp)%cnt_p
    if cnt_x > 1:
        cnt_m = cnt_x-1
        mp = [li%cnt_m for li in l]
        sm = sum(mp)%cnt_m
    p >>= 1
    for i in range(n):
        if x[i]:
            k = cnt_x-1
            if k == 0:
                print(0)
            else:
                a = (sm-p)%k
                print(ans[a]+1)
        else:
            k = cnt_x+1
            a = (sp+p)%k
            print(ans[a]+1)
        p >>= 1
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(500000)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

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

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

def inot(X, i, N):
    return int(X, base=2)^(1<<N-1-i)

@lru_cache(maxsize=1000)
def f(n):
    if n == 0:
        return 0
    else:
        return 1+f(n%bin(n).count('1'))

def main():
    N = ii()
    X = input()
    dic = {}
    for i in range(N):
        Xi = inot(X, i, N)
        print(f(Xi))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(x) for x in input()]
x = 0
for i in a:
    x *= 2
    x += i

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


def solve(x):
    if (x == 0):
        return 0
    d = popcount(x)
    return 1 + solve(x % d)


for i in range(n - 1, -1, -1):
    print(solve(x ^ (1 << i)))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]
def NSTR(n): return [input() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7


def bit_sum(n):
    wa = 0
    while n > 0:
        wa += n & 1
        n >>= 1
    return wa

def bit(n, k):
    return (n >> k) & 1

def main():
    N = INT()
    X = input()
    origX = X
    wa = X.count("1")
    x = 0
    px = 0
    nx = 0
    for c in X:
        x <<= 1
        px <<= 1
        nx <<= 1
        if c == "1":
            x |= 1
            px |= 1
            nx |= 1
        px %= (wa+1)
        if wa != 1:
            nx %= (wa-1)
        else:
            nx %= wa
    if wa == 1:
        nx = None
    # print(px, nx)
    X = x
    # wa+1
    # px = X % (wa+1)
    # if wa != 1:
    #     nx = X % (wa-1)
    # else:
    #     nx = None
    # print(px, nx)

    # 1 ~ Nについて答えを出しておく NlogN
    table = [None]*(N+1)
    table[0] = 0
    table[1] = 1
    for i in range(1, N+1):
        table[i] = table[i % bit_sum(i)] + 1

    for i, c in enumerate(origX):
        count = 0
        x = X ^ (1 << N-i-1)
        if c == "1":
            if x == 0:
                print(0)
                continue
            x = (nx-pow(2, N-i-1, wa-1)) % (wa-1)
            print(table[x]+1)
        else:
            if x == 0:
                print(0)
                continue
            x = (px+pow(2, N-i-1, wa+1)) % (wa+1)
            print(table[x]+1)
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
X=input()
def printf(x,i):
  x=list(x)
  if x[i]=='1':
    x[i]='0'
  else:
    x[i]='1'
  return int(("".join(x)), 2)
def popcount(n):
  return bin(n).count('1')
def f(n):
  count=0
  while n!=0:
    n = n % popcount(n)
    count+=1
  return count
for a in range(N):
  print(f(printf(X,a)))

Submission status: Time Limit Exceeded

Solution code:
import copy
import sys #追加
sys.setrecursionlimit(500*500) #追加

def func(dic, n):
  
  if n in dic:
    return dic[n]
  
  if n == 0:
    return 0
  
  t = bin(n)
  tmp = len(t) - len(t.replace('1','' ))

  n2 = n % tmp
    
  dic[n] = 1 + func(dic, n2)
  
  return dic[n]
   

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

dic = {}

for i in range(n):
  li = list(x)
  
  if li[i] == '1':
    li[i] = '0'
  else:
    li[i] = '1'
    
  x_copy = ''.join(li)
    
  print(func(dic, int(x_copy, 2)))

Submission status: Time Limit Exceeded

Solution code:
import sys
import time
import math
def inpl():
    return list(map(int, input().split()))
st = time.perf_counter()
# ------------------------------

N = int(input())
X = int(input(), 2)
for i in range(N):
	x = X ^ 1<<(N-i-1)
	cnt = 0
	while x!=0:
		cnt+=1
		x = x%(bin(x).count('1'))
	print(cnt)

# ------------------------------
ed = time.perf_counter()
print('time:', ed-st, file=sys.stderr)

Submission status: Time Limit Exceeded

Solution code:
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

import copy

n=ni()
x=[_ for _ in input()]

def popcount(nn):
  ans=0
  while nn>0:
    if nn%2==1:
      ans+=1
    nn//=2
  return ans

def f(nn):
  ans=0
  while nn>0:
    ans+=1
    nn=nn%popcount(nn)
  return ans

for i in range(n):
  xx = copy.copy(x)
  if xx[i]=='1':
    xx[i]='0'
  else:
    xx[i]='1'
  print(f(int(''.join(xx),2)))

Submission status: Time Limit Exceeded

Solution code:
import collections
n = int(raw_input())
x = int(raw_input(),2)
mem = {0:0}

def g(x, mod):
	ximod = 1 % mod
	r = 0
	for i in range(n):
		
		if i: ximod *= 2
		ximod %= mod
		if x & (1 << i):
			r += ximod
			r %= mod
	return r
def f(x):
	if x in mem:
		return mem[x]
	cc=  collections.Counter(bin(x))
	compute = g(x,cc['1'])
	if compute == 0: 
		mem[x] = 1
		return 1
	mem[x] = 1 + f(compute)
	return 1 + f(compute)

for i in range(n - 1, -1, -1):
	print f(x ^ (1 << i))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = str(input())
from functools import lru_cache

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

@lru_cache(maxsize=1000)
def f(m):
    if m == 0:
        return 0
    else:
        amari = m % popcount(m)
        return 1 + f(amari)
    
for i in range(n):
    moji = list(x)
    if moji[i] == "1":
        moji[i] = "0"
    else:
        moji[i] = "1"
    str_moji = "".join(moji)
    print(f(int(str_moji, 2)))

Submission status: Time Limit Exceeded

Solution code:
def popcount(n,res):
    while n !=0:
        bin_str = bin(n)
        x = bin_str.count("1")
        n = n%x
        res += 1
    return res    

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

for i in range(n):    
    if x[i] =="0":
        y = x[:i]+"1"+x[i+1:]
    else:
        y = x[:i] + "0" + x[i+1:]
    print(popcount(int(y,2),0))

Submission status: Time Limit Exceeded

Solution code:
n,x = open(0).read().splitlines()

n = int(n)
size = len(x)
x = int(x,2)

from collections import defaultdict

#count
d = {0:0}

def calc(n):
    if n not in d:
        pop = n % f'{n:b}'.count('1')
        d[n] = calc(pop) + 1
    return d[n]

for i in range(n):
    m = x ^ (1<<(size-i-1))
    print(calc(m))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

n = int(input())
x = input()
num = int(x, 2)


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


# aは1の数
@lru_cache(None)
def calc(a):
    cnt = 1
    while a > 0:
        # print(a)
        temp = popcnt(a)
        a = a % temp
        cnt += 1
    return cnt


ans = [0] * n
cnt = x.count("1")

for i in range(n):
    if x[i] == "1":
        temp = cnt - 1
    else:
        temp = cnt + 1
    t = 1 << (n - i - 1)
    # print(num ^ t, bin(num ^ t)
    if num ^ t:
        ans[i] = calc((num ^ t) % temp)
    else:
        ans[i] = 0
print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
def countSetBits(n): 
    count = 0
    while (n): 
        count += n & 1
        n >>= 1
    return count 

def D():
    N = int(input())
    X = input()
    memo = {}
    def get_steps(n):
        if n == 0:
            return 0
        if n in memo:
            return memo[n]
        ans = 1+get_steps(n%countSetBits(n))
        memo[n] = ans
        return ans
    
    for i in range(N):
        temp = int(X[:i]+('1' if X[i] == '0' else '0')+X[i+1:], 2)
        print(get_steps(temp))
        
D()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x=int(input(),2)
dic={}
def f(x):
    if x in dic:
        return dic[x]
    cnt=0
    for i in bin(x):
        cnt+=i=='1'
    if cnt == 0:
        return 0
    dic[x]=f(x%cnt)+1
    return dic[x]
cnt=0
for i in bin(x):
    cnt+=i=='1'
for i in range(n-1,-1,-1):
    j=x^(1<<i)
    if j==0:
        print(0)
    else :
        if x&(1<<i)==0:
            print(f(j%(cnt+1))+1)
        else :
            print(f(j%(cnt-1))+1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = int(input(),2)
from collections import Counter


def pop_count(n):
    return n%Counter(bin(n))['1']
ans = 0
for i in range(N-1,-1,-1):
    n = X^pow(2,i)
    while n != 0:
        n = pop_count(n)
        ans += 1
    print(ans)
    ans = 0

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
num=int(0)
s=list(s)
bits=int(0)
for i in range(n):
    if(s[i]=='1'):
        bits+=1
i=n-1
curr=int(1)
while(i>=0):
    if(s[i]=='1'):
        num+=curr
    curr*=2
    i-=1
for i in range(n):
    ns=s
    nnum=int(num)
    nbits=int(bits)
    if(ns[i]=='1'):
        ns[i]='0'
        nnum-=(2**(n-i-1))
        nbits-=1
    else:
      	ns[i]='1'
      	nnum+=(2**(n-i-1))
      	nbits+=1
    ans=int(0)
    while(nnum!=0):
        nnum%=nbits
        ans+=1
        nbits=bin(nnum).count('1')
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
from sys import flags
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
x=list(input())
cnt=Counter(x)
x=int("".join(x),2)
# print(x)
# print(math.log2(2*10**5))
# print(cnt)
def wari(now):
    tmp=cnt["1"]
    # print(flag,tmp)
    if flag==1:
        tmp-=1
    else:
        tmp+=1
    # print(tmp)
    if tmp==0:
        return 0
    now%=tmp
    ans=1
    while now:
        cnt2=Counter(bin(now))
        now%=cnt2["1"]
        ans+=1
    return ans

for i in range(n):
    flag=0
    if x&1<<(n-1-i):
        flag=1
        x-=pow(2,(n-1-i))
    else:
        flag=0
        x+=pow(2,(n-1-i))
    # now=int("".join(x),2)
    # print(x)
    print(wari(x))
    # print(x&1<<(n-1-i))
    if x&1<<(n-1-i):
        x-=pow(2,(n-1-i))
    else:
        x+=pow(2,(n-1-i))
    # print(x)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
    n = int(input())
    s = int(input(), 2)
    ans = []
    for i in range(n):
        k = 1 << (n - 1 - i)
        x = k ^ s
        cnt = 0
        while x > 0:
            pc = bin(x).count("1")
            x %= pc
            cnt += 1
        ans.append(cnt)
    print("\n".join(str(y) for y in ans))
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

def popcount(n):
    a = 0
    while n > 0:
         a += n & 1
         n >>= 1
    return a

def f(x):
    a = 0
    while x != 0:
        x = x % popcount(x)
        a += 1
    return a

n = int(input())
x = input().rstrip()

for i in range(n):
    a = str(1 - int(x[i]))
    b = x[:i] + a + x[i+1:]
    print(f(int(b, 2)))

Submission status: Time Limit Exceeded

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

cmap = dict()
pmap = dict()


def pop_count(num):
    try:
        return pmap[num]
    except KeyError:
        res = bin(num).count("1")
        pmap[num] = res
        return res


def f(num):
    if num == 0:
        return 0
    try:
        return cmap[num]
    except KeyError:
        res = f(num % pop_count(num)) + 1
        cmap[num] = res
        return res


for i in range(1, n + 1):
    tmp = x ^ (2 ** (xn - i))
    print(f(tmp))

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy


def popcount(n):
    return sum(map(int, list(f"{n:b}")))


def make_xi(n, i):
    n[i] = "1" if n[i] == "0" else "0"
    return int("".join(n), 2)


def main():
    n = int(input())
    x = list(input())
    ret = 0
    x_i_ret = {}
    for i in range(n):
        _x = deepcopy(x)
        x_i = make_xi(_x, i)
        x_i_origin = deepcopy(x_i)
        ret = 0
        while x_i > 0:
            if x_i in x_i_ret:
                ret += x_i_ret[x_i]
                break
            tmp = popcount(x_i)
            x_i = x_i % tmp
            ret += 1
        else:
            x_i_ret[x_i_origin] = ret

        print(ret)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def popcount(n):
    tmp = 0
    for d in n:
        if d == "1":
            tmp+=1
    return tmp

for i in range(N):
    j = 0
    """
    n = X[0:len(X)-i]
    tmp = ""
    for d in n:
        if d == "0":
            tmp+="1"
        else:
            tmp+="0"
    n = tmp + X[len(X)-i-1:]
    """
    n = X[i]
    if n =="0":
        n="1"
    else:
        n="0"
    n = X[:i]+n+X[i+1:]

    while 1:
        #no = int(format(n, "o"))
        no = int(n, 2)
        if no==0:
            break
        j+=1
        no%=popcount(n)
        n = format(no, "b")
    print(j)

Submission status: Time Limit Exceeded

Solution code:
def f(n):
    ans = 0
    while (n != 0):
        ans += (n % 2)
        n //= 2
    return ans


n = int(input())
s = input()
t = 0;
ans = [0] * 20
for i in range(1, 20):
    j = i
    while (j != 0):
        j %= f(j)
        ans[i]+=1
        
cnt = 0
for i in s:
    t *= 2
    if (i == '1'):
        t += 1
        cnt += 1
for i in range(n - 1, -1, -1):
    q = t    
    nc = cnt
    if (s[n - i - 1] == '0'):
        q += 2 ** (i)
        nc += 1
    else:
        q -= 2 ** (i)
        nc -= 1 
    if (q < 20):
        print(ans[q])
        continue
    q %= nc
    if (q < 20):
        print(ans[q] + 1)
        continue
    q %= f(q)
    print(ans[q] + 2)

Submission status: Time Limit Exceeded

Solution code:
def f(val):
    if val == 0:
        return 0
    re = 0
    tmp = val
    popcount = 0
    while tmp > 0:
        if tmp%2 == 1:
            popcount += 1
        tmp //= 2
    return f(val%popcount) + 1

def pow(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

def main():
    n = int(input())
    X = input()
    x = int(X,2)
    Ans = []
    for i in range(n):
        if X[i] == "0":
            tmp = x + pow(2,n - i - 1)
        else:
            tmp = x - pow(2,n - i - 1)
        Ans.append(f(tmp))
    print(*Ans,sep="\n")


    return
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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


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


# aは1の数
def calc(a):
    cnt = 1
    while a > 0:
        # print(a)
        temp = popcnt(a)
        a = a % temp
        cnt += 1
    return cnt


ans = [0] * n
cnt = x.count("1")

for i in range(n):
    if x[i] == "1":
        temp = cnt - 1
    else:
        temp = cnt + 1
    t = 1 << (n - i - 1)
    # print(num ^ t, bin(num ^ t)
    if num ^ t:
        ans[i] = calc((num ^ t) % temp)
    else:
        ans[i] = 0
print(*ans, sep="\n")

Submission status: Time Limit Exceeded

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

S = {}

def solve(X, cnt):
    if X in S:
        return cnt + S[X]
    
    if X == 0:
        return cnt
    
    X %= bin(X).count('1')
    
    tmp = solve(X, cnt+1)
    
    S[X] = tmp - cnt - 1
    
    return tmp

for i in range(N):
    print(solve(X ^ 1 << (N - i - 1), 0))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
bi = input()
for i in range(n):
    if bi[i] == "0":
        binew = bi[:i]+"1"+bi[1+i:]
    if bi[i] == "1":
        binew = bi[:i]+"0"+bi[1+i:]
    bi10 = int(binew, 2)
    a = 0
    while bi10 > 0:
        binum = str(bin(bi10))[2:]
        bi10 = bi10 % binum.count("1")
        a += 1
    print(a)

Submission status: Time Limit Exceeded

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


n = int(input())
x = input()
xx = x
nx = int(x, 2)
pnx = popcnt(nx)
popl = [-1]*(2*10**5+10)
for i in range(n):
    a = 1 << (n-1-i)
    x = nx ^ a
    if xx[i] == "1":
        px = pnx-1
    else:
        px = pnx+1
    ans = 0
    while x != 0:
        x = x % px
        if popl[x] == -1:
            px = popcnt(x)
            popl[x] = px
        else:
            px = popl[x]
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

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

    memo = [-1] * 21

    def f(x):
        ret = 0
        while x > 0:
            x = x % bin(x)[2:].count('1')
            ret += 1
        return ret

    for x in range(21):
        memo[x] = f(x)

    ans = []
    for j in range(N):
        t = X[:j] + ('0' if X[j] == '1' else '1') + X[j + 1:]
        t = int(t, 2)

        add_v = 0
        while t > 20 or memo[t] == -1:
            t = t % bin(t)[2:].count('1')
            add_v += 1
        ans.append(memo[t] + add_v)

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


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
# 
# sys.setrecursionlimit(10 ** 7)
# 
# (int(x)-1 for x in input().split())
# rstrip()
#
# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok

Submission status: Time Limit Exceeded

Solution code:
# itne me hi thakk gaye?
n = int(input())
org = list(input())
ans = []
# print(org)
for i in range(n):
    tmp = org[:]
    if org[i] == '1':
        tmp[i] = '0'
    else:
        tmp[i] = '1'
    curr_number = int(''.join(tmp), 2)
    count = 0
    pc = tmp.count('1')
    while(curr_number != 0):
        # print(tmp, curr_number, pc)
        curr_number = curr_number % pc
        tmp = list(bin(curr_number)[2:])
        count += 1
        pc = tmp.count('1')
    ans.append(count)
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

N = int(input())
X = input()
x = []
for i in range(N):
    x.append(X[i])

def f(n):
    cnt = 0
    while n != 0:
        n %= Counter(bin(n))['1']
        cnt += 1
    return cnt

for i in range(N):
    if x[i] == '1':
        tmp = '1'
        x[i] = '0'
    else:
        tmp = '0'
        x[i] = '1'
    n = ''.join(x)
    x[i] = tmp
    print(f(int(n, 2)))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# hello worldと表示する
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
n=I()
lis=list(SI())
orig=0
for i in range(n):
    if lis[i]=="0":
        lis[i]=0
    else:
        lis[i]=1
orcount=sum(lis)
for i in range(n):
    j=n-i-1
    if int(lis[i])==1:
        orig+=2**j
#print(orig)
def count1(y):
    count=0
    i=0
    while 2**i<=y:
        if (y>>i) %2==1:
            count+=1
        i+=1
    return count
dp=[0 for i in range(n)]
dp[0]=1
for i in range(1,n):
    u=count1(i+1)
    z=1
    if (i+1)%u==0:
        dp[i]=z
    else:
        dp[i]=z+dp[(i+1)%u-1]
#print(dp)
for i in range(n):
    if int(lis[i])==0:
        num=orig+2**(n-i-1)
        pr=orcount+1
    else:
        num=orig-2**(n-i-1)
        pr=orcount-1
    #print(num,pr)
    if pr==0:
        print(0)
    elif num%pr==0:
        print(1)
    else:
        print(1+dp[num%pr-1])
        
        
    
    

#print(count1(8))

Submission status: Time Limit Exceeded

Solution code:
n = 2 * 10 ** 5
k = int(input())
x = list(str(input()))

for i in range(k):
    temp = x[:]
    if temp[i] == "0":
        temp[i] = "1"
    else:
        temp[i] = "0"
    num = int("".join(temp),2)
    c = 0
    while num != 0:
        c += 1
        num %= bin(num).count("1")

    print(c)

Submission status: Time Limit Exceeded

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

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

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

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

def nasu(a, k):
  ans = 1
  while a != 0:
    k =popcount(a)
    a %= k
    ans += 1
  return ans

import random
N = int(input())
X = input()

t = X.count("1")
X = int(X, 2)

L = [0] * N
for i in range(N):
  a = X ^ (1 << i)
  if a == 0:
    L[i] == 0
    continue
  if X & (1 << i) != 0:
    k = t - 1
  else:
    k = t + 1
  a %= k
  L[i] = nasu(a, k)

for i in range(N - 1, -1, -1):
  print(L[i])

Submission status: Time Limit Exceeded

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

memo = {0: 0}


def f(x):
    if x in memo:
        return memo[x]
    else:
        pc = bin(x).count('1')
        memo[x] = f(x % pc) + 1
        return memo[x]


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

    x = int(''.join(x), 2)
    print(f(x))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
X = input()
#N = 2 * 100000
#X = "0" * N
def hanten(a,i):
    if a[i] == "0":
        tmp = "1"
    else:
        tmp = "0"
    return(a[:i] + tmp+ a[i+1:])
for i in range(N):
    hantened = int(hanten(X,i),2)
    #print(hantened)
    cnt = 0
    #int(hantened, 2) //
    while (hantened > 0):
        hantened = hantened % bin(hantened).count("1")
        cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

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


def f(n):
    count = 0
    while n != 0:
        a = str(bin(n))
        n %= a.count("1")
        count += 1
    return count


for i in range(N):
    if X[i] == "1":
        X[i] = "0"
        n = int("".join(map(str, X)), 2)
        ans = f(n)
        print(ans)
        X[i] = "1"
    else:
        X[i] = "1"
        n = int("".join(map(str, X)), 2)
        ans = f(n)
        print(ans)
        X[i] = "0"

Submission status: Time Limit Exceeded

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

N = int(input())
X = int(input(),2)
l = [0]+[-1]*(N)

def pc(n):
    ans = 0
    while n>0:
        ans += n&1
        n = n>>1
    return ans

def rec(x):
    global l
    if x<=N and l[x]>=0:
        return l[x]
    else:
        tmp = x%pc(x)
        ans = rec(tmp)+1
        if x<=N:
            l[x] = ans
        return ans

a = [0]*N
for i in range(N):
    a[N-1-i] = rec(X^(1<<i))
for x in a:
    print(x)

Submission status: Time Limit Exceeded

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

xlist = []
for i in range(n):
  xlist.append(x ^ (1 << i))
xlist.reverse()
  
for d in xlist:
  cnt = 0
  while d != 0:
    d %= list(str(bin(d))).count("1")
    cnt += 1
  print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
import random
from collections import deque
from decimal import *
import queue

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()
	X = inputStr()
	X_lin = list(X)

	ans = []
	for i in range(N):
		tmpX = []
		if X[i] == "1":
			tmpX = X[:i] + "0" + X[i+1:]
		else:
			tmpX = X[:i] + "1" + X[i+1:]

		oct = int(tmpX, 2)

		ans_tmp = 0
		while True:
			if oct == 0:
				break
			tmp = bc(oct)
			oct = oct % tmp
			ans_tmp += 1
		ans.append(ans_tmp)

	for i in ans:
		print(i)

def bc(x):
	return bin(x).count("1")

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq, functools, collections
import math, random
from collections import Counter, defaultdict

# available on Google, not available on Codeforces
# import numpy as np
# import scipy


def solve(lst):  # fix inputs here
    console("----- solving ------")

    # console(lst)

    r = int("".join(lst), base=2)
    
    for i,x in enumerate(lst):
        # lst[i] = str(1-int(lst[i]))
        # x = int("".join(lst), base=2)
        
        x = r ^ 1 << (len(lst) - i - 1)
        # console(x)
        cnt = 0
        while x != 0:
            ones = bin(x).count("1")
            x = x%ones
            cnt += 1

        # lst[i] = str(1-int(lst[i]))
        print(cnt)

    # return a string (i.e. not a list or matrix)
    return ""  


def console(*args):  # the judge will not read these print statement
    print('\033[36m', *args, '\033[0m', file=sys.stderr)
    return


# for case_num in range(int(input())):
    # read line as a string
    # strr = input()

    # read line as an integer
k = int(input())

    # read one line and parse each word as a string
lst = list(input())

    # read one line and parse each word as an integer
    # lst = list(map(int,input().split()))

    # read matrix and parse as integers (after reading read nrows)
    # lst = list(map(int,input().split()))
    # nrows = lst[0]  # index containing information, please change
    # grid = []
    # for _ in range(nrows):
    #     grid.append(list(map(int,input().split())))

res = solve(lst)  # please change
    
    # Google - case number required
    # print("Case #{}: {}".format(case_num+1, res))

    # Codeforces - no case number required
    # print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(500000)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

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

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

def inot(X, i, N):
    if X[i] == '0':
        return int(X, base=2)+(1<<N-1-i)
    else:
        return int(X, base=2)-(1<<N-1-i)

@lru_cache(maxsize=1000)
def f(n):
    if n == 0:
        return 0
    else:
        return 1+f(n%bin(n).count('1'))

def main():
    N = ii()
    X = input()
    dic = {}
    for i in range(N):
        Xi = inot(X, i, N)
        print(f(Xi))


if __name__ == '__main__':
    main()