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:
## coding: UTF-8
#N = 23
#S = '00110111001011011001110'
N = int(input())
S = input()
P = int(S, 2)
#print(P)



def popcount(x):

    # 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

C = popcount(P)
#print(C)
ret = []

for i in range(N):
    new = []
    for j in range(N):
        if(j != i):
            new.append(S[j])
        else:
            if(S[j] == '0'):
                new.append('1')
                count = C + 1
            else:
                new.append('0')
                count = C - 1
    ten = int(''.join(new), 2)
    #print(i+1, ''.join(new), ten, count)
    now = ten
    res = 0
    while now > 0:
        now = now % count
        count = popcount(now)
        res += 1 
        #print(res, now, count)
    #print(res)
    ret.append(res)


for i in range(N):
    print(ret[i])

Submission status: Wrong Answer

Solution code:
n = int(input())
x=input()
y=0
for i in range(n):
   y = y + (2 ** i) * int(x[-i-1])

FIX = 18
def main(n):
    num = n
    count = 0
    for i in range(FIX+1):
        if num // (2 **(FIX-i)) > 0:
            num = num % (2 **(FIX-i))
            count = count + 1
    return count

for i in range(n):
    if x[i] == "0":
        z = y + (2 ** (n - 1 - i))
    else:
        z = y - (2 ** (n - 1 - i))
    count = 0
    while z != 0:
        z = z % main(z)
        count += 1
    print(count)

Submission status: Wrong Answer

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

def okikae(n):
    kaisu = 0
    if n == 0:
        return 0
    while 1:
        P = popcnt1(n)
        n %= P
        kaisu += 1
        if n == 0:
            return kaisu

OKI = [okikae(i) for i in range(200001)]
X = int(input())
Norig = input()
N = int(Norig,2)
Npop = Norig.count("1")
F = Npop + 1
H = Npop - 1
if H == 0:
    H = -1
FueAmari = N%(Npop + 1)
if Npop != 1:
    HeruAmari = N%(Npop - 1)
else:
    HeruAmari = -1
Fues = []
Herus = []
fue = 1
heru = 1
for i in range(2*(10**5+1)):#2^0の桁から
    fue %= F
    heru %= H
    Fues.append(fue)
    Herus.append(heru)
    fue *= 2
    heru *= 2
