Cod sursa(job #2053410)

Utilizator eragon0502Dumitrescu Dragos eragon0502 Data 31 octombrie 2017 18:52:22
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb


#include <cstdio>

using namespace std;

int f[255],n;
unsigned int v[10000005],aux[10000005];

void rest()
{
    for(int i=0;i<255;++i)
        f[i]=0;
}

int main()
{
    freopen("radixsort.in","r",stdin);
    freopen("radixsort.out","w",stdout);
    int a,b,c;
    unsigned int nr;

    scanf("%d%d%d%d",&n,&a,&b,&c);

    long long tmp;

    v[1]=b;
    for(int i=2; i<=n; ++i)
    {
        tmp=v[i-1]*a+b;
        tmp%=c;
        v[i]=tmp;
    }

    for(int k=0; k<32; k+=8)
    {
        rest();

        for(int i=1;i<=n;++i)
        {
            nr=(v[i]>>k)%255;
            f[nr]++;
        }

        for(int i=1; i<=255; ++i)
            f[i]+=f[i-1];

        for(int i=255; i>0; --i)
            f[i]=f[i-1];

        for(int i=1; i<=n; ++i)
        {
            nr=(v[i]>>k)%255;
            aux[++f[nr]]=v[i];
        }

        for(int i=1; i<=n; ++i)
            v[i]=aux[i];
    }

    for(int i=1;i<=n;i+=10)
        printf("%d ",v[i]);

    return 0;
}