Cod sursa(job #1764288)

Utilizator din99danyMatei Daniel din99dany Data 25 septembrie 2016 13:13:01
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <fstream>
#include <algorithm>
using namespace std;

#define NMAX 30002

int          n,
      v[ NMAX ],
    aib[ NMAX ],
    sol[ NMAX ],
 ocupat[ NMAX ];

int sum( int pos );
int cauta( int val );
void add( int pos, int k );


int main(){


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

    int i, j, x, y, poz;

    scanf("%d",&n);

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

    for( i = n; i >= 1; --i ){
        poz = cauta( v[ i ] );
        add( poz, -1 );
        sol[ poz ] = i;
        ocupat[ poz ] = 1;
    }

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

    return 0;
}

void add( int pos, int k ){

    while( pos <= n ){
        aib[ pos ] += k;
        pos += ( pos & ( - pos ) );
    }

}

int sum( int pos ){

    int s = 0;

    while( pos > 0 ){
        s += aib[ pos ];
        pos -= ( pos & ( - pos ) );
    }

    return s;
}

int cauta( int val ){

    int i = 0;
    int pas = (1 << 18);

    while( pas ){
        if( i + pas < n && sum( i + pas ) < val ) i += pas;
        pas /= 2;
    }

    return i + 1;
}