RNorig = reversed(Norig)
Results = []
Zougen = []#増えたらTrue
Kaisu = [0] * X
#上の桁から見ていく。ゼロなら減ってイチなら増える
for n,bit in enumerate(Norig):#2**(N-1-n)の桁
    if bit == "0":#増える
        Zougen.append(True)
        print(1+OKI[(FueAmari + Fues[X-1-n] )% F])
    else:
        if H == -1:
            print(0)
            continue
        Zougen.append(False)
        print(1+OKI[(HeruAmari - Herus[X-1-n]) % F])

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def all_bit_count(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
  
n = int(readline())
d = [0]*(n+1)
d[1] = 1
for i in range(2,n+1):
  q = all_bit_count(i)
  p = i%q
  d[i] = d[p]+1
  
x = input()
c = x.count('1')

a1 = 0
a0 = 0
C = max(1,c-1)
for i,xi in enumerate(x[::-1]):
  if xi == '1':
    a1 += pow(2,i,C)
    a1 %= C
    a0 += pow(2,i,c+1)
    a0 %= (c+1)
    
for i,xi in enumerate(x):
  if xi == '1':
    cc = (a1 - pow(2,n-1-i,C))%C
  else:
    cc = (a0 + pow(2,n-1-i,c+1))%(c+1)
  print(d[cc]+1)

Submission status: Wrong Answer

Solution code:
def main():

    n = int(input())
    x = list(str(input()))

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

    if p == 0:
        ans = [1]*n
        for i in range(n):
            print(ans[i])
        exit()

    if p == 1:
        ans = [0]*n
        for i in range(n):
            if x[i] == '1':
                ans[i] = 0
            else:
                if x[-1] != 1:
                    ans[i] = 1
                else:
                    ans[i] = 2
        for i in range(n):
            print(ans[i])
        exit()


    def power(a, n, mod):
        bi=str(format(n,"b")) #2進数
        res=1
        for i in range(len(bi)):
            res=(res*res) %mod
            if bi[i]=="1":
                res=(res*a) %mod
        return res

    X1 = 0
    X2 = 0
    import copy
    s = copy.copy(x)
    s.reverse()
    #print(s)
    for i in range(n):
        if s[i] == '1':
            X1 += power(2, i, p+1)
            X2 += power(2, i, p-1)

    #print(p)
    #print(X1)
    #print(X2)
    ans = [0]*n
    for i in range(n):
        if x[i] == '0':
            temp = X1
            temp += power(2, n-1-i, p+1)
            temp %= (p+1)
            if temp == 0:
                ans[i] = 1
                continue
            cnt = 0
            d = p+1
            while temp:
                cnt += 1
                temp %= d
                b = format(temp, 'b')
                d = 0
                for j in range(len(b)):
                    if b[j] == '1':
                        d += 1
        else:
            temp = X2
            temp -= power(2, n-1-i, p-1)
            temp %= (p-1)
            if temp == 0:
                ans[i] = 1
                continue
            cnt = 0
            d = p-1
            while temp:
                cnt += 1
                temp %= d
                b = format(temp, 'b')
                d = 0
                for j in range(len(b)):
                    if b[j] == '1':
                        d += 1
        ans[i] = cnt
    #print(*ans)
    for i in range(n):
        print(ans[i])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def g(x, mod):
	ximod = 1 % mod
	r = 0
	for i,xi in enumerate(x[::-1]):
		
		if i: ximod *= 2
		ximod %= mod
		if xi == 1:
			r += ximod
			r %= mod
	return r

def rep(r):
	return map(int,bin(r)[2:])
def f(x):
	if all([xi == 0 for xi in x]):
		return 0
	cc=  collections.Counter(x)
	compute = g(x,cc[1])
	if compute == 0:
		return 1
	return 1 + f(rep(compute))
	return 1 + f(compute)

for i in range(n - 1, -1, -1):
	y = x[:i] + [1- x[i]] + x[i+1:]
	print f(y)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = input()
f = {}
for i in range(N):
    if X[i]=='1':
        x = int(X[0:i]+'0'+X[i+1:],2)
    else:
        x = int(X[0:i]+'1'+X[i+1:],2)
    count = 0
    while x>0:
        x = x%sum(list(map(int, bin(x)[2:])))
        count += 1
        if x==0:
            print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
x = int(input(),2)
b = int(2**(n-1))
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
for i in range(n):
    temp = x^b
    ans = 0
    # print(temp,x,b)
    while temp:
        # print(i,temp,ans,popcount(temp))
        # print(temp)
        # s = str(bin(temp))
        # print(temp,popcount(temp))
        if popcount(temp) == 0:
            
            break
        temp = temp % popcount(temp)
        ans += 1
        # print(temp,s)
        # break
    b=b>>1
    print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
x = input()
remain = [None]*(n)
ans = [1]*(n)
one = x.count("1")+1
if one == 2:
    for i in range(n):
        if x[i] == "1":
            ans[i] = 0
            remain[i] = 0

num = 0
for i in range(n-1, -1, -1):
    if x[i] == "1":
        num += pow(2, n-1-i, one)

for i in range(n):
    if x[i] == "0":
        num_temp = num+pow(2, n-1-i, one)
        num_temp %= one
        remain[i] = num_temp


one -= 2
if one == 0:
    pass

else:
    for i in range(n):
        if x[i] == "1":
            num_temp = num-pow(2, n-1-i, one)
            num_temp %= one
            remain[i] = num_temp

for i in range(n):
    if remain[i] != 0:
        rem = remain[i]
        while rem != 0:
            ans[i] += 1
            popcount = format(rem, "b").count("1")
            rem %= popcount

for i in ans:
    print(i)

Submission status: Wrong Answer

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

count_j = X.count(1)

def calc_table(m):
	if m == 1:
		return [0] * N
	elif m == 0:
		return None
	table = []
	x = 1
	for i in range(N):
		table.append(x)
		x = (x * 2) % m
	table.reverse()
	return table

count_m = count_j - 1
count_p = count_j + 1

mod_m = calc_table(count_m)
mod_j = calc_table(count_j)
mod_p = calc_table(count_p)

original_j = 0
original_m = 0
original_p = 0
if count_m > 0:
	for i, b in enumerate(X):
		if b == 1:
			original_j = (original_j + mod_j[i]) % count_j
			original_m = (original_m + mod_m[i]) % count_m
			original_p = (original_p + mod_p[i]) % count_p
else:
	for i, b in enumerate(X):
		if b == 1:
			original_j = (original_j + mod_j[i]) % count_j
			original_p = (original_p + mod_p[i]) % count_p
#print(mod_p)
#print(original_m, original_j, original_p)

f_cache = [None] * N
def calc_f(x):
	if x == 0:
		return 0
	f = f_cache[x]
	if f != None:
		return f
	count = 0
	i = x
	while i > 0:
		if i % 2 == 1:
			count += 1
		i //= 2
	f = calc_f(x % count) + 1
	f_cache[x] = f
	return f

for i, b in enumerate(X):
	if b == 0:
		x = (original_p + mod_p[i]) % count_p
		print(calc_f(x) + 1)
	else:
		if count_m > 0:
			x = (original_m - mod_m[i]) % count_m
		else:
			print(0)

Submission status: Wrong Answer

Solution code:
import math

mod = 1000000007
dp = [0, 1]
num = [0, 1]
for i in range(2, 200000):
    if i % 2 == 0:
        num.append(num[i//2])
    else:
        num.append(num[i//2]+1)
    dp.append(dp[i % num[i]]+1)
N = int(input())
x = input()
ones = 0
for c in x:
    if c == '1':
        ones += 1
powlow = [1]
powhigh = [1]
modlow = ones - 1
modhigh = ones + 1
for i in range(200000):
    if modlow != 0:
        powlow.append((powlow[i]*2) % modlow)
    powhigh.append((powhigh[i]*2) % modhigh)
reslow = 0
reshigh = 0
for i in range(N):
    if x[i] == '1':
        if modlow != 0:
            reslow = (reslow + powlow[N - i - 1]) % modlow
        reshigh = (reshigh + powhigh[N - i - 1]) % modhigh
for i in range(N):
    if x[i] == '1':
        if modlow != 0:
            temp = (modlow + reslow - powlow[N - i - 1]) % modlow
            print(dp[temp] + 1)
        else:
            print(1)
    if x[i] == '0':
        temp = (reshigh + powhigh[N - i - 1]) % modhigh
        print(dp[temp] + 1)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    X = input()
    MOD = 0
    for elem in X:
        if elem == '1':
            MOD += 1
    if MOD == 0:
        print("1" + "\n1" * (N-1))
        return 0
    if MOD == 1 and X[-1] == '1':
        print("2\n" * (N-1) + "0")
        return 0
    if MOD == 1 and X[-1] == '0':
        ans = ''
        for i in range(N):
            if X[i] == '1':
                ans += '0'
            else:
                ans += '1'
            if i != N-1:
                ans += '\n'
        print(ans)
        return 0
    MODP1 = MOD + 1
    MODM1 = MOD - 1
    POWEROFTWOP1 = [0] * N
    POWEROFTWOM1 = [0] * N
    POWEROFTWOP1[0] = 1
    POWEROFTWOM1[0] = 1
    for i in range(1,N):
        POWEROFTWOP1.append((POWEROFTWOP1[i-1] * 2) % MODP1)
        POWEROFTWOM1.append((POWEROFTWOM1[i-1] * 2) % MODM1)
    xMODP1 = 0
    xMODM1 = 0
    for i in range(N):
        if X[i] == '1':
            xMODP1 += POWEROFTWOP1[N - i - 1]
            xMODM1 += POWEROFTWOM1[N - i - 1]
    xMODP1 %= MODP1
    xMODM1 %= MODM1
    ans = ""
    for i in range(N):
        if X[i] == '0':
            anscur = xMODP1
            anscur += POWEROFTWOP1[N - i - 1]
            anscur %= MODP1
        if X[i] == '1':
            anscur = xMODM1
            anscur -= POWEROFTWOM1[N - i - 1]
            anscur %= MODM1
        cnt = 1
        while anscur != 0:
            ans2 = bin(anscur)[2:]
            oneCount = 0
            for elem in ans2:
                if elem == '1':
                    oneCount += 1
            anscur %= oneCount
            cnt += 1
        ans += str(cnt)
        if i != N-1:
            ans += '\n'
    print(ans)
                    
main()