Cod sursa(job #2429115)

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

#define NMAX 10000000
#define BITMAX 32

using namespace std;

int v [ NMAX + 1 ] ;
int vc [ NMAX + 1 ] ; /// tinem indicii
int v2 [ NMAX + 1 ] ;
vector <int> q[2] ;

FILE *fin, *fout ;

void sortbybit (int n, int bt ) {
  int byte, i, mask, count ;
  mask = 1 << bt ;
  for (i = 1 ; i <= n ; i++ ) {
    byte = ( (v[i] & mask) == mask ) ;
    q[byte].push_back(i) ;
  }
  count = 0 ;
  for (i = 0 ; i < q[0].size() ; i++ )
    vc[++count] = q[0][i] ;
  for (i = 0 ; i < q[1].size() ; i++ )
    vc[++count] = q[1][i] ;
  q[0].erase(q[0].begin(), q[0].end()) ;
  q[1].erase(q[1].begin(), q[1].end()) ;
  for (i = 1 ; i <= count ; i++ )
    v2[i] = v[vc[i]] ;
  for (i = 1 ; i <= count ; i++ ) {
    v[i] = v2[i] ;
    //fprintf (fout, "%d ", v[i] ) ;
  }
  //fprintf (fout, "\n") ;
}

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