Cod sursa(job #2886400)

Utilizator Vasile_AndreiVasile Andrei Calin Vasile_Andrei Data 7 aprilie 2022 18:47:56
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("radixsort.in");
ofstream fout("radixsort.out");

void countSort(int arr[], int n, int exp){
    int sol[n+1];
    int i,cnt[256]{};

    for(i=1;i<=n;++i)
        ++cnt[(arr[i]/exp)%256];

    for(i=1;i<=255;++i)
        cnt[i]+=cnt[i-1];

    for(i=n;i>=1;--i){
        sol[cnt[(arr[i]/exp)%256]]=arr[i];
        --cnt[(arr[i]/exp)%256];
    }

    for(i=1;i<=n;++i)
        arr[i]=sol[i];
}

void radixSort(int n, int arr[]){
    int mx=0,i;
    for(i=1;i<=n;++i)
        mx=max(mx,arr[i]);

    for(int exp=1;mx/exp>0;exp*=256)
        countSort(arr,n,exp);
}

int n,i,arr[100000001],a,b,c;

int main(){
    fin>>n>>a>>b>>c;
    for(i=1;i<=n;++i){
        if(i==1) arr[i]=b;
        else arr[i]=(a*arr[i-1]+b)%c;
    }

    radixSort(n,arr);

    for(i=1;i<=n;i+=10)
        fout<<arr[i]<<' ';

    fin.close();
    fout.close();
    return 0;
}