Cod sursa(job #1699098)

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

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

typedef unsigned char bkt_t;
void radix(int* st, int* dr){
	int cnt[256];
	for (int k = 0; k < 4; k++){
		memset( cnt, 0, sizeof(cnt) );
		bkt_t* v_lim = (bkt_t*)dr + k;
		for (bkt_t* v = (bkt_t*)st + k; v != v_lim; v += 4)
			cnt[*v]++;
		for (int i = 0, a = 0; i != 256; i++)
			a += cnt[i], cnt[i] = a - cnt[i];
		int* p = st;
		for (bkt_t* v = (bkt_t*)st + k; p != dr; p++, v += 4)
			aux[ cnt[*v]++ ] = *p;
		memcpy( v, aux, (dr - st) * sizeof(*st) );
	}
}

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, v + n);
	for (int i = 0; i < n; i += 10)
		cout << v[i] << ' ';
	cout << '\n';

	return 0;
}