Cod sursa(job #3299290)

Utilizator rapidu36Victor Manz rapidu36 Data 5 iunie 2025 11:21:51
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <vector>

using namespace std;

const int LIM_10 = 1e9;
const int B = 100;

int main()
{
    ifstream in("radixsort.in");
    ofstream out("radixsort.out");
    int n, a, b, c;
    in >> n >> a >> b >> c;
    vector <int> v(n);
    vector <int> aux(n);
    v[0] = b;
    for (int i = 1; i < n; i++)
    {
        v[i] = ((long long)a * v[i-1] + b) % c;
    }
    vector <int> nr(B, 0);
    vector <int> ultim(B);
    long long p = 1;
    while (nr[0] < n)
    {
        fill(nr.begin(), nr.end(), 0);
        for (int i = 0; i < n; i++)
        {
            int cif = v[i] / p % B;
            nr[cif]++;
        }
        ultim[0] = 0;
        for (int cif = 1; cif < B; cif++)
        {
            ultim[cif] = ultim[cif-1] + nr[cif-1];
        }
        for (int i = 0; i < n; i++)
        {
            int cif = v[i] / p % B;
            aux[ultim[cif]++] = v[i];
        }
        for (int i = 0; i < n; i++)
        {
            v[i] = aux[i];
        }
        p *= B;
    }
    int poz = 0;
    while (poz < n)
    {
        out << v[poz] << " ";
        poz += 10;;
    }
    in.close();
    out.close();
    return 0;
}