Cod sursa(job #144623)

Utilizator vlad_popaVlad Popa vlad_popa Data 27 februarie 2008 20:14:16
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <cstdio>

#define MAXN (1<<15)

int AI[MAXN<<1];
int N;
int V[MAXN], val;
int sol[MAXN];

#define mj ((st + dr) >> 1)
#define ns (nod << 1)
#define nd (ns + 1)

void update (int nod, int st, int dr, int a, int b)
{
    if (a <= st && dr <= b)
        AI[nod] += val;
    else
    {
        if (a <= mj)
            update (ns, st, mj, a, b);
        if (b > mj)
            update (nd, mj + 1, dr, a, b);
            
        AI[nod] = AI[ns] + AI[nd];
    }
}

int query (int nod, int st, int dr, int Nr)
{
    if (st == dr)
        return st;
    else
        if (Nr <= AI[ns])
            return query(ns, st, mj, Nr);
        else
            return query(nd, mj + 1, dr, Nr - AI[ns]);
}

void read ()
{
    scanf ("%d\n", &N);
    
    int i;
    val = 1;
    for (i = 1; i <= N; ++ i)
    {
        scanf ("%d\n", V + i);
        update (1, 1, N, i, i);
    }
}

void solve ()
{
    val = -1;
    
    int poz, i;
    for (i = N; i > 0; -- i)
    {
        poz = query(1, 1, N, V[i]);
        sol[poz] = i;
        update (1, 1, N, poz, poz);
    }
    
    for (i = 1; i <= N; ++ i)
        printf ("%d\n", sol[i]);
}

int
 main ()
{
    freopen ("schi.in", "rt", stdin);
    freopen ("schi.out", "wt", stdout);
    
    read ();
    solve ();
    
    return 0;
}