Cod sursa(job #3291550)

Utilizator Ruxandra009Ruxandra Vasilescu Ruxandra009 Data 5 aprilie 2025 09:03:55
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <fstream>
#include <vector>

using namespace std;

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

int n, a, b, c, nrcif;
vector<int> v, cif[10];

void clean(){
    for(int i = 0; i < 10; i ++)
        cif[i].clear();
}

void radsort()
{
    vector<int> aux;

    for(int i = 1, p = 1; i <= nrcif; i ++, p *= 10)
    {
        clean(); aux.clear();
        for(auto x : v)
        {
            int c = (x / p) % 10;
            cif[c].push_back(x);
        }

        for(int i = 0; i < 10; i ++)
            for(auto x : cif[i])
                aux.push_back(x);

        v = aux;
    }
}

int main()
{
    f >> n >> a >> b >> c;
    v.push_back(b);
    for(int i = 1; i < n; i ++)
    {
        int x = (a * v.back() + b) % c;
        v.push_back(x);

        int nr = 0;
        while(x)
            x /= 10, nr ++;

        nrcif = max(nrcif, nr);
    }

    radsort();

    for(int i = 0; i < n; i += 10)
        g << v[i] << " ";
    return 0;
}