Cod sursa(job #1182846)

Utilizator xtreme77Patrick Sava xtreme77 Data 7 mai 2014 21:47:22
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <cstdio>
#include <cstring>
#define MAX 10000100
#define BZ 10
#define max(a,b) (((a)>(b))?(a):(b))
int v[MAX],b[MAX-1];
void radixsort(int n);
int main()
{
    int n,a,b,c;
    freopen("radixsort.in","r",stdin);
    freopen("radixsort.out","w",stdout);
    scanf("%d%d%d%d",&n,&a,&b,&c);v[1]=b;
    for(int i=2;i<=n;++i)v[i]=(1LL*a*v[i-1]+b)%c;
    radixsort(n);
    for(int i=1;i<=n;i+=10)printf("%d ",v[i]);
    printf("\n");
    return 0;
}
void radixsort(int n)
{
    int maxim = v[1], exp = 1;
    for (int i=1;i<=n;i++)maxim=max(maxim,v[i]);
    while (maxim/exp>0){
        int bukt[BZ];memset(bukt,0,sizeof(bukt));
        for (int i=1;i<=n;i++)bukt[(v[i]/exp)%BZ]++;
        for (int i=1;i<BZ;i++)bukt[i]+=bukt[i-1];
        for (int i=n;i>=1;i--)b[--bukt[(v[i]/exp)%BZ]]=v[i];
        memcpy(v+1,b,sizeof(b));
        exp*=BZ;
    }
}