Cod sursa(job #2429123)

Utilizator alex.cojocaruAlex Cojocaru alex.cojocaru Data 7 iunie 2019 22:56:11
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <iostream>
#include <queue>

#define NMAX 10000000
#define BITMAX 32
#define VALMAX 2
using namespace std;

int v [ NMAX ] ;
int vc [ NMAX ] ; /// tinem indicii
int f [ VALMAX ] ;
FILE *fin, *fout ;

void sortbybit (int n, int bt ) {
  int byte, i, mask ;
  mask = (1 << bt) ;
  for (i = 1 ; i <= n ; i++ ) {
    byte = ( ( v[i] & mask ) == mask ) ;
    f[byte]++;
  }
  for (i = 1 ; i <= VALMAX ; i++ )
    f[i] += f[i-1] ;
  for (i = n ; i >= 1 ; i-- ) {
    byte = ( ( v[i] & mask ) == mask ) ;
    vc[f[byte]--] = v[i] ;
  }
  for (i = 0 ; i <= VALMAX ; i++ )
    f[i] = 0 ;
  for (i = 1 ; i <= n ; i++ ) {
    v[i] = vc[i] ;
  }
}

int main() {
  fin = fopen ("radixsort.in", "r" ) ;
  fout = fopen ("radixsort.out", "w" ) ;
  int n, i, a, b, c ;
  fscanf (fin, "%d%d%d%d", &n, &a, &b, &c ) ;
  for (i = 1 ; i <= n ; i++ )
    v[i] = (v[i-1] * a + b ) % c ;
  for (i = 0 ; i < BITMAX ; i++ )
    sortbybit (n, i) ;
  for (i = 1 ; i <= n ; i+=10)
    fprintf (fout, "%d ", v[i] ) ;
  return 0;
}