Cod sursa(job #1517214)

Utilizator dorin31Geman Dorin Andrei dorin31 Data 3 noiembrie 2015 22:56:52
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <iostream>
#include <fstream>
#define maxN 30001

using namespace std;

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

int n,poz,value;
int v[maxN], ans[maxN], arb[3*maxN];

void update(int nod, int st, int dr)
{
    if (st==dr)
    {
        arb[nod]+=value;
        return;
    }
    int mid=(st+dr)>>1;
    if (poz<=mid) update(nod<<1,st,mid);
    else update((nod<<1)+1,mid+1,dr);
    arb[nod]=arb[nod<<1]+arb[(nod<<1)+1];
}

int binary_srch(int value)
{
    int nod=1, st=1, dr=n;
    while (st<dr)
    {
        if (arb[nod<<1]>=value)
        {
            dr=(st+dr)>>1;
            nod<<=1;
        }
        else {
            st=((st+dr)>>1)+1;
            value-=arb[nod<<1];
            nod=(nod<<1)+1;
        }
    }
    return st;
}

int main()
{
    fin>>n;

    value=1;
    for (int i=1; i<=n; ++i)
    {
        fin>>v[i];
        poz=i;
        update(1,1,n);
    }

    //for (int i=1; i<=15; ++i) cout<<arb[i]<<" ";

    for (int i=n; i>=1; --i)
    {
        poz=binary_srch(v[i]);
        ans[poz]=i;
        value=-1;
        update(1,1,n);
    }

    for (int i=1; i<=n; ++i)
        fout<<ans[i]<<'\n';
    return 0;
}