Cod sursa(job #318030)

Utilizator DastasIonescu Vlad Dastas Data 26 mai 2009 17:04:45
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <cstdio>

const int maxn = 30001;

#define left (2*nod)
#define right (left + 1)
#define mij ((st + dr)/2)

FILE *in = fopen("schi.in","r"), *out = fopen("schi.out","w");

int n;
int a[maxn];
int arb[1 << 16];
int rez[maxn];

void read()
{
    fscanf(in, "%d", &n);

    for ( int i = 1; i <= n; ++i )
        fscanf(in, "%d", &a[i]);
}

void build(int nod, int st, int dr)
{
    arb[nod] = dr - st + 1;

    if ( st == dr ) return;

    build(left, st, mij);
    build(right, mij+1, dr);
}

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

    if ( arb[left] < val ) return query(right, mij+1, dr, val - arb[left]);
    else                   return query(left, st, mij, val);
}

void update(int nod, int st, int dr, int what)
{
    if ( what < st || what > dr ) return;

    if ( st == dr )
    {
        arb[nod] = 0;
        return;
    }

    update(left, st, mij, what);
    update(right, mij+1, dr, what);

    arb[nod] = arb[left] + arb[right];
}

int main()
{
    read();

    build(1, 1, n);

    int t;
    for ( int i = n; i; --i )
    {
        t = query(1, 1, n, a[i]);
        rez[t] = i;

        update(1, 1, n, t);
    }

    for ( int i = 1; i <= n; ++i )
        fprintf(out, "%d\n", rez[i]);

    return 0;
}