Cod sursa(job #2634672)

Utilizator euyoTukanul euyo Data 11 iulie 2020 22:13:30
Problema Radix Sort Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.68 kb
#include <cstdio>
#include <vector>

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

const int NumBits = 16;
const int Mask = 65535;
const int MaxN = 10000000;
const int Max10 = 10;
const int BufSz = (1 << 17);

int v[MaxN], f[Mask + 1], aux[MaxN], n;
int p10[Max10 + 1] = { 0, 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 };
char wbuf[BufSz];
int wpos = 0;

static inline void writeChar( char ch ) {
  wbuf[wpos] = ch;
  if ( !(wpos = (wpos + 1) & (BufSz - 1)) ) {
    fwrite( wbuf, 1, BufSz, fout );
  }
}
void writeInt( int x ) {
  int i, cf;
  i = Max10;
  while ( p10[i] > x ) {
    --i;
  } 
  if ( i == 0 ) {
    writeChar( '0' );
  } else {
    do {
      cf = '0';
      while ( p10[i] <= x ) {
        x -= p10[i];
        ++cf;
      }
      writeChar( cf );
    } while ( --i > 0 );
  }
  writeChar( ' ' ); 
}
static inline void flushBuf() {
  fwrite( wbuf, 1, wpos, fout );
}

static inline void countSort( int step ) {
  int u4, i;
   
  for ( i = 0; i <= Mask; ++i ) {
	f[i] = 0;
  }
  for ( i = 0; i < n; ++i ) {
	u4 = ((v[i] >> (NumBits * step)) & Mask);
    ++f[u4];
  }
  for ( i = 1; i <= Mask; ++i ) {
    f[i] += f[i - 1];
  }
  for ( i = n - 1; i >= 0; --i ) {
	u4 = ((v[i] >> (NumBits * step)) & Mask);
    aux[--f[u4]] = v[i];	
  }
  for ( i = 0; i < n; ++i ) {
	v[i] = aux[i];	
	aux[i] = 0;
  }
} 

int main() {
  int a, b, c;
  
  fscanf( fin, "%d%d%d%d", &n, &a, &b, &c );
  v[0] = b;
  for ( int i = 1; i < n; ++i ) {
    v[i] = ((long long)a * v[i - 1] + b) % c;
  }
  countSort( 0 );
  countSort( 1 );
  for ( int i = 0; i < n; i += 10 ) {
    writeInt( v[i] );
  }
  flushBuf();
  fclose( fin );
  fclose( fout );
  return 0;
}