Cod sursa(job #3220573)

Utilizator DumitrescuADumitrescuA DumitrescuA Data 4 aprilie 2024 10:53:20
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
#include <vector>
using namespace std;

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

int v[10000005];

void csort(int n,int exp){
    int aux[n],i,c[10]={0};
    for(i=0;i<n;i++)
        c[(v[i]/exp)%10]++;
    for(i=1;i<10;i++) c[i]+=c[i-1];
    for(i=n-1;i>=0;i--){
        aux[c[(v[i]/exp)%10]-1]=v[i];
        c[(v[i]/exp)%10]--;
    }
    for(i=0;i<n;i++) v[i]=aux[i];
}

void fsort(int n,int max1){
    int i;
    for(i=1;max1/i>0;i*=10){
        csort(n,i);
    }
}

int main()
{
    int n,a,b,c,i,max1;
    cin>>n>>a>>b>>c;//v.resize(n);
    v[0]=b;max1=v[0];
    for(i=1;i<n;i++){
        v[i]=(a*v[i-1]+b)%c;max1=max(max1,v[i]);
    }
    fsort(n,max1);
    for(i=0;i<n;i+=10) cout<<v[i]<<" ";
    return 0;
}