Cod sursa(job #2205690)

Utilizator Raoul_16Raoul Bocancea Raoul_16 Data 19 mai 2018 22:02:11
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 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);}