Cod sursa(job #2368167)

Utilizator aditzu7Adrian Capraru aditzu7 Data 5 martie 2019 14:23:10
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <stdio.h>
using namespace std;
int n,a,b,c;
int i;
int v[10001*1001];
int maxim(int n,int v[]){
int i;
int mmax=v[1];
for(i=2;i<=n;i++) if(v[i]>mmax) mmax=v[i];
return mmax;

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

}
for(i=1;i<=n;i++) v[i]=ssol[i];
}
void radix(int n,int v[]){
int exp,mmax;
mmax=maxim(n,v);
for(exp=1;mmax/exp>0;exp*=10) sortcif(n,v,exp);

}
int main()
{
    freopen("radixsort.in","r",stdin);
    freopen("radixsort.out","w",stdout);
    scanf("%d%d%d%d",&n,&a,&b,&c);
v[1]=b;
for(i=2;i<=n;i++)v[i]=(v[i-1]*a+b)%c;
radix(n,v);
for(i=1;i<=n;i+=10) printf("%d ",v[i]);


        return 0;
}