Cod sursa(job #2539109)

Utilizator marius004scarlat marius marius004 Data 5 februarie 2020 17:20:26
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
 
std::ifstream f("radixsort.in");
std::ofstream g("radixsort.out");
 
const int NMAX = 10000005;
int N,A,B,C,v[NMAX],fr[256],w[NMAX];
 
inline int digit(int n,long long p){
    return ((n >> p) & 255);
}
 
int main(){
    
    f >> N >> A >> B >> C;
    
    v[1] = B;
    
    for(int i = 2;i <= N;++i)
        v[i] = (1LL * A * 1LL * v[i - 1] + 1LL * B) % C;
    
    long long 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;
}