Cod sursa(job #2832494)

Utilizator guzgandemunteIonescu Laura guzgandemunte Data 13 ianuarie 2022 20:27:45
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <iostream>
#include <cstring>
#include <fstream>
#define NMAX 10000000
#define BASE (1 << 8)

using namespace std;
using ll = long long;

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

int n, a, b, c;
int arr[NMAX], out[NMAX];
int freq[BASE];

void generateArray() {
    arr[0] = b;
    for (int i = 1; i < n; ++i) arr[i] = (1LL * a * arr[i - 1] + b) % c;
}

int main()
{
    fin >> n >> a >> b >> c;
    generateArray();

    for (int digits = 0; digits < 32; digits += 8) {
        memset(freq, 0, sizeof(freq));
        for (int i = 0; i < n; ++i) ++freq[(arr[i] >> digits) & (BASE - 1)];
        for (int i = 1; i < BASE; ++i) freq[i] += freq[i - 1];
        for (int i = n - 1; i >= 0; --i) out[freq[(arr[i] >> digits) & (BASE - 1)]-- - 1] = arr[i];
        for (int i = 0; i < n; ++i) arr[i] = out[i];
    }
    /*for (int digit = 1; digit <= k; ++digit) {
        memset(freq, 0, sizeof(freq));
        for (int i = 0; i < n; ++i) ++freq[(arr[i] / power) % 10];
        for (int i = 1; i <= 10; ++i) freq[i] += freq[i - 1];
        for (int i = n - 1; i >= 0; --i) {
            out[freq[(arr[i] / power) % 10] - 1] = arr[i];
            --freq[(arr[i] / power) % 10];
        }
        for (int i = 0; i < n; ++i) arr[i] = out[i];
        power *= 10;
    }*/

    for  (int i = 0; i < n; i += 10) fout << arr[i] << " ";

    fin.close();
    fout.close();
    return 0;
}