Cod sursa(job #2205691)

Utilizator Raoul_16Raoul Bocancea Raoul_16 Data 19 mai 2018 22:04:03
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <bits/stdc++.h>
using namespace std;
const int MAX = 10000005;
const int bits = 8 , size = 1 << bits , mask = size - 1;
int N,A,B,C;
int v[MAX],aux[MAX];
void read();
void print();
int getMask(int,int);
void countSort(int[],int[],int);
void radixSort();
int main(){
    read();
    radixSort();
    print();
    return 0;
}
void read(){
    ifstream f("radixsort.in");
    f >> N >> A >> B >> C;
    v[0] = B;
    for(int i=1;i<N;++i)
        v[i] = (1LL * A * v[i-1] + B) % C;
}
void print(){
    ofstream g("radixsort.out");
    for(int i=0;i<N;i+=10)
        g << v[i] << " ";
    g << "\n";
}
int getMask(int x,int offset){
    return (x >> offset) & mask;
}
void countSort(int source[],int destination[],int offset){
    int cnt[size],indx[size];
    memset(cnt , 0 , sizeof cnt);
    for(int i=0;i<N;++i)
        ++cnt[getMask(source[i],offset)];
    indx[0] = 0;
    for(int i=1;i<size;++i)
        indx[i] = cnt[i-1] + indx[i-1];
    for(int i=0;i<N;++i)
        destination[indx[getMask(source[i],offset)]++] = source[i];
}
void radixSort(){
    for (int i = 0; i * bits < 32; ++i)
        if (i & 1)
            countSort(aux, v, i * bits);
        else
            countSort(v, aux, i * bits);
}