Cod sursa(job #1227923)

Utilizator andreas.chelsauAndreas Chelsau andreas.chelsau Data 12 septembrie 2014 10:45:01
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <iostream>
using namespace std;

int n,a,b,c;
short int bucket[10000001][4];

short int B[10000001][4];
void fill_buckets(int k, int nr){
	bucket[k][0] = nr % 1000;
	bucket[k][1] = (nr % 1000000 - bucket[k][0]) / 1000;
	bucket[k][2] = (nr % 1000000000 - bucket[k][1] * 1000 - bucket[k][0]) / 1000000;
	bucket[k][3] = (nr - bucket[k][2] * 1000000 - bucket[k][1] * 1000 - bucket[k][0]) / 1000000000;
}
void create_buckets(){
	int nr;
	nr = b;
	fill_buckets(0,nr);
	for(int i = 1; i < n; i++){
		nr = (int)(((long long)a * (long long)nr + (long long)b) % (long long)c);
		fill_buckets(i,nr);
	}
}
void counting_sort(int d){
	int C[1001];
	for(int i = 0; i < 1000; i++)
		C[i] = 0;
	for(int i = 0; i < n; i++)
		C[bucket[i][d]]++;
	for(int i = 1; i < 1000; i++)
		C[i] += C[i - 1];
	for(int i = n - 1; i >= 0; i--){
		int j = bucket[i][d];
		B[C[j] - 1][d] = j;
		for(int k = 0; k < 4; k++)
			if(k != d)
				B[C[j] - 1][k] = bucket[i][k];
		C[j] --;
	}
	for(int i = 0; i < n; i++)
		for(int j = 0; j < 4; j++)
			bucket[i][j] = B[i][j];
}
void radix_sort(){
	for(int i = 0; i < 4; i++){
		counting_sort(i);
	//	cout<<i<<'\n';
	}
}
int main(){
	freopen("radixsort.in","r",stdin);
	freopen("radixsort.out","w",stdout);
	scanf("%d%d%d%d",&n,&a,&b,&c);
	create_buckets();
	radix_sort();

	for(int i = 0; i < n; i += 10){
		int nr = bucket[i][3] * 1000000000 + bucket[i][2] * 1000000 + bucket[i][1] * 1000 + bucket[i][0];
		printf("%d ",nr);
	}
	return 0;
}