Cod sursa(job #1081490)

Utilizator addy01adrian dumitrache addy01 Data 13 ianuarie 2014 18:04:29
Problema Order Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <iostream>
#include <fstream>
#define MAXN 30000
using namespace std;

ifstream in("order.in");
ofstream out("order.out");

int n;
int arbint[2*MAXN];

inline void constr(int nod,int st,int dr)
{
    if(st==dr)
        {
            arbint[nod]=1;
            return ;
        }

    int mid=(st+dr) >> 1;

        constr(2*nod,st,mid);
        constr(2*nod+1,mid+1,dr);

    arbint[nod]=arbint[2*nod]+arbint[2*nod+1];
}

inline void update(int nod,int st,int dr,int poz)
{
    if(st==dr)
    {
        arbint[nod]=0;
        return ;
    }
    int mid=(st+dr) >> 1;

    if(poz<=mid)
        update(2*nod,st,mid,poz);
    else
        update(2*nod+1,mid+1,dr,poz);

    arbint[nod]=arbint[2*nod]+arbint[2*nod+1];
}

inline int query(int nod,int st,int dr,int x)
{
    if(st==dr)
       return st;

    int mid=(st+dr) >> 1;

    if(x<=arbint[2*nod])
        return query(2*nod,st,mid,x);
    else
        return query(2*nod+1,mid+1,dr,x-arbint[2*nod]);

}


int main()
{
    in>>n;
    constr(1,1,n);
    int i,poz=2,len,p;
    for(i=1;i<=n;i++)
        {
            poz=poz+i-1;
            len=arbint[1];

            while(poz>len)
                poz-=len;

            p=query(1,1,n,poz);
            out<<p<<" ";

            update(1,1,n,p);

        }
out<<"\n";

    return 0;
}