Cod sursa(job #1363438)

Utilizator cristian.enciuCristian Enciu cristian.enciu Data 26 februarie 2015 23:03:48
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include<stdio.h>
#include<string.h>

int n, a, b, c, z;
int v[10000010];
int v1[10000010];

inline int extract(int x)
{
	return ((x >> (z * 8)) & 0xFF);
}

void mysort(int x[], int y[])
{
	int counter[1 << 8];
	int index[1 << 8];

	memset(counter, 0, sizeof(counter));

	for(int i = 0 ; i < n ; ++i) {
		++counter[extract(x[i])];
	}

	index[0] = 0;
	for(int i = 1 ; i < (1 << 8) ; ++i) {
		index[i] = index[i-1] + counter[i-1];
	}

	for(int i = 0 ; i < n ; ++i) {
		y[index[extract(x[i])]++] = x[i];
	}
}

int main()
{
	freopen("radixsort.in", "r", stdin);
	freopen("radixsort.out", "w", stdout);

	scanf("%d%d%d%d", &n, &a, &b, &c);

	v[0] = b;
	for(int i = 1 ; i < n ; ++i)
		v[i] = ((1LL * a * v[i-1]) % c + b) % c;

	int size = sizeof(int);
	for(z = 0 ; z < size ; ++z) {
		mysort(v, v1);
		++z;
		mysort(v1, v);
	}

	for(int i = 0 ; i < n ; i += 10)
		printf("%d ", v[i]);

	return 0;
}