Cod sursa(job #2343029)

Utilizator flibiaVisanu Cristian flibia Data 13 februarie 2019 17:12:25
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#pragma GCC optimize("03")
#include <bits/stdc++.h>
#define ui unsigned int

using namespace std;

ifstream in("radixsort.in");
ofstream out("radixsort.out");

int n;
ui a, b, c, v[10000100], tp, idx[256], counter[256], aux[10000010];
vector <ui> w[256];

int main() {
	in >> n >> a >> b >> c;
	v[1] = b;
	for (int i = 2; i <= n; i++)
		v[i] = (a * v[i - 1] + b) % c;
	for (int os = 0; os < 4; os++) {
		memset(idx, 0, sizeof idx);
		memset(counter, 0, sizeof counter);
		for (int i = 1; i <= n; i++)
			counter[(v[i] >> (8 * os)) & 255]++;
		idx[0] = 0;
		for (int i = 1; i < 256; i++)
			idx[i] = idx[i - 1] + counter[i - 1];	
		for (int i = 1; i <= n; i++)
			aux[++idx[(v[i] >> (8 * os)) & 255]] = v[i];
		memcpy(v, aux, sizeof(v));
	}
	for (int i = 1; i <= n; i += 10)
		out << v[i] << ' ';
	return 0;
}