Cod sursa(job #2966248)

Utilizator RobertlelRobert Robertlel Data 16 ianuarie 2023 21:58:31
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.82 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;


ifstream f ("radixsort.in");
ofstream g ("radixsort.out");

vector < int > v;
vector < int > :: iterator it;


int n , a , b , c;
long long val , val1;



void Radix_Sort()
{
    queue < int > coada[20];
    int maxi = 0;
    for (int i = 0 ; i < v.size () ; ++i)
        maxi = max (maxi , v[i]);
        int n = 0;
    while (maxi)
        n++ , maxi /= 10;
        int div  = 1;
    for (int i = 1 ; i <= n ; ++i)
    {
        vector<int> :: iterator it;
        for (it = v.begin() ; it != v.end() ; ++it)
        {
            int cif = (*it / div) % 10;
            coada[cif].push(*it);
        }
        div *= 10;
        int k = 0;

        for (int j = 0 ; j <= 9 ; ++j)
            while (!coada[j].empty())
            {
                v[k++] = coada[j].front ();
                coada[j].pop ();
            }
    }

}

void RadixSort()
{
	queue<int> q[20];
	int maxi = 0;
	for(int i = 0 ; i < v.size() ; ++i)
		maxi = max(maxi , v[i]);
		int n = 0;
		while (maxi)
        n++ , maxi /= 10;
	int p = 1;
	for(int i = 1 ; i <= n ; ++i)
		{
			vector<int> :: 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()
{
    f >> n >> a >> b >> c;
    v.push_back(b);
    val = b;
    for (int i = 2 ; i <= n ; i++)
    {
        val1 = (1LL * a * val + b) % c;
        v.push_back(val1);
        val = val1;
    }
     Radix_Sort ();

    for (it = v.begin() ; it != v.end() ; it++)
          g << *it <<" ";
    return 0;
}