Cod sursa(job #1405561)

Utilizator heracleRadu Muntean heracle Data 29 martie 2015 13:25:02
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <cstdio>
#include <cstring>

FILE* in=fopen("radixsort.in","r");
FILE* out=fopen("radixsort.out","w");

int n,a,b,c;

const int Q=10000007;

int v[Q];

int aux[Q];

int cate[255];

int main()
{
    fscanf(in,"%d%d%d%d",&n,&a,&b,&c);

    v[1]=b;

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

    int go;

    for(int k=0; k<32; k+=8)
    {
        memset(cate,0,sizeof cate);
        for(int i=1; i<=n; i++)
        {
            go=((v[i])>>k)&255;
            cate[go]++;
        }

        for(int i=1; i<256; i++)
            cate[i]+=cate[i-1];

        for(int i=255; i>0; i--)
        {
            cate[i]=cate[i-1];
        }
        cate[0]=0;

        for(int i=1; i<=n; i++)
        {
            go=((v[i])>>k)&255;
            aux[++cate[go]]=v[i];
        }
        for(int i=1; i<=n; i++)
        {
            v[i]=aux[i];
        }

    }

    for(int i=1; i<=n; i+=10)
    {
        fprintf(out,"%d ",v[i]);
    }



    return 0;
}