Cod sursa(job #2549566)

Utilizator ReksioCroftOctavian Florin Staicu ReksioCroft Data 17 februarie 2020 19:55:39
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <stdio.h>
#include <vector>
#define nmax 10000000
using namespace std;
int v[nmax];

void radixsort( int start, int stop, int mask) {
  int i, poz;
  vector<int> v0;
  vector<int> v1;
  for( i = start; i <= stop; i++ ) {
    if ( ( v[i] & mask ) != 0 )
      v1.push_back( v[i] );
    else
      v0.push_back( v[i] );
  }
  poz = start;
  for ( i = 0; i < v0.size(); i++ )
    v[poz++] = v0[i];
  for ( i = 0; i < v1.size(); i++ )
    v[poz+i] = v1[i];
  v1.clear();
  v0.clear();
  if( mask == 0 )
    return;
  if( poz-1 > start )
    radixsort( start, poz-1, mask>>1 );
  if( poz < stop )
    radixsort( poz, stop, mask>>1 );
}

int main() {
  int n, a, b, c, i;
  FILE *fin, *fout;
  fin = fopen( "radixsort.in", "r" );
  fscanf( fin, "%d%d%d%d", &n, &a, &b, &c );
  fclose( fin );
  v[0] = b;
  for ( i = 1; i < n; i++ )
    v[i] = ( 1LL * a * v[i-1] + b ) % c;

  radixsort( 0, n-1, 1<<30 );
  fout = fopen( "radixsort.out", "w" );

  for ( i = 0; i < n; i+=10 )
    fprintf( fout, "%d ", v[i]);
  fclose( fout );
  return 0;
}