Cod sursa(job #1419798)

Utilizator stoianmihailStoian Mihail stoianmihail Data 16 aprilie 2015 16:08:10
Problema Schi Scor 60
Compilator c Status done
Runda Arhiva de probleme Marime 4.17 kb
/// 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 ;
}