Cod sursa(job #2539083)

Utilizator marius004scarlat marius marius004 Data 5 februarie 2020 16:42:23
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>

std::ifstream f("radixsort.in");
std::ofstream g("radixsort.out");

const int NMAX = 10000005;
int N,A,B,C,p,v[NMAX],fr[256],w[NMAX];

int digit(int n,int p){
    return ((n >> p) & 255);
}

int main(){
    
    f >> N >> A >> B >> C;
    
    v[1] = B;
    
    for(int i = 2;i <= N;++i)
        v[i] = (A * v[i - 1] + B) % C;
    
    p = 0;
    for(int t = 1;t <= 4;++t){
        
        for(int i = 0;i <= 255;++i)
            fr[i] = 0;
        
        for(int i = 1;i <= N;++i)
            fr[digit(v[i],p)]++;
        
        for(int i = 1;i <= 255;++i)
            fr[i] += fr[i - 1];
        
        for(int i = N;i >= 1;--i)
            w[ fr[digit(v[i],p)]-- ] = v[i];
        
        for(int i = 1;i <= N;++i)
            v[i] = w[i];
        p += 8;
    }
    
    for(int i = 1;i <= N;i += 10)
        g << v[i] << ' ';
    
    return 0;
}