Cod sursa(job #1425087)

Utilizator GinguIonutGinguIonut GinguIonut Data 26 aprilie 2015 17:10:55
Problema Order Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <fstream>
#define dim 30001
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
int arb[4*dim],cop,nre,p,i,l,n;
void arbore(int nod, int st, int dr)
{
    if(st==dr)
    {
        arb[nod]=1;
        return;
    }
    int mijl=(st+dr)/2;
    arbore(2*nod,st,mijl);
    arbore(2*nod+1,mijl+1,dr);
    arb[nod]=arb[nod*2]+arb[nod*2+1];
}
int query(int nod, int st, int dr, int val)
{
    if(st==dr)
        return st;
    int mijl=(st+dr)/2;
    if(arb[2*nod]>=val)
        query(2*nod,st,mijl,val);
    else
        query(2*nod+1,mijl+1,dr,val-arb[2*nod]);
}
void update(int nod, int st, int dr, int poz)
{
    if(st==dr)
    {
        arb[nod]=0;
        return;
    }
    int mijl=(st+dr)/2;
    if(poz<=mijl)
        update(2*nod,st,mijl,poz);
    else
        update(2*nod+1,mijl+1,dr,poz);
    arb[nod]=arb[nod*2]+arb[nod*2+1];
}
int main()
{
    fin>>n;
    cop=1;
    l=n;
    arbore(1,1,n);
    for(i=1;i<=n;i++)
    {
        cop+=i;
        cop%=l;
        if(cop==0)
            nre=l;
        else
            nre=cop;
        p=query(1,1,n,nre);
        fout<<p<<" ";
        update(1,1,n,p);
        l--;
        cop--;
    }
    return 0;
}