Cod sursa(job #2355495)

Utilizator EdythestarGhiriti Edmond Edythestar Data 26 februarie 2019 09:24:53
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

vector<int> a;
int n;

void readgen(){
	int A, B, C;
	fin >> n >> A >> B >> C;
	a.resize(n);
	a[0] = B;
	for (int i = 1; i < n; i++)
		a[i] = (A*a[i - 1] + B) % C;
}

int getMax(){
	int mx = -1;
	for (int i = 0; i < n;i++)
	if (mx < a[i]) mx = a[i];
	return mx;
}

void rsort(int htv){
	vector<int> count(10, 0);
	vector<int> masol(n, 0);
	for (int i = 0; i < n; i++)
		count[(a[i] / htv) % 10]++; 
	
	for (int i = 1; i < 10; i++)
		count[i] += count[i - 1];

	for (int i = n-1; i>=0; i--){
		count[(a[i] / htv) % 10]--;
		masol[count[(a[i] / htv) % 10]] = a[i];
	}
	for (int i = 0; i < n; i++)
		a[i] = masol[i];
}

void solve(){
	int m=getMax();
	for (int htv = 1; m / htv > 0; htv *= 10)
		rsort(htv);
}

void write(){
	int i = 0;
	while (i < n){
		fout << a[i] << " ";
		i = i + 10;
	}
}

int main(){
	readgen();
	solve();
	write();
	
}