Cod sursa(job #1174927)

Utilizator veleanduAlex Velea veleandu Data 24 aprilie 2014 10:53:01
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <cstdio>
#include <fstream>
#include <iostream>
using namespace std;

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

const int kMaxN = 10000005;

int n;
int ap[1 << 16];

int aux[kMaxN], el[kMaxN];

void solve(int p) {
	int mask = (1 << 16) - 1;
 	
    for (int i = 0; i <= mask; ++i)
		ap[i] = 0;

	for (int i = 1; i <= n; ++i)
		ap[(el[i] & (mask << p)) >> p]++;
	
	for (int i = 1; i <= mask; ++i)
		ap[i] += ap[i - 1];
	for (int i = mask; i > 0; --i) {
		ap[i] = ap[i - 1];
	}
	ap[0] = 0;

	for (int i = 1; i <= n; ++i)
		aux[++ap[(el[i] & (mask << p)) >> p]] = el[i];
	for (int i = 1; i <= n; ++i)
		el[i] = aux[i];
}

int main() {

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

 	int a, b, c;
	scanf("%d %d %d %d", &n, &a, &b, &c);
	el[1] = b;
	for (int i = 2; i <= n; ++i)
		el[i] = (1LL * a * el[i - 1] + b) % c;

 	solve(0);   
	solve(16);

	for (int i = 1; i <= n; i += 10)
		printf("%d ", el[i]);
	return 0;
}