Cod sursa(job #1955402)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 5 aprilie 2017 22:41:02
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <cstdio>
#define BAZA 256
using namespace std;
int v[10000001],aux[10000001],f[BAZA];
int main()
{
    FILE *fin=fopen ("radixsort.in","r");
    FILE *fout=fopen ("radixsort.out","w");
    int n,a,b,c,i,x,nr;
    fscanf (fin,"%d%d%d%d",&n,&a,&b,&c);
    v[1]=b;
    for (i=2;i<=n;i++)
        v[i]=((long long)v[i-1]*a+b)%c;
    nr=1;
    for (int bit=0;bit<=3;bit++){
        for (i=0;i<=BAZA-1;i++)
            f[i]=0;
        for (i=1;i<=n;i++)
            f[(v[i]/nr)%BAZA]++;
        for (i=1;i<=BAZA-1;i++)
            f[i]+=f[i-1];
        for (i=n;i>0;i--){
            x=(v[i]/nr)%BAZA;
            aux[f[x]]=v[i];
            f[x]--;
        }
        for (i=1;i<=n;i++)
            v[i]=aux[i];
        nr=nr*BAZA;
    }
    for (i=1;i<=n;i+=10)
        fprintf (fout,"%d ",v[i]);
    return 0;
}