Cod sursa(job #212223)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 4 octombrie 2008 17:43:20
Problema Schi Scor 75
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <fstream>
#define Lg_max 30001

using namespace std;

ifstream fin ("schi.in");
ofstream fout ("schi.out");

int heap[Lg_max<<1];
int val_final[Lg_max];
int sir[Lg_max],n,poz,val;

void citire()
{
    fin>>n;
    for (int i=1 ; i<=n ;i++)
        fin>>sir[i];
}

void umple(int st,int dr,int niv)
{
    if (st>dr)
        return;
    if (st==dr)
    {
        heap[niv]=1;
        return ;
    }
    int mij=(st+dr)>>1;

    umple( st ,mij , (niv<<1));
    umple( mij+1 ,dr ,(niv<<1)+1);

    heap[niv]=heap[niv<<1]+heap[(niv<<1)+1];
}

void regen(int nod ,int st,int dr)
{
    if (st>dr)
        return ;
    if (st==dr)
    {
        heap[nod]=0;
        val_final[st]=val;
        return ;
    }
    int mij=(st+dr)>>1;
    if (poz<=heap[(nod<<1)])
        regen((nod<<1),st,mij);
    else
    {
        poz=poz-heap[(nod<<1)];
        regen((nod<<1)+1,mij+1,dr);
    }
//se refac sumele
heap[nod]=heap[(nod<<1)+1]+heap[(nod<<1)];
}


void rezolvare()
{
    umple(1,n,1);
    for (int i=n;i>=1;i--)
    {
        poz=sir[i];
        val=i;
        regen(1,1,n);
    }
}

void afisare()
{
    for (int i=1;i<=n;i++)
        fout<<val_final[i]<<" \n";
}

int main ()
{
    citire();
    rezolvare();
    afisare();
    return 0;
}