Cod sursa(job #2165978)

Utilizator catalinlupCatalin Lupau catalinlup Data 13 martie 2018 14:47:40
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <bits/stdc++.h>
#define INFILE "radixsort.in"
#define OUTFILE "radixsort.out"
using namespace std;
ifstream in(INFILE);
ofstream out(OUTFILE);

int getMax(int arr[],int n){
    int mx=INT_MIN;
    for(int i=0;i<n;i++)
        mx=max(mx,arr[i]);
    return mx;
}

void CountSort(int arr[],int n,int ex){
    int count[10];
    memset(count,0,sizeof(count));
    int output[n];
    for(int i=0;i<n;i++){
        count[(arr[i]/ex)%10]++;
    }
    for(int i=1;i<10;i++){
        count[i]+=count[i-1];
    }
    for(int i=n-1;i>=0;i--){
        output[count[(arr[i]/ex)%10]-1]=arr[i];
        count[(arr[i]/ex)%10]--;
    }
    for(int i=0;i<n;i++){
        arr[i]=output[i];
    }
}

void Radixsort(int arr[],int n){
    int m=getMax(arr,n);
    //cout<<m<<"\n";
    for(int ex=1;m/ex>0;ex*=10)
        CountSort(arr,n,ex);
}

void Afs(int arr[], int n){
    for(int i=0;i<n;i+=10){
        out<<arr[i]<<" ";
    }
    out<<"\n";
}

int main(){
    int n;
    in>>n;
    int arr[n];
    int A,B,C;
    in>>A>>B>>C;
    arr[0]=B;
    for(int i=1;i<n;i++){
        arr[i]=(A * arr[i-1] + B) % C;
    }
    Radixsort(arr,n);
    Afs(arr,n);
    return 0;
}