Cod sursa(job #1789557)

Utilizator denniscrevusDennis Curti denniscrevus Data 27 octombrie 2016 09:52:45
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <fstream>
#define NMAX 30005

using namespace std;

int arb[3*NMAX], n, b[NMAX], rez[NMAX],i,aux, v[NMAX];

void update(int st, int dr, int poz, int nod)
{
    if(st == dr)
    {
        arb[nod] = b[poz];
        return;
    }

    int mid = (st + dr)>>1;

    if(mid>=poz)
        update(st, mid, poz, nod<<1);
    if(mid<poz)
        update(mid+1, dr, poz, (nod<<1)+1);

    arb[nod] = arb[nod<<1] + arb[(nod<<1) + 1];
}

int cautbin(int st, int dr, int val, int nod)
{
    if(st == dr)
        return st;

    int mid = (st + dr)/2;

    if(arb[nod<<1] >= val)
        return cautbin(st, mid, val, nod<<1);
    else
    {
        val -= arb[nod<<1];
        return cautbin(mid+1, dr, val, (nod<<1)+1);
    }
}

ifstream f("schi.in");
ofstream g("schi.out");

int main()
{
    f>>n;

    for(i=1;i<=n;i++)
    {
        f>>v[i];
        b[i] = 1;
        update(1, n, i, 1);
    }

    for(i=n;i>=1;i--)
    {
        aux = cautbin(1,n,v[i],1);
        //g<<aux<<" ";
        b[aux] = 0;
        update(1,n,aux,1);
        rez[aux] = i;
    }
    //g<<"\n";
    for(i=1;i<=n;i++)
        g<<rez[i]<<"\n";
}