Cod sursa(job #1092774)

Utilizator matei_cChristescu Matei matei_c Data 27 ianuarie 2014 13:38:02
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include<cstdio>
#include<algorithm>
using namespace std ;

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

struct aaa
{
    int v, i ;
};

aaa 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 > 0 )
    {
        S += aib[ind] ;
        ind -= ( ind & -ind ) ;
    }

    return S ;
}

int query(int val)
{
    int ind = 1 ;
    int ad = maxp ;

    while( ad )
    {
        int V = suma( ind + ad ) ;

        if( V == val )
            return ind + ad ;

        if( V < val )
            ind += ad ;

        ad >>= 1 ;
    }

    return ind ;
}

bool cmp( aaa A, aaa B )
{
    return A.v < B.v ;
}

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[i].v = poz ; sol[i].i = i ;
        update( poz, -1 ) ;
    }

    sort( sol + 1, sol + N + 1, cmp ) ;

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

    return 0 ;
}