Pagini recente » Cod sursa (job #2442466) | Cod sursa (job #2820566) | Cod sursa (job #2471498) | Cod sursa (job #2688906) | Cod sursa (job #1419798)
/// Bibliotecilecare ne trebuiesc
#include <stdio.h> /// pentru fread() + fwrite() + printf()
#include <ctype.h> /// pentru isdigit()
#include <math.h> /// pentru log2()
/// constantele care ne trebuiesc
#define Nadejde 32768 /// marimea AIB-ului
#define Smerenie 30000 /// marimea vectorul
#define Dragoste 4096 /// marimea bufferului
#define MAXDIG 5 /// cate cifre poate avea un short ?
/// variabilele care ne trebuiesc
int LOG ; /// 2^( lg + 1 )
int number ; /// numarul cautat
int interval ; /// folosit la cautarea binara
int Fenwick[ Nadejde + 1 ] ; /// AIB -ul nostru
char c ; /// un caracter
char digits[ MAXDIG ] ; /// vectorul cu cifrele numarului
char buff[ Dragoste ] ; /// bufferul oferit de sistem
char Buff[ Dragoste ] ; /// bufferul de iesire
short n ; /// cati concurenti avem
short i ; /// un index
short lg ; /// log2(n)
short dig ; /// cate cifre avem
short div ; /// catul impartirii la 10
short parse ; /// pozitia in Buff[]
short pos = Dragoste ; /// pozitia in buff[]
short Ski[ Smerenie + 1 ] ; /// vectorul nostru
short Position[ Smerenie + 1 ] ; /// clasamentul final
/// un fel de fgetc()
char getChar( FILE *fin )
{
/// daca am golit buff[]
if( pos == Dragoste )
{
fread ( buff , 1 , Dragoste , fin ) ;
pos = 0 ;
}
return buff[ pos ++ ] ;
}
/// un fel de fscanf() dar mai rapid
inline void fLaser( FILE *fin , short *result )
{
*result = 0 ;
do{
c = getChar( fin ) ;
}while( !isdigit( c ) ) ;
do{
*result = ( *result << 3 ) + ( *result << 1 ) + c - '0' ;
c = getChar( fin ) ;
}while( isdigit( c ) ) ;
}
/// un fel de fputc()
inline void putChar( FILE *fout , char ch )
{
Buff[ parse ++ ] = ch ;
/// daca s-a umplut Buff[]
if( parse == Dragoste )
{
fwrite( Buff , 1 , Dragoste , fout ) ;
parse = 0 ;
}
}
/// un fel fprintf() dar mai rapid
inline void fPut( FILE *fout , short num )
{
dig = 0 ;
do{
div = num / 10 ;
digits[ dig ++ ] = num - ( div << 3 ) - ( div << 1 ) + '0' ;
num = div ;
}while( num ) ;
do{
putChar( fout , digits[ -- dig ] ) ;
}while( dig ) ;
}
/// golim Buff[]
void FlushBuff( FILE *fout )
{
fwrite( Buff , 1 , parse , fout ) ;
}
/// updatam AIB-ul
void Add ( int val , short x )
{
do{
Fenwick[ x ] += val ;
x += x & -x ;
}while( x <= LOG ) ;
}
/// cautam binar suma partiala val
int BinarySearch( int val )
{
int x = 0 ;
int poz = -1 ;
interval = LOG ;
while( interval )
{
if( Fenwick[ x + interval ] < val )
{
val -= Fenwick[ x + interval ] ;
x += interval ;
}
else
{
if( Fenwick[ x + interval ] == val )
{
poz = x + interval ;
}
}
interval >>= 1 ;
}
return poz ;
}
/// int main()
int main( )
{
/// deschidere fisiere *C*
FILE *fin = fopen( "schi.in" , "r" ) ;
FILE *fout = fopen( "schi.out" , "w" ) ;
/// citim parsat datele de intrare
fLaser( fin , &n ) ;
/// calculam logaritmii
lg = log2( n ) ;
LOG = 1 << ( lg + 1 ) ;
/// citim parsat vectorul
for( i = 1 ; i <= n ; i ++ )
{
fLaser( fin , &Ski[ i ] ) ;
/// facem update in punctul i
Add( 1 , i ) ;
}
/// parcurgem invers vectorul
for( i = n ; i > 0 ; i -- )
{
/// cautam pozitia
number = BinarySearch( Ski[ i ] ) ;
Add( -1 , number ) ;
Position[ number ] = i ;
}
/// afisam parsat vectorul clasament
for( i = 1 ; i <= n ; i ++ )
{
fPut( fout , Position[ i ] ) ;
putChar( fout , '\n' ) ;
}
/// golim Buff[]
FlushBuff( fout ) ;
/// inchidem fisierele
fclose( fin ) ;
fclose( fout ) ;
/// Multumim Doamne!
printf( "Hristos a inviat!" ) ;
/// dai return 0
return 0 ;
}