Cod sursa(job #2400517)

Utilizator onipreponiprep oniprep Data 8 aprilie 2019 20:27:30
Problema Order Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
const int N=30009;
int n,STEP;
int aint[2*N];
void build()
{
    for(int i=1;i<=n;++i)
        aint[i+n-1]=1;
    for(int i=n-1;i>=1;--i)
        aint[i]=aint[i<<1]+aint[(i<<1)|1];
}
void update(int a,int b)
{
    for(aint[a+=n-1]=b;a>=1;a>>=1)
        aint[a>>1]=aint[a]+aint[a^1];
}
int query(int st,int dr)
{
    int ans=0;
    for(st+=n-1,dr+=n;st<dr;st>>=1,dr>>=1)
    {
        if(st&1)
            ans+=aint[st++];
        if(dr&1)
            ans+=aint[--dr];
    }
    return ans;
}
int binary(int val)
{
    int ans=0,step=STEP;
    for(;step;step>>=1)
    {
        if(query(1,ans+step)<val)
            ans+=step;
        if(ans==val+1)
            break;
    }
    return ans+1;
}
int main()
{
    fin.sync_with_stdio(false);
    fin>>n;
    int nn=n,pas=0,curr=1;
    STEP=1<<(int(log2(n)+1));
    build();
    while(nn)
    {
        pas++;
        int next=(query(1,curr)+pas)%nn;
        if(!next)
            next+=nn;
        int ans=binary(next);
        update(ans,0);
        fout<<ans<<" ";
        curr=ans;
        nn--;
    }
    return 0;
}