Cod sursa(job #2900756)

Utilizator AlexPascu007Pascu Ionut Alexandru AlexPascu007 Data 12 mai 2022 09:03:55
Problema Radix Sort Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>

using namespace std;

const int DIM = 10000010;

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

int n, a, b, c, p, i, t;
int v[DIM], aux[DIM], f[300];

int cifra(int x, int p) {
    return (x >> p) & 255;
}

int main() {
    fin >> n >> a >> b >> c;
    v[1] = b;
    for (i = 2; i <= n; i++)
        v[i] = (1LL * a * v[i - 1] + b) % c;
    for (t = 1; t <= 4; t++) {
        for (i = 0; i < 256; i++)
            f[i] = 0;
        for (i = 1; i <= n; i++)
            f[cifra(v[i], p)]++;
        for (i = 1; i < 256; i++)
            f[i] += f[i - 1];
        for (i = n; i; i--)
            aux[f[cifra(v[i], p)]--] = v[i];
        for (i = 1; i <= n; i++)
            v[i] = aux[i];
        p += 8;
    }
    for (i = 1; i <= n; i += 10)
        fout<<v[i]<<" ";
    return 0;
}