Cod sursa(job #1076039)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 9 ianuarie 2014 20:33:05
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <cstdio>
#define Nmax 30005

using namespace std;

int a[3*Nmax];

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

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

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

int main()
{
    int N,pas,poz=2,len,p;
    freopen ("order.in","r",stdin);
    freopen ("order.out","w",stdout);
    scanf("%d", &N);
    Build(1,1,N);
    for(pas=1;pas<=N;++pas)
    {
        poz=poz+pas-1; len=a[1];
        while(poz>len)
            poz-=len;
        p=Query(1,1,N,poz);
        printf("%d ", p);
        Update(1,1,N,p);
    }
    printf("\n");
    return 0;
}