Cod sursa(job #2491857)

Utilizator maria15Maria Dinca maria15 Data 13 noiembrie 2019 13:02:28
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <fstream>
#include <bitset>
#include <cstring>

using namespace std;

ifstream fin("radixsort.in");

int n, i, j, sol[10000001], v[10000001], nrcifre, maxim, x, nr, cif, b, c, divi;
long long a;

int main(){
    freopen("radixsort.out", "w", stdout);
    fin>>n>>a>>b>>c;
    v[1] = maxim = b;
    int f[257];
    for(i=2;i<=n;++i){
        v[i] = (a*v[i-1] + b)%c;
    }
    for(j=1, divi = 0;j<=4;++j, divi += 8){
        memset(f, 0, sizeof f);
        for(i=1;i<=n;++i){
            ++f[((v[i]>>divi)&255)];
        }
        for(i=1;i<256;++i)
            f[i] += f[i-1];
        for(i=n;i>0;i--){
            sol[f[((v[i]>>divi)&255)]--] = v[i];
        }
        memcpy(v, sol, (n+1) << 2);
    }
    for(i=1;i<=n;i+=10)
        printf("%d ", sol[i]);
    return 0;
}