Problem:


Score : 400 points

Problem Statement

Let \mathrm{popcount}(n) be the number of 1s in the binary representation of n.
For example, \mathrm{popcount}(3) = 2, \mathrm{popcount}(7) = 3, and \mathrm{popcount}(0) = 0.

Let f(n) be the number of times the following operation will be done when we repeat it until n becomes 0: "replace n with the remainder when n is divided by \mathrm{popcount}(n)." (It can be proved that, under the constraints of this problem, n always becomes 0 after a finite number of operations.)

For example, when n=7, it becomes 0 after two operations, as follows:

\mathrm{popcount}(7)=3, so we divide 7 by 3 and replace it with the remainder, 1.

\mathrm{popcount}(1)=1, so we divide 1 by 1 and replace it with the remainder, 0.

You are given an integer X with N digits in binary.
For each integer i such that 1 \leq i \leq N, let X_i be what X becomes when the i-th bit from the top is inverted.
Find f(X_1), f(X_2), \ldots, f(X_N).

Constraints

1 \leq N \leq 2 \times 10^5

X is an integer with N digits in binary, possibly with leading zeros.

Input

Input is given from Standard Input in the following format:

N
X

Output

Print N lines. The i-th line should contain the value f(X_i).

Sample Input 1

3
011

Sample Output 1

2
1
1

X_1 = 7, which will change as follows: 7 \rightarrow 1 \rightarrow 0. Thus, f(7) = 2.

X_2 = 1, which will change as follows: 1 \rightarrow 0. Thus, f(1) = 1.

X_3 = 2, which will change as follows: 2 \rightarrow 0. Thus, f(2) = 1.

Sample Input 2

23
00110111001011011001110

Sample Output 2

2
1
2
2
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
3



Sample input:
3
011


Sample output:
2
1
1

Submission status: Wrong Answer

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

def calc(num, cnt, ans):
  if cnt == 0:
    ans += 1
    print(ans)
    return ans
  mod = num % cnt
  if mod == 0:
    ans += 1
    print(ans)
  else:
    ans += 1
    n = format(mod, 'b')
    cnt = n.count('1')
    calc(mod, cnt, ans)

n = int(X, 2)
c = X.count('1')
for i in range(1, N+1):
  num = n
  cnt = c
  if X[i-1] == '0':
    num += 2**(N-i)
    cnt += 1
    calc(num, cnt, 0)
  else:
    num -= 2**(N-i)
    cnt -= 1
    calc(num, cnt, 0)

Submission status: Wrong Answer

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

t = [0]
for n in range(1, N+1):
    b = bin(n)[2:]
    c = b.count("1")
    t.append(1 + t[n%c])

base = X.count("1")
basex = int(X, 2)
for n in range(N):
    if X[n] == "0":
        c = base + 1
        x = basex + 2**(N-n-1)
    else:
        c = base - 1
        x = basex - 2**(N-n-1)
    
    if c == 0:
        print(1)
    else:
        print(1 + t[x%c])

Submission status: Wrong Answer

Solution code:
# def popcount(x):
#     bitx = bin(x)
#     cnt = bitx.count('1')
#     return cnt

n = int(input())
x = list(input())
popcount = x.count('1')
for i in range(n):
    tmp = x.copy()
    tmp2 = popcount
    if tmp[i] == '1':
        tmp[i] = '0'
        tmp2 -= 1
    else:
        tmp[i] = '1'
        tmp2 += 1
    tmp = int(''.join(tmp), 2)
    if tmp2 == 0:
        print(0)
    elif tmp % tmp2 == 0:
        print(1)
    elif tmp % 2 != 0 and tmp2 % 2 == 0:
        print(3)
    else:
        print(2)

Submission status: Wrong Answer

Solution code:
n = int(input())
x = input()
# print (int(x,2))
a = x.count('1')
# print (a)


