Cod sursa(job #179490)

Utilizator tm_raduToma Radu tm_radu Data 15 aprilie 2008 22:54:56
Problema Schi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <stdio.h>
#define NM 30001
#define lf (nod<<1)
#define rt (lf+1)
#define mij ((st+dr)>>1)

int n, p[NM], a[2*NM], c[NM];
int i, j, k, pos;

void Build(int nod, int st, int dr);
int Query(int nod, int st, int dr, int nr);
void Update(int nod, int st, int dr);

int main()
{
    freopen("schi.in", "r", stdin);
    freopen("schi.out", "w", stdout);
    scanf("%d", &n);
    for ( i = 1; i <= n; ++i )
        scanf("%d", &c[i]);
    Build(1, 1, n);
    
    for ( i = n; i >= 1; --i )
    {
        pos = Query(1, 1, n, c[i]);
        p[pos] = i;
        Update(1, 1, n);
    }
    for ( i = 1; i <= n; i++ )
        printf("%d\n", p[i]);
    
    return 0;
}

void Build(int nod, int st, int dr)
{
    if ( st == dr )
    {
        a[nod] = 1;
        return;
    }
    Build(lf, st, mij);
    Build(rt, mij+1, dr);
    a[nod] = a[lf] + a[rt];
}

int Query(int nod, int st, int dr, int nr)
{
    if ( st == dr ) return st;
    if ( nr <= a[lf] ) return Query(lf, st, mij, nr);
    else               return Query(rt, mij+1, dr, nr - a[lf]);
}

void Update(int nod, int st, int dr)
{
    if ( st == dr )
    {
        a[nod]--;
        return;
    }
    if ( pos <= mij ) Update(lf, st, mij);
    else              Update(rt, mij+1, dr);
    a[nod] = a[lf] + a[rt];
}