Cod sursa(job #1426667)

Utilizator gabi.cristacheGabi Cristache gabi.cristache Data 30 aprilie 2015 10:30:49
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <fstream>
#include <queue>
#include <algorithm>

#define MaxN 10000005

using namespace std;

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

int N, A, B, C, v[MaxN];
queue<int> q[10];

int main() {
	fin >> N >> A >> B >> C;

	v[1] = B;
	for (int i = 2; i <= N; ++i)
		v[i] = (A * v[i - 1] + B) % C;

	int finished = false;
	int d = 1;
	while (!finished) {
		finished = true;

		for (int i = 1; i <= N; ++i) {
			int divisor = v[i] / d;
			q[divisor % 10].push(v[i]);

			if (divisor > 0)
				finished = false;
		}

		int k = 0;
		for (int i = 0; i <= 9; ++i) {
			while (!q[i].empty()) {
				v[++k] = q[i].front();
				q[i].pop();
			}
		}
		d *= 10;
	}

	for (int i = 1; i <= N; i += 10) {
		fout << v[i] << ' ';
	}

	return 0;
}