Cod sursa(job #3332399)

Utilizator rares89_Dumitriu Rares rares89_ Data 6 ianuarie 2026 15:43:22
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 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() {
    for(int shift = 0; shift < 32; shift += 8) {
        int count[256] = {0};

        for(int i = 1; i <= n; ++i) {
            count[(v[i] >> shift) & 255]++;
        }

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

        for(int i = n; i >= 1; --i) {
            int bucket = (v[i] >> shift) & 255;
            aux[count[bucket]] = v[i];
            count[bucket]--;
        }

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

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

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