Cod sursa(job #1425500)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 27 aprilie 2015 16:12:33
Problema Schi Scor 100
Compilator cpp Status done
Runda pregatire-lot-aib Marime 0.95 kb
#include<cstdio>

using namespace std;

FILE *fin = fopen( "schi.in", "r" ), *fout = fopen( "schi.out", "w" );

const int nmax = 30000;
int v[ nmax + 1 ], p[ nmax + 1 ];
int ai[ 4 * nmax + 1 ];

void update( int nod, int st, int dr, int poz, int i ) {
    if ( st == dr ) {
        ai[ nod ] = 1;
        p[ st ] = i;
        return ;
    }
    int mid = ( st + dr ) / 2;
    if ( mid - st + 1 - ai[ 2 * nod ] >= poz ) {
        update( 2 * nod, st, mid, poz, i );
    } else {
        update( 2 * nod + 1, mid + 1, dr, poz - mid + st - 1 + ai[ 2 * nod ], i );
    }
    ai[ nod ] = ai[ 2 * nod ] + ai[ 2 * nod + 1 ];
}
int main() {
    int n;
    fscanf( fin, "%d", &n );
    for( int i = 1; i <= n; ++ i ) {
        fscanf( fin, "%d", &v[ i ] );
    }
    for( int i = n; i > 0; -- i ) {
        update( 1, 1, n, v[ i ], i );
    }
    for( int i = 1; i <= n; ++ i ) {
        fprintf( fout, "%d\n", p[ i ] );
    }
    fclose( fin );
    fclose( fout );
    return 0;
}