Cod sursa(job #2609716)

Utilizator smitoiStefan Mitoi smitoi Data 3 mai 2020 11:48:38
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 kb
#include <iostream>
#include <vector>
#include <bits/stdc++.h>
#include <algorithm>
#include <fstream>

using namespace std;

int		maxim(vector<long long int>& array)
{
	int		maxim = 0;
	
	for (size_t index = 0; index < array.size(); ++index)
		if (array[maxim] < array[index])
			maxim = index;
	
	return array[maxim];
}

vector<long long int>	counting_sort(vector<long long int>&	array, int		baza, int		exponent)
{
	vector<long long int>	count(baza, 0);
	vector<long long int> 	rez(array.size(), 0);
	int		aux = 0;
	
	for(size_t index = 0; index < array.size(); ++index)
	{
		aux = array[index] / exponent % baza;
		count[aux] += 1;
	}
	
	for(size_t index = 1; index < count.size(); ++index)
		count[index] += count[index - 1];

	for(int index = array.size() - 1; index > -1; --index)
	{
		aux = array[index] / exponent % baza;
		count[aux] -= 1;
		rez[count[aux]] = array[index];
	}
	
	return rez;
}

vector<long long int>	radix_sort(vector<long long int>& array, int	baza)
{
	int		elMax = maxim(array);
	for (int	exponent = 1; elMax / exponent > 0; exponent *= baza)
		array = counting_sort(array, baza, exponent);

	return array;
}

long long int a, b, c, n; vector<long long int> v;
ifstream f("radixsort.in");
ofstream g("radixsort.out");

int	main()
{
	ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
	
	
	f >> n >> a >> b >> c;
	v.push_back(b);
	
	//  v[i] = (A * v[i-1] + B) % C, pentru 2 ≤ i ≤ N 
	for (long long int i = 1; i < n; i++)
		v.push_back((a * v[i - 1] + b) % c);
	
	v = radix_sort(v, 256);

	for (long long int i = 0; i < n; i += 10)
		g << v[i] << ' ';

	
	return	0;
}