Cod sursa(job #1778963)

Utilizator Tiberiu02Tiberiu Musat Tiberiu02 Data 14 octombrie 2016 16:06:51
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <cstdio>

#define MAXN 30000
#define INF 999999

int v[MAXN+1], aib[MAXN+1], clasament[MAXN+1], n;

using namespace std;

void update( int p, int val )
{
    for( ; p<=n; p+=p&-p )
        aib[p]+=val;
}

int query( int p )
{
    int s=0;

    for( ; p>0; p-=p&-p )
        s=s+aib[p];

    return s;
}

int caut( int val )
{
    int b=1, e=n, m, p, l=INF;

    while( b<=e )
    {
        m=(b+e)/2;
        p=query(m);

        if( p==val && l>m )
            l=m;
        else
            if( p<val )
                b=m+1;
            else
                e=m-1;
    }

    return l;
}

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

    int poz, i;

    scanf( "%d", &n );

    for( i=1;i<=n;i++ )
    {
        scanf( "%d", &v[i] );

        aib[i]=i&-i;
    }

    for( i=n;i>=1;i-- )
    {
        poz=caut(v[i]);
        clasament[poz]=i;

        update(poz,-1);
    }

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

    return 0;
}