Cod sursa(job #1227949)

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

unsigned int n,a,b,c,C[10001];
unsigned short int bucket[10000001][3];
unsigned short int B[10000001][3];
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;*/
	bucket[k][0] = nr % 10000;
	bucket[k][1] = (nr % 100000000 - bucket[k][0]) / 10000;
	bucket[k][2] = (nr - bucket[k][1] * 10000 - bucket[k][0]) / 100000000;
}
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){

	for(int i = 0; i < 10000; i++)
		C[i] = 0;
	for(int i = 0; i < n; i++)
		C[bucket[i][d]]++;
	for(int i = 1; i < 10000; 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 < 3; 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 < 3; 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();
	int i,nr;
	for(i = 0; i < 3; i++)
		counting_sort(i);
	
	
	for(i = 0; i < n; i += 10){
		nr = bucket[i][2] * 100000000 + bucket[i][1] * 10000 + bucket[i][0];
		//nr = bucket[i][3] * 1000000000 + bucket[i][2] * 1000000 + bucket[i][1] * 1000 + bucket[i][0];
		printf("%d ",nr);
	}
	return 0;
}