Cod sursa(job #1068283)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 28 decembrie 2013 10:48:41
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <fstream>

#define maxn 30001

using namespace std;

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

int v[maxn],arb[maxn*4];
int ans[maxn];
int n,val,wh;

void create_arb (int node, int left, int right)
{
    if (left == right)
    {
        arb[node] = 1;
        return;
    }

    int mid = (left+right)/2;

    create_arb (node<<1,left,mid);
    create_arb ((node<<1)+1,mid+1,right);

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

void update (int node, int left, int right)
{
    if (left == right)
    {
        arb[node] = 0;
        return;
    }

    int mid = (left+right)/2;

    if (wh <= mid)
        update (node<<1,left,mid);
    else
        update ((node<<1)+1,mid+1,right);

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

void query (int node, int left, int right)
{
    if (left == right)
    {
        wh = left;
        return;
    }

    int mid =(left+right)/2;

    if (val <= arb[node<<1])
    {
        query (node<<1,left,mid);
    }
    else
    {
        val -= arb[node<<1];
        query ((node<<1)+1,mid+1,right);
    }
}

int main()
{
    fin>>n;

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

    create_arb (1,1,n);

    for (int i=n; i>=1; --i)
    {
        val = v[i];

        query (1,1,n);

        ans[wh] = i;

        update (1,1,n);
    }

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