Cod sursa(job #1480693)

Utilizator pas.andreiPopovici Andrei-Sorin pas.andrei Data 3 septembrie 2015 00:56:21
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <cctype>
#include <set>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <vector>
#include <list>
#include <bitset>
#include <iomanip>
#define MAX 5000001LL
#define FASTIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

using namespace std;


vector<int> v, List[10];

int main() {
	//FASTIO
	int n, a, b, c, i, p10, j,nr;

	FILE *fin = fopen("radixsort.in", "r");
	FILE *fout = fopen("radixsort.out", "w");

	fscanf(fin, "%d%d%d%d", &n, &a, &b, &c);
	v.resize(n);

	v[0] = b;
	for (i = 1; i < n; ++i)
		v[i] = (v[i - 1] * a + b) % c;

	p10 = 1;
	for (c = 1; c < 10; ++c) {
		for (i = 0; i < n; ++i) {
			List[(v[i] / p10) % 10].push_back(v[i]);
			//v.pop_back();
		}

		nr = 0;
		for (i = 0; i < 10; ++i) {
			for (j = 0; j < List[i].size(); ++j) {
				v[nr] = List[i][j];
				++nr;
			}

			List[i].clear();
		}

		p10 *= 10;
	}

	for (i = 0; i < n; i += 10)
		fprintf(fout, "%d ", v[i]);

	return 0;
}