Cod sursa(job #2491632)

Utilizator MihneaGhiraMihnea MihneaGhira Data 12 noiembrie 2019 21:26:57
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include<fstream>
#include<cstring>
using namespace std;
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
int n,maxim,A,B,C;
int v[1001005],aux[1001005],f[260];

void counting(int putere){
    memset(f,0,sizeof(f));

    for(int i=0;i<n;i++){
        int h=v[i]/putere%256;
        f[h]++;
    }
    for(int i=1;i<256;i++){
        f[i]+=f[i-1];
    }
    for(int i=n-1;i>=0;i--){
        int h=v[i]/putere%256;
        aux[f[h]-1]=v[i];
        f[h]--;
    }

    for(int i=0;i<n;i++){
        v[i]=aux[i];
    }
    return ;
}

int main(){
    fin>>n>>A>>B>>C;
    maxim=v[0]=B;

    for(int i=1;i<n;i++){
        v[i]=(A*v[i-1] +B)%C;
        maxim=max(maxim,v[i]);
    }

    int pow=1;

    while(pow<=maxim){
        counting(pow);
        pow*=256;
    }
    for(int i=0;i<n;i+=10){
        fout<<v[i]<<" ";
    }
    return 0;
}