Cod sursa(job #2960747)

Utilizator alexandru_ioan.06Alexandru Ioan alexandru_ioan.06 Data 4 ianuarie 2023 21:56:26
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;
ifstream cin ("radixsort.in");
ofstream cout ("radixsort.out");

vector<long long> v;

int NrCif(long long num)
{
	int c = 0;
	while(num)
		{
			c++;
			num /= 10;
		}
	return c;
}

void RadixSort()
{
	queue<long long> q[10];
	long long maxi = 0;
	for(int i = 0 ; i < v.size() ; ++i)
		maxi = max(maxi , v[i]);
	int n = NrCif(maxi) + 1;
	int p = 1;
	for(int i = 1 ; i <= n ; ++i)
		{
			vector<long long> :: iterator it;
			for(it = v.begin() ; it != v.end() ; ++it)
				{
					int cif = (*it / p) % 10;
					q[cif].push(*it);
				}
			p *= 10;
			int m = 0;
			for(int j = 0 ; j <= 9 ; ++j)
				while(!q[j].empty())
					{
						v[m++] = q[j].front();
						q[j].pop();
					}
		}
}

int main()
{
	int n , a , b , c;
	cin >> n >> a >> b >> c;
	long long val = b;
	v.push_back(b);
	for(int i = 2 ; i <= n ; ++i)
		{
			long long val1 = (a * val + b) % c;
				v.push_back(val1);
			val = val1;
		}
	RadixSort();
	for(int i = 0 ; i < v.size() ; i += 10)
		cout << v[i] <<' ';
}