Cod sursa(job #346832)

Utilizator freak93Adrian Budau freak93 Data 9 septembrie 2009 20:03:41
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include<fstream>

using namespace std;

const char iname[]="order.in";
const char oname[]="order.out";
const int maxn=66100;

ifstream f(iname);
ofstream g(oname);

int aib[maxn],i,j,n,k,maxt,elim;

int update(int nod,int l,int r,int w,int v)
{
    if(l==r)
        {
            aib[nod]+=v;
            return w;
        }
    aib[nod]+=v;

    int mij=(l+r)>>1;
    if(w<=mij)
        update(2*nod,l,mij,w,v);
    if(w>mij)
        update(2*nod+1,mij+1,r,w,v);

    return w;
}

int query(int nod,int l,int r,int x)
{
    if(l==r)
        return l;

    int mij=(l+r)>>1;
    if(x<=aib[nod*2])
        return query(nod*2,l,mij,x);
    else
        return query(nod*2+1,mij+1,r,x-aib[nod*2]);
}

int main()
{
    f>>n;
    for(maxt=1;maxt<n;maxt<<=1);
    for(i=1;i<=n;++i)
        update(1,1,maxt,i,1);
    elim=1;
    for(j=1,i=n;i;--i,++j)
        elim+=j,g<<update(1,1,maxt,query(1,1,maxt,elim=(elim-1)%i+1),-1)<<" ",--elim;
    g<<"\n";

    f.close();
    g.close();

    return 0;
}