Cod sursa(job #1092517)

Utilizator narcis_vsGemene Narcis - Gabriel narcis_vs Data 27 ianuarie 2014 10:16:35
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <fstream>

using namespace std ;
const int MASK = 65535;
const int Nmax = 10000002;
int A , B , C , N, v[Nmax] , sol [Nmax] , aux1[Nmax] , aux2[Nmax];
inline void Read(){
    ifstream f("radixsort.in");
    f >> N >> A >> B >> C;
    f.close();
}

inline void Build(){
    v[1] = B;
    for(int i = 2;i <= N; ++i)
        v[i] = (1LL*A*v[i-1] + B) % C;
}

inline void RadixSort(){
    int cnt[MASK+1], i;
    for(int shift = 0; shift <= 16; shift += 16){
        for(i = 0 ;i <= MASK ; ++i)
            cnt[i] = 0;
        for(i = 1 ;i <= N ;++i){
            aux1[i] = (v[i]>>shift)&MASK;
            ++cnt[aux1[i]];
        }
        for(i = 1;i <= MASK; ++i)
            cnt[i] += cnt[i-1];
        for(i = N; i ;--i)
            aux2[cnt[aux1[i]]--] = v[i];
        for(i = 1;i <= N; ++i)
            v[i] = aux2[i];
    }
}

inline void Write(){
    ofstream g("radixsort.out");
    for(int i = 1; i <= N;i += 10)
        g<<v[i]<<" ";
    g<<"\n";
    g.close();
}

int main(){
    Read();
    Build();
    RadixSort();
    Write();
    return 0;
}