Cod sursa(job #1054414)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 13 decembrie 2013 20:41:42
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <fstream>
#define Nmax 30005

using namespace std;

int N,aint[4*Nmax];

inline void Build(int nod, int st, int dr)
{
    int mij;
    if(st==dr)
        aint[nod]=1;
    else
    {
        mij=(st+dr)/2;
        Build(2*nod,st,mij);
        Build(2*nod+1,mij+1,dr);
        aint[nod]=aint[2*nod]+aint[2*nod+1];
    }

}

inline void Read()
{
    int i;
    ifstream fin("order.in");
    fin>>N;
    fin.close();
    Build(1,1,N);
}

inline int Query(int nod,int x,int st,int dr)
{
    int mij;
    if(st==dr)
        return st;
    mij=(st+dr)/2;
    if(x<=aint[2*nod])
        return Query(2*nod,x,st,mij);
    return Query(2*nod+1,x-aint[2*nod],mij+1,dr);
}

inline void Update(int nod, int x, int st, int dr)
{
    int mij;
    if(st==dr)
    {
        aint[nod]=0;
        return ;
    }
    mij=(st+dr)/2;
    if(x<=mij)
        Update(nod*2,x,st,mij);
    else
        Update(nod*2+1,x,mij+1,dr);
    aint[nod]=aint[nod*2]+aint[nod*2+1];
}

inline void Solve()
{
    int pas,poz=2,len,x,i;
    ofstream fout("order.out");
    for(pas=1;pas<=N;++pas)
    {
        poz=poz+pas-1;len=aint[1];
        while(poz>len)
            poz-=len;
        x=Query(1,poz,1,N);
        Update(1,x,1,N);
        fout<<x<<" ";
    }
    fout<<"\n";
    fout.close();
}

int main()
{
    Read();
    Solve();
    return 0;
}