Cod sursa(job #3221071)

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

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

vector<int> nums;


int getMax(){
    int max1=nums[0],i;
    for (i=1;i<nums.size();i++)
        if (nums[i]>max1)
            max1=nums[i];
    return max1;
}
void csort(long long exp){
    int o[nums.size()];
    int i,c[10]={0};
    for(i=0;i<nums.size();i++)
        c[(nums[i]/exp)%10]++;
    for (i=1;i<10;i++)
        c[i]+=c[i-1];
    for(i=nums.size()-1;i>=0;i--) {
        o[c[(nums[i]/exp)%10]-1]=nums[i];
        c[(nums[i]/exp)%10]--;
    }
    for (i=0;i<nums.size();i++)
        nums[i]=o[i];
}
void sort1(){
    long long  exp;
    long long m=getMax();
    for (exp=1;m/exp>0;exp*=10)
        csort(exp);
}

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