Cod sursa(job #1866322)

Utilizator xtreme77Patrick Sava xtreme77 Data 2 februarie 2017 21:04:56
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <bits/stdc++.h>

using namespace std ;

const int MAX = 1e7 + 14 ;
const int MOD = ( 1 << 8 ) + 14 ;

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

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

int main ()
{
	int n , a , b , c ; 
	fin >> n >> a >> b >> c ; 
	v [1] = b ; 
	for ( int i = 2 ; i <= n ; ++ i ) {
		v [i] = (1LL * v [i-1] * a + 1LL * b) % c ;
	}
	for ( int i = 0 ; i < 32 ; i += 8 ) {
		memset (ind, 0, sizeof(ind)) ;
		int sz = 0 ; 
		for ( int j = 1 ; j <= n ; ++ j ) {
			ind [((v[j] >> i) & 255)] ++ ; 
		}
		for ( int j = 0 ; j <= 256 ; ++ j ) {
			ind [j] += ind [j-1] ; 
		}
		memset (aux, 0, sizeof(aux)) ;
		for ( int j = n ; j >= 1 ; -- j ) {
			aux [ind[((v[j] >> i) & 255)]--] = v [j] ;
		}
		memcpy (v,aux,sizeof(aux)) ;
	}
	for ( int i = 1 ; i <= n ; i += 10 ) {
		fout << v [i] << ' ' ; 
	}
	return 0 ; 
}