Cod sursa(job #1100442)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 6 februarie 2014 21:33:29
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <cstdio>
#include <algorithm>

using namespace std;

int a[10000005],aux[10000005],put[15],N,stop;

inline void Precalcul()
{
    int i;
    put[0]=1;
    for(i=1;i<10;++i)
        put[i]=put[i-1]*10;
}

inline int Get_Digit(int x, int grad)
{
    return (x/put[grad])%10;
}

inline void RadixSort()
{
    int grad,cif,i;
    for(grad=0;grad<=stop;++grad)
    {
        aux[0]=0;
        for(cif=0;cif<10;++cif)
            for(i=1;i<=N;++i)
                if(Get_Digit(a[i],grad)==cif)
                    aux[++aux[0]]=a[i];
        for(i=1;i<=N;++i)
            a[i]=aux[i];
    }
}

int main()
{
    int i,A,B,C,maxim=0;
    freopen ("radixsort.in","r",stdin);
    freopen ("radixsort.out","w",stdout);
    scanf("%d%d%d%d", &N,&A,&B,&C);
    Precalcul();
    for(i=1;i<=N;++i)
    {
        a[i]=(1LL*a[i-1]*A+1LL*B)%C;
        maxim=max(maxim, a[i]);
    }
    for(stop=1;stop<=9 && put[stop]<=maxim;++stop);
    --stop;
    RadixSort();
    for(i=1;i<=N;i+=10)
        printf("%d ", a[i]);
    printf("\n");
    return 0;
}