Cod sursa(job #2546063)

Utilizator teisanumihai84Mihai Teisanu teisanumihai84 Data 13 februarie 2020 19:37:03
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#define b 256
#define dim 10000001
using namespace std;
ifstream fin ("radixsort.in");
ofstream fout ("radixsort.out");
int   v[dim], aux[dim], f[256], i, n, A, B, C, biti, cif, c, maxim;
void sterge ()
{
    for (int i=0; i<=255; i++)
        f[i]=0;
}
int main()
{
    fin>>n>>A>>B>>C;
    v[1]=B;
    for (i=2; i<=n; i++) {
        v[i]=(A*v[i-1]+B)%C;
        if (v[i]>maxim)
            maxim=v[i];
    }
    C--;
    while (C!=0)
    {
        cif++;
        C/=b;
    }
    biti=0;
    for (c=1; c<=cif; c++)
    {
        sterge();
        for (i=1; i<=n; i++)
            f[(v[i]>>biti)&255]++;
        for (i=1; i<b; i++)
            f[i]+=f[i-1];
        for (i=n; i>=1; i--)
            aux[f[((v[i]>>biti)&255)]--]=v[i];
        for (i=1; i<=n; i++)
            v[i]=aux[i];
        biti+=8;
    }
    for (i=1; i<=n; i+=10)
        fout<<v[i]<<" ";
}