Cod sursa(job #1092803)

Utilizator matei_cChristescu Matei matei_c Data 27 ianuarie 2014 14:04:40
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include<cstdio>
#include<algorithm>
using namespace std ;

#define maxn 30001
#define maxp ( 1 << 14 )



int sol[maxn] ;

int N, v[maxn] ;

int aib[maxn] ;

void update(int ind, int val)
{
    while( ind <= N )
    {
        aib[ind] += val ;
        ind += ( ind & -ind ) ;
    }
}

int suma(int ind)
{
    int S = 0 ;

    if( ind > N )
        ind = N ;

    while( ind )
    {
        S += aib[ind] ;
        ind -= ( ind & -ind ) ;
    }

    return S ;
}

int query(int val)
{
    int ind = 0 ;
    int ad = maxp ;
    int sum = 0;
    int rez = 0;
    while( ad )
    {
        if( ind + ad <= N && sum + aib[ind + ad] <= val )  {
            if( sum + aib[ind + ad] == val ) {
                rez = ind + ad;
                ad >>= 1;
                continue;
            }
            sum += aib[ind + ad];
            ind += ad;

        }
        ad >>= 1 ;

    }

    return rez ;
}


int main()
{
    freopen("schi.in", "r", stdin);
    freopen("schi.out", "w", stdout);

    scanf("%d", &N);

    for(int i = 1; i <= N; ++i )
        update(i, 1), scanf("%d", &v[i]) ;

    for(int i = N; i > 0; --i )
    {
        int poz = query( v[i] ) ;
        sol[poz] = i;
        update( poz, -1 ) ;
    }

    for(int i = 1; i <= N; ++i )
        printf("%d\n", sol[i]);

    return 0 ;
}