nests

#include <bits/stdc++.h>
#define N 1000001
using namespace std;
int n,i,j,k,c[N],pot_sa_scad(),cifra_maxima,numar_orbite,lungime_orbite,numar_biti;
string p;

void calculeaza_orbite(int j)
{
    if(j==0)
    {
        numar_orbite=0;
        return;
    }
    if(2*j==n)
    {
        numar_orbite=0;
        return;
    }
    numar_orbite=__gcd(n,j); /// calculeaza gcd(n,j)
    lungime_orbite=n/numar_orbite;
    if(lungime_orbite%2==0) /// daca orbitele au lungime para descompune orbitele in doua
        numar_orbite*=2,lungime_orbite/=2;
    --numar_orbite; /// orbita care incepe in 0 este prestabilita
}

int pot_sa_scad()
{
    if(numar_orbite>cifra_maxima)
        return 0;
    if(numar_orbite==cifra_maxima&&numar_biti==1)
        return 0;
    while(p[numar_orbite]=='0')
        p[numar_orbite++]='1',++numar_biti;
    p[numar_orbite]='0';
    --numar_biti;
    while(cifra_maxima>=0&&p[cifra_maxima]=='0')
        cifra_maxima--;
    ++c[0];
    return 1;
}

int main()
{
    cin>>n>>p;
    numar_biti=count(p.begin(),p.end(),'1');
    cifra_maxima=p.size();
    --cifra_maxima;
    reverse(p.begin(),p.end());
    do
    {
        calculeaza_orbite(c[0]);
    } while(pot_sa_scad());
    for(i=0;i<cifra_maxima&&p[i]=='0';++i)
        p[i]='1';
    p[i]='0';
    k=min(c[0],n-c[0]);
    while(cifra_maxima<numar_orbite)
    {
        p=p+'0';
        cifra_maxima++;
    }
    for(i=1,j=numar_orbite-1;j>=0;++i,--j)
    {
        int x=(i+k)%n,y=(i+n-k)%n;
        if(p[j]=='0')
            c[i]=min(x,y);
        else
            c[i]=max(x,y);
    }
    ++numar_orbite;
    for(;i<n;++i)
        j=i-numar_orbite,c[i]=(i+c[j]+n-j)%n;
    for(i=0;i<n;++i)
        cout<<c[i]<<' ';
    return 0;
}