Cod sursa(job #2672585)

Utilizator Gheorghita_VladGheorghita Vlad Gheorghita_Vlad Data 14 noiembrie 2020 11:20:14
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#include <queue>
#include <vector>
#include <math.h>
using namespace std;
ifstream f("radixsort.in");
ofstream g("radixsort.out");
int n,a,b,c;
vector <int> v;
int countDigits(unsigned int n)
{
    return (int) (1 + log10((double) n));
}
int getMaxValue(vector<int> &v)
{
    int result = -1;
    vector<int>::iterator it;
    for (it = v.begin(); it != v.end(); it++)
    {
        result = max( result, *it );
    }
    return result;
}
void radixSort( vector<int> &v)
{
    queue<int> Q[10];
    int steps = countDigits ( getMaxValue(v) );
    int power = 1;
    for (int k = 1; k <= steps; k++)
    {
        for ( vector<int>::iterator it = v.begin(); it != v.end(); ++it)
        {
            int i = (*it / power) % 10;
            Q[i].push(*it);
        }
        power *= 10;
        int n;
        n = 0;
        for (int i = 0; i <= 9; i++)
        {
            while (!Q[i].empty())
            {
                v[n++] = Q[i].front();
                Q[i].pop();
            }
        }
    }
}
int main()
{
    f>>n>>a>>b>>c;
    v.push_back(b);
    for (int i=1; i<n; i++)
        v.push_back((1LL*a*v[i-1]+b)%c);
    radixSort(v);
    for (int i=0; i<n; i+=10)
        g<<v[i]<<" ";
    return 0;
}