Cod sursa(job #810355)

Utilizator alexalghisiAlghisi Alessandro Paolo alexalghisi Data 10 noiembrie 2012 10:32:12
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <iostream>
#include <fstream>
#define DN 120005
using namespace std;

int arb[DN],total=0,poz,rez;
int v[30004];
int final[30004];

void update(int nod,int left,int right,int p)
{
    if(left==right)
    {
        arb[nod]=p;
        return;
    }
    int mij=(left+right)/2;
    if(poz<=mij) update(2*nod,left,mij,p);
    else update(2*nod+1,mij+1,right,p);

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

void find(int nod,int left,int right,int suma)
{
    if(left==right)
    {
        rez=left;
        arb[nod]=0;
        return;
    }
    int mij=(left+right)/2;
    if(suma<=arb[2*nod]) find(2*nod,left,mij,suma);
    else find(2*nod+1,mij+1,right,suma-arb[2*nod]);
    arb[nod]=arb[2*nod]+arb[2*nod+1];
}


int main()
{
    int n;
    ifstream f("schi.in");
    ofstream g("schi.out");
    f>>n;
    for(int i=1;i<=n;i++)
    {
        f>>v[i];
        poz=i;
        update(1,1,n,1);
    }

    for(int i=n;i>=1;i--)
    {
        total=0;

        find(1,1,n,v[i]);
        final[rez]=i;
    }
    for(int i=1;i<=n;i++)
        g<<final[i]<<"\n";
    return 0;
}