Cod sursa(job #1699086)

Utilizator mihai995mihai995 mihai995 Data 6 mai 2016 01:33:52
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <iostream>
#include <cstdlib>
#include <cstring>
using namespace std;

const int N = 1e7, B = 16, mask = (1 << B) - 1;
int v[N], n;

void radix(int* v, int n){
	int aux[n], cnt[1 << B], lim = 0;
	for (int i = 0; i != n; i++)
		lim |= v[i];
	lim = 32 - __builtin_clz(lim);

	for (int shr = 0; shr < lim; shr += B){
		memset( cnt, 0, sizeof(cnt) );
		for (int i = 0; i != n; i++)
			cnt[ v[i] >> shr & mask ]++;
		for (int i = 0, a = 0; i <= mask; i++)
			a = cnt[i] + (cnt[i] = a);
		for (int i = 0; i != n; i++)
			aux[ cnt[ v[i] >> shr & mask ]++ ] = v[i];
		memcpy(v, aux, sizeof(aux));
	}
}

void generate(){
	long a, b, c, x = 0;
	cin >> n >> a >> b >> c;
	for (int i = 0; i != n; i++)
		v[i] = x = (a * x + b) % c;
}

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

	generate();
	radix(v, n);
	for (int i = 0; i != n; i += 10)
		cout << v[i] << ' ';
	cout << '\n';

	return 0;
}