Cod sursa(job #38338)

Utilizator filipbFilip Cristian Buruiana filipb Data 25 martie 2007 18:09:49
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <stdio.h>
#define NMax 30005
#define NMaxArb 65536

int N, v[NMax], Res[NMax], A[NMaxArb];

void init(int nod, int l, int r)
{
     int m = (l + r) / 2;
     
     if (l < r)
        init(2*nod, l, m),
        init(2*nod+1, m+1, r);
        
     A[nod] = r-l+1;
}

int query(int nod, int l, int r, int val)
{
    int m;
        
    if (l == r)
       return l;
    else
    {
        m = (l + r) / 2;
        if (val <= A[2*nod]) return query(2*nod, l, m, val);
        else return query(2*nod+1, m+1, r, val - A[2*nod]);
    }   
    
}

void update(int nod, int l, int r, int poz)
{
     int m;
     
     if (l < r)
     {
           m = (l + r) / 2;
           if (poz <= m) update(2*nod, l, m, poz);
           else update(2*nod+1, m+1, r, poz);
     }
     
     A[nod]--;
}

int main(void)
{
    int i, ok;
    
    freopen("schi.in", "r", stdin);
    freopen("schi.out", "w", stdout);    
    
    scanf("%d", &N);
    for (i = 1; i <= N; i++)
        scanf("%d", &v[i]);
           
    init(1, 1, N);
    for (i = N; i >= 1; i--)
    {
        ok = query(1, 1, N, v[i]);                
        Res[ok] = i;
        update(1, 1, N, ok);
    }
    
    for (i = 1; i <= N; i++)
        printf("%d\n", Res[i]);

    return 0;
}