Cod sursa(job #3332398)

Utilizator rares89_Dumitriu Rares rares89_ Data 6 ianuarie 2026 15:38:38
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <fstream>

using namespace std;

ifstream fin("radixsort.in");
ofstream fout("radixsort.out");

const int NMAX = 10000005;
int n, A, B, C;
int v[NMAX];
int aux[NMAX];

void RadixSort() {
    int max_val = v[0];
    for(int i = 1; i < n; ++i) {
        max_val = max(max_val, v[i]);
    }

    for(int exp = 1; max_val / exp > 0; exp *= 10) {
        int count[10] = {0};

        for(int i = 0; i < n; ++i) {
            count[(v[i] / exp) % 10]++;
        }

        for(int i = 1; i < 10; ++i) {
            count[i] += count[i - 1];
        }

        for(int i = n - 1; i >= 0; --i) {
            int digit = (v[i] / exp) % 10;
            aux[count[digit] - 1] = v[i];
            count[digit]--;
        }

        for(int i = 0; i < n; ++i) {
            v[i] = aux[i];
        }
    }
}

int main() {
    fin >> n >> A >> B >> C;
    fin.close();
    v[0] = B;
    for(int i = 1; i < n; ++i) {
        v[i] = (1LL * A * v[i - 1] + B) % C;
    }

    RadixSort();
    for(int i = 0; i < n; i += 10) {
        fout << v[i] << " ";
    }

    return 0;
}