Cod sursa(job #443891)

Utilizator DraStiKDragos Oprica DraStiK Data 18 aprilie 2010 20:16:03
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <algorithm>
using namespace std;

#define DIM 30005

int aint[DIM<<2];
int n;

void update (int nod,int st,int dr,int poz,int val)
{
    int mij;

    if (st==dr)
        aint[nod]=val;
    else
    {
        mij=(st+dr)/2;
        if (poz<=mij)
            update (nod<<1,st,mij,poz,val);
        else
            update ((nod<<1)|1,mij+1,dr,poz,val);
        aint[nod]=aint[nod<<1]+aint[(nod<<1)|1];
    }
}

int find (int nod,int st,int dr,int poz)
{
    int mij;

    if (st==dr)
        return st;
    else
    {
        mij=(st+dr)/2;
        if (poz<=aint[nod<<1])
            return find (nod<<1,st,mij,poz);
        return find ((nod<<1)|1,mij+1,dr,poz-aint[nod<<1]);
    }
}

void solve ()
{
    int i,start,next,left,poz;

    for (i=1; i<=n; ++i)
        update (1,1,n,i,1);
    for (start=i=1, left=n; left; ++i, --left)
    {
        next=(start+i)%left;
        if (!next)
            next=left;
        poz=find (1,1,n,next);
        printf ("%d ",poz);
        update (1,1,n,poz,0);
        start=next-1;
        if (!start)
            start=left-1;
    }
}

int main ()
{
    freopen ("order.in","r",stdin);
    freopen ("order.out","w",stdout);

    scanf ("%d",&n);
    solve ();

    return 0;
}