Cod sursa(job #1867958)

Utilizator xtreme77Patrick Sava xtreme77 Data 4 februarie 2017 14:20:31
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>
#include <cstring>

using namespace std ;

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

const int MAX = 1e7 + 14 ;
const int MOD = 270 ;

int cnt [MOD] ; 
int aux [MAX] ;
int v [MAX] ;

void RadixSort ( int n ) 
{
	for ( int bucket = 0 ; bucket < 32 ; bucket += 8 ) {
		memset (cnt, 0, sizeof(cnt));
		for ( int i = 1 ; i <= n ; ++ i ) {
			cnt [ ((v[i]>>bucket) & 255) ] += 1 ;
		}
		memset (aux, 0, sizeof(aux)) ;
		for ( int i = 1 ; i < 256 ; ++ i ) {
			cnt [i] += cnt [i-1] ;
		}
		for ( int i = n ; i >= 1 ; -- i ) {
			aux [cnt[((v[i]>>bucket)&255)]--] = v [i] ;
		}
		memcpy (v,aux,sizeof(aux)) ;
	}
}

int main ()
{
	int n, a, b, c ;
	cin >> n >> a >> b >> c ; 
	v [1] = b ; 
	for ( int i = 2 ; i <= n ; ++ i ) 
		v [i] = (1LL * a * v[i-1] + 1LL * b) % c ;
	RadixSort (n) ;
	for ( int i = 1 ; i <= n ; i += 10 ) {
		cout << v [i] << ' ' ;
	}
	return 0 ;
}