Cod sursa(job #2407143)

Utilizator Leonard123Mirt Leonard Leonard123 Data 16 aprilie 2019 16:01:33
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
using namespace std;
#define maxn 10000005

ifstream cin("radixsort.in");
ofstream cout("radixsort.out");
int arr[maxn],n,a,b,c,m;

void create_array(){
    for(int i=2; i<=n; i++)
        arr[i] = (a * arr[i-1] + b) % c;
}

void digit_sort(int d){
    int output[n+5],count[10]={0};
    for(int i=1; i<=n; i++)
        count[(arr[i]/d)%10]++;
    for(int i=1; i<=9; i++)
        count[i]+=count[i-1];
    for(int i=n; i>0; i--){
        output[count[(arr[i]/d)%10]-1]=arr[i];
        count[(arr[i]/d)%10]--;
    }
    for(int i=1; i<=n; i++)
        arr[i]=output[i-1];
}

void radix_sort(){
    for(int i=1; i<=n; i++)
        if(arr[i]>m)
            m=arr[i];
    for(int d=1; m/d>0; d*=10)
        digit_sort(d);
}

int main(){
    cin>>n>>a>>b>>c;
    arr[1]=b;
    create_array();
    radix_sort();
    for(int i=1; i<=n; i+=10)
        cout<<arr[i]<<' ';
}