Pagini recente » Cod sursa (job #1176203) | Cod sursa (job #1256645) | Cod sursa (job #564917) | Cod sursa (job #682693) | Cod sursa (job #1666396)
#include <stdio.h>
#define MAX_N 30000
int aib[ 1 + MAX_N ];
int locul[ MAX_N ];
int locPartial[ MAX_N ];
//determinam ultimul bit al lui n
inline int lastBit( int x ) { return x & -x; }
//adaugam val la pozitia i si actualizam aib-ul
inline void add( int i , int val , int n ) {
while( i <= n ) {
aib[ i ] += val;
i += lastBit( i );
}
}
//calculam suma de la 1 la i in aib
inline int suma( int i ) {
int s;
s = 0;
while( i > 0 ) {
s += aib[ i ];
i -= lastBit( i );
}
return s;
}
//calculeaza locul in clasamentul partial pt locul dat
int calculLoc( int loc ) { return loc - suma( loc - 1 ); }
//cauta pe ce loc se afla cel de pe locul dat in clasamentul partial
int cautare( int loc , int n ) {
int min , max , mid;
min = 0;
max = n;
while( max - min > 1 ) {
mid = ( min + max ) >> 1;
if( calculLoc( mid + 1 ) <= loc )
min = mid;
else
max = mid;
}
return min;
}
int main() {
int n , i , loc ;
FILE *fin = fopen( "schi.in" , "r" );
fscanf( fin , "%d" , &n );
for( i = 0 ; i < n ; i++ )
fscanf( fin , "%d" , &locPartial[ i ] );
fclose( fin );
//pt fiecare concurent caut locul lui in clasamentul real
for( i = n - 1 ; i >= 0 ; i-- ) {
loc = cautare( locPartial[ i ] , n );
locul[ loc ] = i + 1;
add( loc + 1 , 1 , n );
}
FILE *fout = fopen( "schi.out" , "w" );
//scriu clasamentul
for( i = 0 ; i < n ; i++ )
fprintf( fout , "%d\n" , locul[ i ] );
fclose( fout );
return 0;
}