for i in range(n):
  if x[i] == '0':
    b = '1'
    cnt = a + 1
  else:
    b = '0'
    cnt = a - 1
  d = x[:i] + b + x[i+1:]
  # print (d, int(d,2))
  v = int(d,2)
  out = 0
  # while v != 0:
  if cnt == 0:
    print (0)
    continue
  v %= cnt
  cnt = bin(v).count('1')
  if cnt == 0:
    out = 1
  elif cnt < 3:
    out = 2
  else:
    out = 3
  print (out)

Submission status: Wrong Answer

Solution code:
n = int(input())
x = input()
value = [0, 1]
for i in range(2, 2 * (10 ** 5) + 1):
    ans = 1
    i = i % bin(i).count('1')
    value.append(ans + value[i])

for i in range(n):
    t = x[:i] + ('0' if x[i] == '1' else '1') + x[i + 1:]
    print(1)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = input()
count = X.count("1")
listX = list(X)
total = int(X,2)
check = [0]*(N+1)
for i in range(1,N+1):
    pop = bin(i).count("1")
    if i%pop==0:
        check[i]=1
    else:
        check[i]= check[i%pop]+1
for i in range(N):
    if listX[i] == '0':
        print(check[(total+2**(N-1-i))%(count+1)]+1)
    else :
        if count == 1:
            print("1")
        else:
            print(check[(total-2**(N-1-i))%(count-1)]+1)

Submission status: Wrong Answer

Solution code:
import collections
memo = collections.defaultdict(int)
memo[0] = 0
memo[1] = 1


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


N = int(input())
sX = input()
modX = sX.count('1')
if modX == 0:
    for _ in range(N):
        print(1)
elif modX == 1:
    sX = sX[::-1]
    if sX[0] == '1':
        ans = [2] * (N - 1) + [0]
    else:
        ans = [0] * (N - 1) + [2]
    print('\n'.join(map(str, ans)))
