Buggy python submission (verdict: Time Limit Exceeded):


def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    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
    
    N=I()
    Xst=input()
    
    dp=[0]*(N+1)
    for i in range(1,N+1):
        X=i
        X=X%popcount(X)
        dp[i]=dp[X]+1 
        
    a=Xst.count("1")
    X=int(Xst,2)
    
    
    
    for i in range(N):
        if Xst[i]=="0":
            xa=a+1
            X2=X+(1<<(N-i-1))
        else:
            xa=a-1
            X2=X-(1<<(N-i-1))
        cnt=0
        #print(X2,xa)
        if X2!=0:
            X2=X2%xa
            cnt=dp[X2]+1
        print(cnt)
    
    
        

main()


Fixed submission:


def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    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
    
    N=I()
    Xst=input()
    
    #メモ化
    dp=[0]*(N+5)
    for i in range(1,N+5):
        X=i
        X=X%popcount(X)
        dp[i]=dp[X]+1 
       
    a=Xst.count("1")
    #a+1,a-1でしか割らない
    if a==0:
        for i in range(N):
            print(1)
        exit()
    elif a==1:
        for i in range(N):
            if Xst[i]=="1":
                print(0)
            else:
                if i!=(N-1):
                    print(1)
                else:
                    if Xst[-1]=="0":
                        print(2)
        exit()
    
    remp=[0]*(N+1)
    remm=[0]*(N+1)
    
    remp[0]=1%(a+1)
    remm[0]=1%(a-1)
    
    for i in range(1,N+1):#
        remp[i]=(2*remp[i-1])%(a+1)
        remm[i]=(2*remm[i-1])%(a-1)
    
    Xremp=0
    Xremm=0
    for i in range(N):
        if Xst[i]=="1":
            Xremp+=remp[N-i-1]
            Xremm+=remm[N-i-1]
    Xremp%=(a+1)
    Xremm%=(a-1)
    
    #print(Xremp,Xremm)
    
    for i in range(N):
        if Xst[i]=="0":
            Xrem2=(Xremp+remp[N-i-1])%(a+1)
        else:
            Xrem2=(Xremm-remm[N-i-1])%(a-1)
        
        print(dp[Xrem2]+1)
    
    
    
        

main()

Buggy python submission (verdict: Time Limit Exceeded):


def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    
    def pcnt(X):
        st=str(bin(X))
        return st.count("1")
    
    def calc(X):
        if X==0:
            return 0
        cnt=0
        while X!=0:
            #print(X,pcnt(X))
            X=X%pcnt(X)
            cnt+=1
        return cnt
    
    N=I()
    Xst=input()
    a=Xst.count("1")
    X=int(Xst,2)
    
    for i in range(N):
        if Xst[i]=="0":
            xa=a+1
            X2=X+(1<<(N-i-1))
        else:
            xa=a-1
            X2=X-(1<<(N-i-1))
        cnt=0
        #print(X2,xa)
        if X2!=0:
            X2=X2%xa
            cnt=1+calc(X2)
        print(cnt)
    
    
        

main()


Fixed submission:


def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    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
    
    N=I()
    Xst=input()
    
    #メモ化
    dp=[0]*(N+5)
    for i in range(1,N+5):
        X=i
        X=X%popcount(X)
        dp[i]=dp[X]+1 
       
    a=Xst.count("1")
    #a+1,a-1でしか割らない
    if a==0:
        for i in range(N):
            print(1)
        exit()
    elif a==1:
        for i in range(N):
            if Xst[i]=="1":
                print(0)
            else:
                if i!=(N-1):
                    print(1)
                else:
                    if Xst[-1]=="0":
                        print(2)
        exit()
    
    remp=[0]*(N+1)
    remm=[0]*(N+1)
    
    remp[0]=1%(a+1)
    remm[0]=1%(a-1)
    
    for i in range(1,N+1):#
        remp[i]=(2*remp[i-1])%(a+1)
        remm[i]=(2*remm[i-1])%(a-1)
    
    Xremp=0
    Xremm=0
    for i in range(N):
        if Xst[i]=="1":
            Xremp+=remp[N-i-1]
            Xremm+=remm[N-i-1]
    Xremp%=(a+1)
    Xremm%=(a-1)
    
    #print(Xremp,Xremm)
    
    for i in range(N):
        if Xst[i]=="0":
            Xrem2=(Xremp+remp[N-i-1])%(a+1)
        else:
            Xrem2=(Xremm-remm[N-i-1])%(a-1)
        
        print(dp[Xrem2]+1)
    
    
    
        

main()