Cod sursa(job #1181828)

Utilizator superman_01Avramescu Cristian superman_01 Data 3 mai 2014 22:04:36
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>

#define NMAX 10000005
#define get_max(a,b) ((a)>(b)?(a):(b))
#define get_min(a,b) ((a)>(b)?(b):(a))
#define mask 255

using namespace std;

typedef vector < int > ::iterator IT;

ifstream in ( "radixsort.in" );
ofstream out ( "radixsort.out" );

int v[NMAX] , N , A , B , C ;


void RadixSort ( int Shift )
{
	int i , j ;
	vector < int > Elem[mask+2] ;
	for ( i = 1 ; i <= N ; ++i )
		Elem[ (v[i] >> Shift) & mask].push_back( v[i] ) ;
	for ( i = 0 , j = 0 ; i <= mask ; ++i )
		for ( IT it = Elem[i].begin() ; it != Elem[i].end() ; ++it )
			v[++j] = *it;		
}

int main ( void )
{
	int i , j ;
	in >> N >> A >> B >> C;
	v[1] = B ;
	for ( i = 2 ; i <= N ; ++i )
		v[i] = ( A*v[i-1] + B ) % C ;
	for ( i = 0 ; i <= 3 ; ++i )
		RadixSort ( i * 8 ) ;
	for ( i = 1 ; i <= N ; i +=10)
		out << v[i] << " ";
	in.close();
	out.close();
	return 0 ;
}