Cod sursa(job #2930942)

Utilizator TudosieRazvanTudosie Marius-Razvan TudosieRazvan Data 29 octombrie 2022 21:28:03
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.82 kb
#include <cstdio>
#include <climits>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <bitset>
#include <map>
#include <cstring>
#include <algorithm>
#define NMAX 2003
#define MOD 1000000007
using namespace std;

int n,a,b,c;
queue<long long int> bucket[10];

FILE* fin, * fout;



int main()
{
	fin = fopen("radixsort.in", "r");
	fout = fopen("radixsort.out", "w");


	fscanf(fin, "%d %d %d %d", &n, &a, &b, &c);
	long long int prec = b;
	bucket[prec % 10].push(prec);
	for (int i = 2; i <= n; i++)
	{
		long long int x = ((long long int)a * prec + b)%c;
		bucket[x % 10].push(x);
		prec = x;
	}

	//fac un counting sort pe astea
	//Practic fac mereu o sortare dupa cifra de pe pozitia x/p 
	//Si pun sortarile astea un bucket-uri
	//Dar e important cand imi refac vectorul sa imi scot elementele
	//in aceeasi ordine in care le-am bagat
	//Pentru ca asa se pastreaza sortate in bucket
	long long int p = 10;
	while (1)
	{
		//imi refac vectorul initial 
		vector<long long int>sortat;
		for (int i = 0; i <= 9; i++)
		{
			while (!bucket[i].empty())
			{
				sortat.push_back(bucket[i].front());
				bucket[i].pop();
			}
		}
		//acuma sortez frumos dupa urmatoarea cifra semnificativa
		bool amMaiMare = false;
		for (int i = 0; i < sortat.size(); i++)
		{
			int poz = (sortat[i] / p) % 10;
			if (sortat[i] > p)
			{
				amMaiMare = true;
			}
			bucket[poz].push(sortat[i]);
		}
		if (!amMaiMare)
		{
			//am terminat, ma opresc
			break;
		}
		p = p * 10;
	}

	vector<long long int>sortat;
	for (int i = 0; i <= 9; i++)
	{
		while (!bucket[i].empty())
		{
			sortat.push_back(bucket[i].front());
			bucket[i].pop();
		}
	}
	for (int i = 0; i < sortat.size(); i += 10)
	{
		fprintf(fout, "%d ", sortat[i]);
	}
	return 0;
}