Cod sursa(job #2059701)

Utilizator eragon0502Dumitrescu Dragos eragon0502 Data 7 noiembrie 2017 14:28:10
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <cstdio>

using namespace std;

int f[260],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=1LL*(1LL*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)%256;
            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];
        f[0]=0;

        for(int i=1; i<=n; ++i)
        {
            nr=(v[i]>>k)%256;
            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;
}