Cod sursa(job #1996120)

Utilizator AdrianaMAdriana Moisil AdrianaM Data 30 iunie 2017 11:15:23
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

typedef vector<unsigned int> VI;
typedef queue<unsigned int> QI;

int n;
unsigned int A, B, C;
unsigned int v[10000001];

int main()
{
	ifstream is("radixsort.in");
	is >> n >> A >> B >> C;
	is.close(); 
	
	v[1] = B;
	for (int i = 2; i <= n; ++i)
		v[i] = (A * v[i - 1] % C + B) % C;

	QI b[256];
	for (unsigned int key = 0; 1 << key <= C; key += 8)
	{
		for (int i = 1; i <= n; ++i)
			b[(v[i] >> key) & 255].push(v[i]);
		int cnt = 1;
		for (int i = 0; i <= 255; ++i)
			while (!b[i].empty())
			{
				v[cnt++] = b[i].front();
				b[i].pop();
			}
	}

	ofstream os("radixsort.out");
	for (int i = 1; i <= n; i += 10)
		os << v[i] << " ";
	os.close();
	return 0;
}