Cod sursa(job #1824385)

Utilizator KronSabau Valeriu Kron Data 7 decembrie 2016 19:51:53
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <iostream>
#include <fstream>
#define Nmax 30010
using namespace std;
int arb[4*Nmax+100],v[Nmax],sol[Nmax],n,pozitie;
ifstream f("schi.in");
ofstream g("schi.out");
void update(int nod,int st,int dr,int val)
{
    if(st==dr)
    {
        arb[nod]=val;
        return;
    }
    int mij=(st+dr)/2;

    if(pozitie<=mij)
        update(2*nod,st,mij,val);
    else
        update(2*nod+1,mij+1,dr,val);

    arb[nod]=arb[2*nod]+arb[2*nod+1];
}
int query(int nod,int st,int dr,int loc)
{
    if(st==dr)
    {
        return st;
    }
    int mij=(st+dr)/2;
    if(loc<=arb[2*nod])
        query(2*nod,st,mij,loc);

    else query(2*nod+1,mij+1,dr,loc-arb[2*nod]);

}
int main()
{
    int n;
    f>> n;
    for(int i=1;i<=n;i++){
        f>> v[i];
    }

    for(int i=1;i<=n;i++){
        pozitie=i;
        update(1,1,n,1);
    }
    for(int i=n;i>0;i--)
    {
        pozitie=query(1,1,n,v[i]);
        sol[pozitie]=i;
        update(1,1,n,0);
    }

    for(int i=1;i<=n;i++)
        g << sol[i] << "\n";
    return 0;
}