Cod sursa(job #1854147)

Utilizator TincaMateiTinca Matei TincaMatei Data 22 ianuarie 2017 14:06:20
Problema Schi Scor 95
Compilator c Status done
Runda Arhiva de probleme Marime 2.24 kb
#include <stdio.h>
#define MAX_N 30000
#include <ctype.h>

/** Funcţiile necesare parsării fişierului de intrare **/
FILE *_fin;
int _in_loc; char _in_buff[4096];


void read_init(const char* nume) // Apelaţi această funcţie la începutul funcţiei <main>
{
    _fin = fopen(nume, "r");
    _in_loc = 4095;
}

char read_ch()
{
    ++_in_loc;
    if (_in_loc == 4096) {
        _in_loc = 0;
        fread(_in_buff, 1, 4096, _fin);
    }
    return _in_buff[_in_loc];
}

int read_u32() // Apelaţi această funcţie pentru a citi un număr ce se încadrează în categoria <unsigned int>
{
    int u32 = 0; char c;
    while (!isdigit(c = read_ch()) && c != '-');
    int sgn = 1;
    if (c == '-') {
        sgn = -1;
    } else {
        u32 = c - '0';
    }
    while (isdigit(c = read_ch())) {
        u32 = u32 * 10 + c - '0';
    }
    return u32 * sgn;
}

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
inline 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 , rez;
  min = 0;
  max = n;
  while( max - min > 1 ) {
    mid = ( min + max ) >> 1;
    rez = calculLoc( mid + 1 );
    if( rez <= loc )
      min = mid;
    else
      max = mid;
  }
  return min;
}

int main() {
  int n , i , loc ;
  read_init("schi.in");
  n = read_u32();
  for( i = 0 ; i < n ; i++ )
    locPartial[i] = read_u32();

  //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;
}