Cod sursa(job #1251415)

Utilizator vlad2901Vlad Berindei vlad2901 Data 29 octombrie 2014 14:08:09
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <vector>
#include <queue>
#include <iostream>

#define NMAX 10000000

using namespace std;

ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
int v[NMAX];
queue<int> bucket1[256];
queue<int> bucket2[256];

int main() {
	int a, b, c, n;
	fin >> n >> a >> b >> c;
	v[0] = b;
	for (int i = 1; i < n; ++i) {
		v[i] = (a * v[i - 1] + b) % c;
	}
	for (int i = 0; i < n; ++i) {
		bucket1[v[i] & 0x000000ff].push(v[i]);
	}
	int val;
	for (int b = 0; b < 256; ++b) {
		while (!bucket1[b].empty()) {
			val = bucket1[b].front();
			bucket1[b].pop();
			bucket2[(val & 0x0000ff00) >> 2].push(val);
		}

	}
	for (int b = 0; b < 256; ++b) {
		while (!bucket2[b].empty()) {
			val = bucket2[b].front();
			bucket2[b].pop();
			bucket1[(val & 0x00ff0000) >> 4].push(val);
		}
	}
	for (int b = 0; b < 256; ++b) {
		while (!bucket1[b].empty()) {
			val = bucket1[b].front();
			bucket1[b].pop();
			bucket2[(val & 0xff000000) >> 6].push(val);
		}
	}
	int count = 0;
	for (int b = 0; b < 256; ++b) {
		while (!bucket2[b].empty()) {
			if (count % 10 == 0) {
				fout << bucket2[b].front() << " ";
			}
			bucket2[b].pop(); 
			++count;
		}
	}
	return 0;
}