Cod sursa(job #3357919)

Utilizator TestLicenta123Test Test TestLicenta123 Data 13 iunie 2026 21:48:44
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>

using namespace std;

ifstream cin ("radixsort.in");
ofstream cout ("radixsort.out");

int v[100001];
int aux[100001];
int fv[256];

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, a, b, c;
    cin >> n >> a >> b >> c;

    v[0] = 0;
    for (int i = 1; i <= n; i++) {
        long long nr = 1LL * v[i - 1];
        nr *= 1LL * a;
        nr += 1LL * b;
        nr %= 1LL * c;
        v[i] = (int)nr;
    }

    for (int bit = 0; bit < 32; bit += 8) {

        for (int i = 0; i < 256; i++) {
            fv[i] = 0;
        }

        for (int i = 0; i <= n; i++) {
            long long nr = v[i] >> bit;
            nr &= 255LL;
            fv[nr]++;
        }

        for (int i = 1; i < 256; i++) {
            fv[i] += fv[i - 1];
        }

        for (int i = n; i >= 0; i--) {
            long long nr = v[i] >> bit;
            nr &= 255LL;
            aux[fv[nr] - 1] = v[i];
            fv[nr]--;
        }

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

    for (int i = 1; i <= n; i += 10) {
        cout << v[i] << " ";
    }

    return 0;
}