Cod sursa(job #1457151)

Utilizator al.mocanuAlexandru Mocanu al.mocanu Data 2 iulie 2015 19:56:28
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <stdio.h>
#define MAX 10000005
#define MASK (1 << 8) - 1

int n, a, b, c, v[MAX], aux[MAX], i, move, x[MASK + 5];

int radix();

int main(){
	freopen("radixsort.in", "r", stdin);
	freopen("radixsort.out", "w", stdout);
	scanf("%d%d%d%d", &n, &a, &b, &c);
	v[1] = b;
	for(i = 2; i <= n; i++)
		v[i] = (1LL * a * v[i - 1] + b) % c;

	radix();
	for(i = 1; i <= n; i += 10)
		printf("%d ", v[i]);
	printf("\n");

	return 0;
}

int radix(){
	for(move = 0; move < 32; move += 8){
		for(i = 1; i <= n; i++)
			x[(v[i] >> move) & MASK]++;

		for(i = 1; i <= MASK; i++)
			x[i] += x[i - 1];
		for(i = MASK; i; i--)
			x[i] = x[i - 1];
		x[0] = 0;

		for(i = 1; i <= n; i++)
			aux[++x[(v[i] >> move) & MASK]] = v[i];
		for(i = 1; i <= n; i++)
			v[i] = aux[i];
	
		for(i = 1; i <= MASK; i++)
			x[i] = 0;
	}
}