Cod sursa(job #2499301)

Utilizator radugnnGone Radu Mihnea radugnn Data 25 noiembrie 2019 19:54:23
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>
#define DIM 10000010
using namespace std;
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
int cifra(int x, int p){
    return ((x>>p)&255);
}
int v[DIM],aux[DIM];
int f[260];
int N,A,B,C,mx,grupe,i,putere;
int main(){
    fin>>N>>A>>B>>C;
    v[1]=B;
    mx=B;
    for(i=2;i<=N;i++){
        v[i]=(A*v[i-1]+B)%C;
        if(v[i]>mx)
            mx=v[i];
    }
    grupe=8;
    while((1<<grupe)<mx)
        grupe+=8;

    for(putere=0;putere<=grupe;putere+=8){
        for(i=0;i<=255;i++)
            f[i]=0;
        for(i=1;i<=N;i++)
            f[cifra(v[i],putere)]++;
        for(i=1;i<=255;i++)
            f[i]+=f[i-1];
        for(i=N;i>=1;i--){
            aux[f[cifra(v[i],putere)]]=v[i];
            f[cifra(v[i],putere)]--;
        }
        for(i=1;i<=N;i++)
            v[i]=aux[i];
    }
    for(i=1;i<=N;i+=10)
        fout<<v[i]<<" ";
}