Cod sursa(job #956357)

Utilizator dariusdariusMarian Darius dariusdarius Data 2 iunie 2013 22:11:17
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include<cstdio>
#include<cstring>
#include<cassert>
#include<algorithm>
using namespace std;
int aint[200000];
int n,N;
void update(int nod,int st,int dr,int i)
{
    if(st==dr) aint[nod]=0;
    else
    {
        int med=(st+dr)/2;
        if(i<=med)
            update(2*nod,st,med,i);
        else
            update(2*nod+1,med+1,dr,i);
        aint[nod]=aint[2*nod]+aint[2*nod+1];
    }
}
int query(int nod,int st,int dr,int x,int y)
{
    if(x<=st && dr<=y)
        return aint[nod];
    int v1=0,v2=0,med=(st+dr)/2;
    if(x<=med)
        v1=query(2*nod,st,med,x,y);
    if(y> med)
        v2=query(2*nod+1,med+1,dr,x,y);
    return v1+v2;
}
int ith_1(int nod,int st,int dr,int i)
{
    if(st==dr) return st;
    ///al i-lea 1 din intervalul [st,dr]
    int med=(st+dr)/2;
    if(i>aint[2*nod])
        return ith_1(2*nod+1,med+1,dr,i-aint[2*nod]);
    return ith_1(2*nod,st,med,i);
}
void query_ith(int &i,int pas)
{
    pas+=aint[1];pas-=query(1,1,N,i+1,n);
    assert(aint[1]!=0);
    pas=pas%aint[1];if(pas==0) pas=aint[1];
    i=ith_1(1,1,N,pas);
}
int main()
{
    freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);
    scanf("%d",&n);
    for(N=1;N<n;N<<=1);
    for(int i=1;i<=n;i++)
        aint[N+i-1]=1;
    for(int i=N-1;i>=1;i--)
        aint[i]=aint[2*i]+aint[2*i+1];
    int X=1;
    for(int i=1;i<=n;i++)
    {
        query_ith(X,i);
        printf("%d%c",X,i==n?'\n':' ');
        update(1,1,N,X);
    }
    return 0;
}