else:
    modp = modX + 1
    modm = modX - 1
    sX = sX[::-1]
    Xmodp = 0
    Xmodm = 0
    for i, b in enumerate(sX):
        if b == '1':
            Xmodp += pow(2, i, modp)
            Xmodp %= modp
            Xmodm += pow(2, i, modm)
            Xmodm %= modm
    s = []
    for i, b in enumerate(sX):
        if b == '1':
            s += [(Xmodm - pow(2, i, modm)) % modm]
        else:
            s += [(Xmodp + pow(2, i, modp)) % modp]
    t = s[::-1]
    ans = []
    for k in t:
        ans += [1 + f(k)]
    print('\n'.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
n = int(input())
x = input()
mod_num1 = [0 for i in range(n+1)]
mod_num2 = [0 for i in range(n+1)]
mod_num3 = [0 for i in range(n+1)]
num2 = x.count('1')
if num2 == 0:
    for i in range(n):
        print(1)
        exit()
elif num2 == 1:
    index = x.index('1')
    for i in range(n):
        if x[i] == '1':
            print(0)
        else:
            if index == n-1:
                print(2)
            else:
                print(1)
    exit()
num1 = num2 - 1
num3 = num2 + 1
for i in range(n):
    if x[i] == '1':
        mod_num1[i] = pow(2, n-i-1 ,num1)
        mod_num2[i] = pow(2, n-i-1, num2)
        mod_num3[i] = pow(2, n-i-1, num3)
def popcount(num):
    res = 0
    while num != 0:
        res += 1
        num = num % "{:b}".format(num).count('1')
    return res
s_1 = sum(mod_num1)
s_2 = sum(mod_num2)
s_3 = sum(mod_num3)
for i in range(n):
    if x[i] == '1':
        print(popcount((s_1 - pow(2, n-i-1, num1)) % num1) + 1)
    else:
        print(popcount((s_3 + pow(2, n-i-1, num3)) % num3) + 1)

Submission status: Wrong Answer

Solution code:
from itertools import repeat

def bitcount(x):
	result = 0
	while x > 0:
		if x % 2 == 1: 
			result += 1

		x //= 2
	return result

ff = {}

def f(x):
	count = 0
	while x != 0:
		count += 1
		#print(x, bitcount(x))
		x = x % bitcount(x)	
	return count

#n = 200000
n = int(input())
s = input()
#s = "".join(list(repeat('1', n)))
bc = s.count('1')

x = 0
pow = 1
for bit in reversed(range(n)):
	if s[bit] == '1':
		x += pow
	pow *= 2


mods1 = []
mod1, mod2 = bc + 1, bc - 1
mods2 = []

#print(mod1, mod2)

pow = 1
mods1.append(pow % mod1)

if mod2 != 0:
	mods2.append(pow % mod2)

for bit in range(1, n):
	if mod1 != 0:
		mods1.append(2 * mods1[bit - 1] % mod1)
	if mod2 != 0:
		mods2.append(2 * mods2[bit - 1] % mod2)

mods1 = list(reversed(mods1))
mods2 = list(reversed(mods2))

#print(mods1)
#print(mods2)

x_mod_1 = 0
x_mod_2 = 0
for bit in reversed(range(n)):
	if s[bit] == '1':		
		x_mod_1 = (x_mod_1 + mods1[bit]) % mod1
		if mod2 != 0:
			x_mod_2 = (x_mod_2 + mods2[bit]) % mod2

#print(x_mod_1, x_mod_2)

result = []

for bit in reversed(range(n)):
	if s[bit] == '0':
		new_mod = (x_mod_1 + mods1[bit]) % mod1
		result.append(1 + f(new_mod))

	else:
		if mod2 == 0:
			result.append(0)
		else:
			new_mod = (x_mod_2 + mods2[bit]) % mod2
			result.append(1 + f(new_mod))

for x in reversed(result):
	print(x)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
st = 0
for i in range(n):
    st += int(s[i])
#print(st)
if st == 1:
    if s[-1] == '1':
        for _ in range(n-1):
            print(2)
        print(0)
    else:
        for i in range(n):
            if s[i] == '1':
                print(0)
            else:
                print(1)
    exit()
m1 = [1]
p1 = [1]
for i in range(n-1):
    m1.append(m1[-1]*2%(st-1))
    p1.append(p1[-1]*2%(st+1))
if st-1 == 1:
    m1[0] = 0
if st+1 == 1:
    p1[0] = 0
m1.reverse()
p1.reverse()
#print(m1)
#print(p1)
ansm = 0
ansp = 0
for i in range(n):
    ansm += m1[i] * int(s[i])
    ansp += p1[i] * int(s[i])
#print(ansm)
#print(ansp)
time = [0 for _ in range(20)]
def nex(time):
    for i in range(20):
        if time[i] == 0:
            time[i] += 1
            return time
        else:
            time[i] = 0
ans = [0 for _ in range(200001)]
time2 = 1
time[0] = 1
while time2 <= 200000:
    #print(time,time2)
    ans[time2] = ans[time2 % sum(time)] + 1
    time = nex(time)
    time2 += 1
#print(ans[:20])
for i in range(n):
    if s[i] == '1':
        use = (ansm-m1[i]) % (st-1)
    else:
        use = (ansp+p1[i]) % (st+1)
    print(1+ans[use])

Submission status: Wrong Answer

Solution code:
import collections
memo = collections.defaultdict(int)
memo[0] = 0
memo[1] = 1


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


N = int(input())
sX = input()
modX = sX.count('1')
if modX == 0:
    for _ in range(N):
        print(0)
    exit()
elif modX == 1:
    sX = sX[::-1]
    if sX[0] == '1':
        ans = [2] * (N - 1) + [0]
    else:
        ans = [0] * (N - 1) + [2]
    print('\n'.join(map(str, ans)))
    exit()
else:
    modp = modX + 1
    modm = modX - 1
    sX = sX[::-1]
    Xmodp = 0
    Xmodm = 0
    for i, b in enumerate(sX):
        if b == '1':
            Xmodp += pow(2, i, modp)
            Xmodp %= modp
            Xmodm += pow(2, i, modm)
            Xmodm %= modm
    s = []
    for i, b in enumerate(sX):
        if b == '1':
            s += [(Xmodm - pow(2, i, modm)) % modm]
        else:
            s += [(Xmodp + pow(2, i, modp)) % modp]
    t = s[::-1]

ans = []
for k in t:
    ans += [1 + f(k)]
print('\n'.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
import math
n = int(input())

ans = [0]*n
for i in range(n):
	for x in range(1,math.floor(math.sqrt(n))):
		for y in range(1,math.floor(math.sqrt(n))):
			for z in range(1,math.floor(math.sqrt(n))):
				if pow(x,2) + pow(y,2) + pow(z,2) + x*y + y*z + z*x == i:
					ans[i] += 1
for i in range(n):
	print(ans[i])

Submission status: Wrong Answer

Solution code:
n=int(input())
x=int(input(),2)
A=[0]*(n+1)
A[1]=1
def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x = x + (x >> 8) 
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f
for i in range(2,n+1):
  k=popcount(i)
  A[i]=A[i%k]+1
for i in range(n):
  y= x^(1<<(n-1-i))
  p=popcount(y)
  if p==0:
    print(0)
  else:  
    print(A[y%(popcount(y))]+1)

Submission status: Wrong Answer

Solution code:
n = int(input())
x = list(input())
zuru = [0, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 2, 3, 1, 2, 1, 2, 1, 1, 2, 3, 1, 2, 2, 3, 2, 2, 2, 2, 1, 2, 1, 2, 1, 2, 2, 3, 1, 2, 1, 3, 2, 2, 2, 2, 1, 2, 2, 3, 2, 2, 2, 1, 2, 2, 2, 2, 1, 2, 2, 3, 1, 2, 1, 2, 1, 1, 2, 3, 1, 2, 2, 3, 2, 2, 2, 2, 1, 1, 2, 3, 1, 2, 2, 2, 2, 2, 2, 2, 1, 3, 2, 3, 1, 2, 2, 3, 2, 2, 2, 3, 2, 2, 2, 2, 1, 2, 1, 3, 2, 2, 2, 1, 1, 2, 3, 3, 1, 2, 2, 3, 2, 3, 1, 2, 1]

for i in range(len(x)):
  y = x.copy()
  if x[i] == "0":
    y[i] = "1"
  else:
    y[i] = "0"
  n = int("".join(y), 2)
  count = 0
  while n != 0:
    one_num = bin(n)
    n = n % one_num.count("1")
    count += 1
    if 0 <= n <=128:
      count += zuru[n-1]
      break
    print(count)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
X = input().strip()

def solve(N,X):
    if not '1' in X:
        for i in range(N):
            print(0)
        exit()

    def popcount(n):
        t = 0
        while n > 0:
            k = bin(n).count('1')
            n %= k
            t += 1
        return t

    X1 = X.count('1')

    Rp1 = []
    Rm1 = []
    Bp1 = []
    Bm1 = []

    for i, x in enumerate(list(X[::-1])):
        tp1 = pow(2,i,X1+1)
        if X1-1 > 0:
            tm1 = pow(2,i,X1-1)
        else:
            tm1 = 0
        Bp1.append(tp1)
        Bm1.append(tm1)
        if x == '1':
            Rp1.append(tp1)
            Rm1.append(tm1)
        else:
            Rp1.append(0)
            Rm1.append(0)

    basep1 = sum(Rp1) % (X1+1)
    if X1-1 > 0:
        basem1 = sum(Rm1) % (X1-1)
    else:
        basem1 = 0
    Rp1 = Rp1[::-1]
    Rm1 = Rm1[::-1]
    Bp1 = Bp1[::-1]
    Bm1 = Bm1[::-1]

    #print("base",basep1)
    #print("base",basem1)
    for bp1,bm1,x in zip(Bp1,Bm1,X):
        if x == '1':
            t = basem1 - bm1
            MOD = X1 - 1
            if MOD <= 0:
                print(0)
                continue
        else:
            t = basep1 + bp1
            MOD = X1 + 1
        #print("x",x,"t",t)
        #print(t % MOD,MOD)
        print(popcount(t % MOD) + 1)

solve(N,X)

Submission status: Wrong Answer

Solution code:
def popcount(n,ans):
	if n==0: return ans
	if dp[n] != -1: return dp[n]
	ne = n%str(bin(n)).count("1")
	ans = popcount(ne,ans+1)
	dp[ne] = ans
	return ans

global dp
n = int(input())
s = input()
#print(int(s,2))
x = int(s,2)
d = str(bin(x)).count("1")
dp = []
for i in range(n): dp.append(-1)

for i in range(n):
	if s[i] == "1":
		temp_d = d-1
		temp = int(s[:i] + "0" + s[i+1:],2)
	else:
		temp_d = d+1
		temp = int(s[:i] + "1" + s[i+1:],2)
	if temp_d == 0:
		print(0)
	else:
		next_temp = temp%temp_d
		print(popcount(next_temp,1))

Submission status: Wrong Answer

Solution code:
import sys
import math
import itertools
import random
def popcount(n,cnt):
    tmp=str(bin(n))
    num=0
    for i in range(len(tmp)):
        if(tmp[i]=='1'):
            num+=1
    if(num==0):
        return cnt+1
    elif(n%num==0):
        return cnt+1
    else:
        return popcount(n%num,cnt+1) 
n=int(input())
x=input()
for i in range(n):
    tmp=x
    if(tmp[i]=='0'):
        tmp=tmp[:i]+'1'+tmp[i+1:]
    else:
        tmp=tmp[:i]+'0'+tmp[i+1:]
    ans=popcount(int(tmp,2),0)
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = list(map(int, list(input())))
X.reverse()
def int2bit(n):
	ret = [0 for i in range(18)]
	cnt = 0
	i = 0
	while n > 0:
		ret[i] = n % 2
		cnt += n % 2
		n = n // 2
		i += 1
	return (ret, cnt)

def func(bit, popcount):
	ret = 0
	base = 1
	for b in bit:
		ret = (ret + base*b) % popcount
		base = (base * 2) % popcount
	return ret

def func2(n):
	(bit, popcount) = int2bit(n)
	return func(bit, popcount)

F = [0 for _ in range(N+1)]

for n in range(1, N+1):
	a = func2(n)
	F[n] = 1 + F[a]
P = sum(X)

f_1 = func(X, P+1)
f_0 = func(X, max(1, P-1))

base_1 = [1]
base_0 = [1]
for i in range(N-1):
	base_1.append((base_1[i] * 2) % (P+1))
	base_0.append((base_0[i] * 2) % max(1, P-1))
print(base_0)
for i in range(N):
	idx = N - 1 - i
	if X[idx] == 0:
		print(1 + F[(f_1 + base_1[idx]) % (P+1)])
	if X[idx] == 1:
		if P == 1:
			print(0)
		else:
			print(1 + F[(f_0 - base_0[idx]) % (P-1)])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

'''
Author: andyli
Time: 2020-07-11 19:58:49
'''

import os
from io import BytesIO, IOBase
import sys


def main():
    n = int(input())
    x = input()
    popcounts = x.count('1')
    if popcounts == 1:
        for i in range(n):
            if x[i] == 1:
                print(0)
                continue
            if (i == n-1 and x[-1] == '0') or (i != n-1 and x[-1] == '1'):
                print(2)
            else:
                print(1)
        return
    if popcounts == 0:
        for i in range(n):
            print(1)
        
        return
    modmi = [0 for i in range(n+2)]
    modpl = [0 for i in range(n+2)]
    s = 1
    for i in range(0,n+2):
        s %= (popcounts-1)
        modmi[i] = s
        s <<= 1
    s = 1
    for i in range(0,n+2):
        s %= (popcounts+1)
        modpl[i] = s
        s <<= 1
    demodmi = int(x,base=2)%(popcounts-1)
    demodpl = int(x,base=2)%(popcounts+1)
    def count(n):
        ans = 0
        while n > 0:
            n %= bin(n).count('1')
            ans += 1
        return ans
    # print('\t',demodmi,demodpl)
    for i in range(n):
        if x[i] == '0':
            demodmi = (demodmi + modmi[(n-i-1)]) % (popcounts-1)
            demodpl = (demodpl + modpl[(n-i-1)]) % (popcounts+1)
            pass
        else:
            demodmi = (demodmi - modmi[(n-i-1)]) % (popcounts-1)
            demodpl = (demodpl - modpl[(n-i-1)]) % (popcounts+1)
            pass
        mod = demodmi if x[i] == '1' else demodpl
        # print('\t', mod)
        print(1 + count(mod))
        if x[i] == '1':
            demodmi = (demodmi + modmi[(n-i-1)]) % (popcounts-1)
            demodpl = (demodpl + modpl[(n-i-1)]) % (popcounts+1)
            pass
        else:
            demodmi = (demodmi - modmi[(n-i-1)]) % (popcounts-1)
            demodpl = (demodpl - modpl[(n-i-1)]) % (popcounts+1)
            pass

    return


# region fastio
BUFSIZE = 1048576


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda: self.buffer.read().decode('ascii')
        self.readline = lambda: self.buffer.readline().decode('ascii')


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
def input(): return sys.stdin.readline().rstrip('\r\n')

# endregion


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def cin():
    return input().split()
def qpow(a,b,p):
    if p == 1 or p == 0:
        return 0
    a = (a%p+p)%p
    ans = 1
    while b!=0:
        if (b&1) != 0:
            ans = (ans * a) % p
        b >>= 1
        a = a * a  % p
    return ans

def f(x):
    ans = 0
    if x == 0:
        return ans
    for i in range(31):
        if ((x>>i)&1) == 1:
            ans += 1
    return f(x%ans) + 1

n = int(input())
x = list(input())
x = x[::-1]
cnt = 0;l = len(x)
r1 = 0;r2 = 0
for i in x:
    if i == '1':
        cnt += 1
i = 0
while i < l:
    if x[i] == '1':
        r1 += qpow(2,i,cnt+1)
        r2 += qpow(2,i,cnt-1)
    i += 1
i = 0
a = []
while i < l:
    if x[i] == '0':
        t = f((r1+qpow(2,i,cnt+1))%(cnt+1))+ 1
    else:
        if cnt-1 !=  0:
            t = f((r2-qpow(2,i,cnt-1)+(cnt-1))%(cnt-1)) + 1
        else:
            t = 1
    i += 1
    a.append(t)
a = a[::-1]
for i in a:
    print(i)

Submission status: Wrong Answer

Solution code:
#create date: 2020-07-11 21:18

import sys
stdin = sys.stdin

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def popcount(m):
    res = 0
    while m:
        if m & 1:
            res += 1
        m //= 2
    return res
def f(m):
    cnt = 0
    while m:
        #print("test", m)
        m = m % popcount(m)
        cnt += 1
    return cnt

def main():
    n = ni()
    x = ns()
    pop0 = x.count("1") + 1
    pop1 = x.count("1") - 1
    y0 = 0; y1 = 0
    for i, xi in enumerate(x):
        r = n - i - 1
        if xi == "1":
            y0 += pow(2, r, pop0)
            y0 %= pop0
            if pop1 != 0:
                y1 += pow(2, r, pop1)
                y1 %= pop1

    for i, xi in enumerate(x):
        r = n - i - 1
        if xi == "0":
            m = (y0 + pow(2, r, pop0)) % pop0
            print(f(m) + 1)
        else:
            if pop1 == 0:
                print(1)
                continue
            m = (y1 - pow(2, r, pop1)) % pop1
            print(f(m) + 1)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:


def main():
    n_ansl = [0]*(2*(10**5))
    for i in range(1,2*(10**5)):
    # for i in range(1,20):
        cnt = 0
        one_cnt = bin(i).count("1")
        rem = i
        while rem != 0:
            one_cnt = bin(rem).count("1")
            rem = rem%one_cnt   
            cnt += 1
        n_ansl[i] = cnt

    n = int(input())
    x = input()
    one_cnt = x.count('1')
    
    curr_2b = 1
    curr_sum = 0
    curr_sum_p1 = 0
    curr_sum_m1 = 0
    for i in range(n-1, -1, -1):
        if x[i] == '1':
            curr_sum += curr_2b
            curr_sum_p1 += curr_2b
            curr_sum_m1 += curr_2b
            curr_sum%=one_cnt
            curr_sum_p1%=(one_cnt+1)
            if one_cnt > 1:
                curr_sum_m1%=(one_cnt-1)
        curr_2b*=2

    curr_2b = 1
    ansl = [0]*(n)
    for i in range(n-1, -1, -1):
        if x[i] == '1':
            diff = (-1)*curr_2b
            if one_cnt > 1:
                ans = (curr_sum_m1 + diff)%(one_cnt-1)
                ansl[i] = n_ansl[ans]+1
            else:
                ansl[i] = 0
        else:
            diff = curr_2b
            ans = (curr_sum_p1 + diff)%(one_cnt+1)
            ansl[i] = (n_ansl[ans]+1)
        curr_2b *= 2


    print(ansl)
    for a in ansl:
        print(a)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
x=input()
def popcount(n):
    num=str(bin(n))
    return num.count('1')
xx=x.count('1')
xx2=int(x,2)
print(xx,xx2)
for i in range(n):
    if x[i]=='0':
        xxx=xx+1
        xxx2=xx2+2**(n-1-i)
    else:
        xxx=xx-1
        xxx2=xx2-2**(n-1-i)
    count=0

    while xxx2!=0:
        xxx2%=xxx
        xxx=popcount(xxx2)
        count+=1
    print(count)

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7


def main():
    N = int(input())
    S = input()
    d = pow(2, N-1, MOD)
    rd = pow(2, MOD-2, MOD)
    bits = 0
    for s in S:
        if s == "1":
            bits += 1
    S = int(S, 2)
    answer = []
    for i in range(N):
        x = S ^ d
        cur_bits = 0
        if S < x:
            cur_bits = bits + 1
        else:
            cur_bits = bits - 1
        ans = 0
        while x > 0:
            x = x % cur_bits
            ans += 1
            cur_bits = 0
            T = "{:0b}".format(x)
            for t in T:
                if t == "1":
                    cur_bits += 1
        answer.append(ans)
        d *= rd
        d %= MOD

    print(*answer, sep="\n")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def main():
    n = int(input())
    x = input()
    count = 0
    sub = 1
    last = [[0, 0]]*n
    for i in range(n):
        if x[i] == "1":
            count += 1
            
    if count == 0:
        for i in range(n):
            print(1)
        sys.exit()
    if count == 1:
        if x[-1] == "1":
            for i in range(n-1):
                print(2)
            print(0)
            sys.exit()
        else:
            for i in range(n-1):
                if x[i] == "1":
                    print(0)
                else:
                    print(1)
            print(2)
            sys.exit()
    
    sub1, sub2 = 1, 1
    num1, num2 = 0, 0
    for i in range(n):
        last[i] = [sub1, sub2]
        if x[n-i-1] == "1":
            num1 += sub1
            num2 += sub2
            num1 %= count-1
            num2 %= count+1
        sub1 *= 2
        sub2 *= 2
        sub1 %= count-1
        sub2 %= count+1
            
    
    
    key = [0]*(2**18+1)
    for i in range(1, 2**18):
        c = 0
        for j in range(18):
            if (i>>j)&1:
                c += 1
        judge = i%c
        key[i] = key[judge] + 1
    
    for i in range(n):
        if x[i] == "1":
            judge = (num1+count-1-last[n-1-i][0])%(count-1)
            print(1+key[judge])
        else:
            judge = (num2+last[n-1-i][1])%(count+1)
            print(1+key[judge])

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def main():
    n = int(input())
    x = input()
    count = 0
    sub = 1
    last = [[0, 0]]*n
    for i in range(n):
        if x[i] == "1":
            count += 1
            
    if count == 0:
        for i in range(n):
            print(1)
        sys.exit()
    if count == 1:
        if x[-1] == "1":
            for i in range(n-1):
                print(2)
            print(0)
            sys.exit()
        else:
            for i in range(n-1):
                if x[i] == "1":
                    print(0)
                else:
                    print(1)
            print(2)
            sys.exit()
    
    sub1, sub2 = 1, 1
    num1, num2 = 0, 0
    for i in range(n):
        last[i] = [sub1, sub2]
        if x[n-i-1] == "1":
            num1 += sub1
            num2 += sub2
            num1 %= count-1
            num2 %= count+1
        sub1 *= 2
        sub2 *= 2
        sub1 %= count-1
        sub2 %= count+1
            
    
    
    key = [0]*(2**18+1)
    for i in range(1, 2**18):
        c = 0
        for j in range(18):
            if (i>>j)&1:
                c += 1
        judge = i%c
        key[i] = key[judge] + 1
    
    for i in range(n):
        if x[i] == "1":
            judge = (num1-last[n-1-i][0])%(count-1)
            print(1+key[judge])
        else:
            judge = (num2+last[n-1-i][1])%(count+1)
            print(1+key[judge])

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from functools import lru_cache

import sys

sys.setrecursionlimit(4100000)

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 calc2(a):
    if a == 0:
        return 0
    return calc2(a % popcnt(a)) + 1


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

kotae = [0] * (cnt + 2)
for i in range(cnt + 1):
    kotae[i] = calc2(i)


for i in range(n):
    if x[i] == "1":
        temp = cnt - 1
    else:
        temp = cnt + 1
    t = 1 << (n - i - 1)

    if num ^ t:
        ans[i] = calc2(temp)
    else:
        ans[i] = 0
print(*ans, sep="\n")

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

'''
Author: andyli
Time: 2020-07-11 19:58:49
'''

import os
from io import BytesIO, IOBase
import sys


def main():
    n = int(input())
    x = input()
    popcounts = x.count('1')
    if popcounts == 1:
        for i in range(n):
            if (i == n-1 and x[-1] == '0') or (i != n-1 and x[-1] == '1'):
                print(2)
            else:
                print(1)
        return
    if popcounts == 0:
        for i in range(n):
            print(1)
        
        return
    modmi = [0 for i in range(n+2)]
    modpl = [0 for i in range(n+2)]
    s = 1
    for i in range(0,n+2):
        s %= (popcounts-1)
        modmi[i] = s
        s <<= 1
    s = 1
    for i in range(0,n+2):
        s %= (popcounts+1)
        modpl[i] = s
        s <<= 1
    demodmi = int(x,base=2)%(popcounts-1)
    demodpl = int(x,base=2)%(popcounts+1)
    def count(n):
        ans = 0
        while n > 0:
            n %= bin(n).count('1')
            ans += 1
        return ans
    # print('\t',demodmi,demodpl)
    for i in range(n):
        if x[i] == '0':
            demodmi = (demodmi + modmi[(n-i-1)]) % (popcounts-1)
            demodpl = (demodpl + modpl[(n-i-1)]) % (popcounts+1)
            pass
        else:
            demodmi = (demodmi - modmi[(n-i-1)]) % (popcounts-1)
            demodpl = (demodpl - modpl[(n-i-1)]) % (popcounts+1)
            pass
        mod = demodmi if x[i] == '1' else demodpl
        # print('\t', mod)
        print(1 + count(mod))
        if x[i] == '1':
            demodmi = (demodmi + modmi[(n-i-1)]) % (popcounts-1)
            demodpl = (demodpl + modpl[(n-i-1)]) % (popcounts+1)
            pass
        else:
            demodmi = (demodmi - modmi[(n-i-1)]) % (popcounts-1)
            demodpl = (demodpl - modpl[(n-i-1)]) % (popcounts+1)
            pass

    return


# region fastio
BUFSIZE = 1048576


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda: self.buffer.read().decode('ascii')
        self.readline = lambda: self.buffer.readline().decode('ascii')


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
def input(): return sys.stdin.readline().rstrip('\r\n')

# endregion


if __name__ == '__main__':
    main()