Cod sursa(job #2540296)

Utilizator Theo20067Cismaru Theodor-Alexe Theo20067 Data 6 februarie 2020 22:45:16
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
#include <algorithm>
#define BAZA 256
using namespace std;
int n,A,B,C,i,V[10000001],W[10000001],F[BAZA],maxim,cif,P,j;
ifstream fin ("radixsort.in");
ofstream fout("radixsort.out");
int main () {

    fin>>n>>A>>B>>C;
    V[1]=B;
    for(i=2;i<=n;i++)
    {
        V[i]=(A*1LL*V[i-1]+B)%C;
        if(V[i]>maxim)
            maxim=V[i];
    }
    cif=0;
    while(maxim!=0)
    {
        cif++;
        maxim=maxim/BAZA;
    }
    P=0;
    for(j=1;j<=cif;j++)
    {
        for(i=0;i<=BAZA-1;i++)
            F[i]=0;

        for(i=1;i<=n;i++)
            F[(V[i]>>P)&255]++;

        for(i=1;i<=BAZA-1;i++)
            F[i]=F[i]+F[i-1];

        for(i=n;i>=1;i--)
            W[F[(V[i]>>P)&255]--]=V[i];

        for(i=1;i<=n;i++)
            V[i]=W[i];
        P=P+8;
    }
    for(i=1;i<=n;i=i+10)
        fout<<V[i]<<" ";
    return 0;
}