Cod sursa(job #2897374)

Utilizator radugheoRadu Mihai Gheorghe radugheo Data 3 mai 2022 15:52:19
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>

using namespace std;

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

int a, b, c, n, i, p, cif, t;
int v[10000005], aux[10000005];
int f[256];

int takeCifra(int a, int b){
    return ((a>>b)&255);
}

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