Cod sursa(job #3221080)

Utilizator DumitrescuADumitrescuA DumitrescuA Data 5 aprilie 2024 21:06:23
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <vector>
using namespace std;

ifstream cin("radixsort.in");
ofstream cout("radixsort.out");

int nums[10000000],o[10000000],c[10],n;


int getMax(){
    int max1=nums[0],i;
    for (i=1;i<n;i++)
        if (nums[i]>max1)
            max1=nums[i];
    return max1;
}
void csort(int exp){

    int i;for(i=0;i<10;i++) c[i]=0;
    for(i=0;i<n;i++)
        c[(nums[i]/exp)%10]++;
    for (i=1;i<10;i++)
        c[i]+=c[i-1];
    for(i=n-1;i>=0;i--) {
        o[c[(nums[i]/exp)%10]-1]=nums[i];
        c[(nums[i]/exp)%10]--;
    }
    for (i=0;i<n;i++)
        nums[i]=o[i];
}
void sort1(){
    int  exp;
    int m=getMax();
    for (exp=1;m/exp>0;exp*=10)
        csort(exp);
}

signed main()
{
    int a,b,c;int i;
    cin>>n>>a>>b>>c;
    nums[0]=b;
    for(i=1;i<n;i++){
        nums[i]=((long long)a*nums[i-1]+b)%c;
    }
    sort1();
    for(i=0;i<n;i+=10) cout<<nums[i]<<" ";
    return 0;
}