Cod sursa(job #1699095)

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

const int N = 1e7, B = 1 << 16;
int v[N], aux[N], n;

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

	for (int k = 0; k < 2; k++){
		memset( cnt, 0, sizeof(cnt) );
		for (int i = 0; i != n; i++)
			cnt[ (short*)(v + i)[k] ]++;
		for (int i = 0, a = 0; i != B; i++)
			a += cnt[i], cnt[i] = a - cnt[i];
		for (int i = 0; i != n; i++)
			aux[ cnt[ (short*)(v + i)[k] ]++ ] = v[i];
		memcpy( v, aux, n * sizeof(*v) );
	}
}

void generate(){
	long 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;
}