Cod sursa(job #213417)

Utilizator dragosmihaiDragos Oana dragosmihai Data 9 octombrie 2008 19:22:56
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <fstream>

using namespace std;

int arb[120001],n,v[30001],poz,loc[30001];

void citire()
{
    ifstream f("schi.in");
    f>>n;
    for(int i=0;i<n;i++)
        f>>v[i];
}

void init(int nod,int st, int dr)
{
    if(dr<st) return;
    if(st==dr)
    {
        arb[nod]=1;
        return;
    }
    int left=nod<<1;
    int right=left+1;
    int mid=(st+dr)/2;
    init(left,st,mid);
    init(right,mid+1,dr);
    arb[nod]=arb[left]+arb[right];
}

void podium(int nod,int st,int dr)
{
    if(dr<st) return;
    if(st==dr)
    {
        arb[nod]=0;
        loc[st]=poz+1;
        return;
    }
    int left=nod<<1;
    int right=left+1;
    int mid=(st+dr)/2;
    if(v[poz]<=arb[left])
        podium(left,st,mid);
    else
    {
        v[poz]-=arb[left];
        podium(right,mid+1,dr);
    }
    arb[nod]=arb[left]+arb[right];
}

void schi()
{
    for(int i=n-1;i>=0;i--)
    {
        poz=i;
        podium(1,1,n);
    }
    ofstream g("schi.out");
    for(int i=1;i<=n;i++)
        g<<loc[i]<<"\n";

}

int main()
{
    citire();
    init(1,1,n);
    schi();
    return 0;
}