Cod sursa(job #3032393)

Utilizator AlexSerban21Serban Alexandru AlexSerban21 Data 22 martie 2023 09:17:54
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <fstream>
using namespace std;
ifstream fin ("radixsort.in");
ofstream fout ("radixsort.out");
int n,a,i,nrc,maxc,p,b,c,v[10000001],x[10000001],s[256];
int main()
{
    fin>>n>>a>>b>>c;
    v[1]=b;
    for (i=2; i<=n; i++)
    {
        v[i]=(1ll*a*v[i-1]+b)%c;
        if (v[i]>maxc)
            maxc=v[i];
    }
    while (maxc>0)
    {
        nrc++;
        maxc/=256;
    }
    for (c=1; c<=nrc; c++)
    {
        for (i=0; i<=255; i++)
            s[i]=0;
        for (i=1; i<=n; i++)
            s[(v[i]>>p)&255]++;
        for (i=1; i<=255; i++)
            s[i]+=s[i-1];
        for (i=1; i<=n; i++)
        {
            x[s[(v[i]>>p)&255]]=v[i];
            s[(v[i]>>p)&255]--;
        }
        for (i=1; i<=n; i++)
            v[i]=x[i];
        p=p+8;
    }
    for (i=1; i<=n; i+=10)
        fout<<v[i]<<" ";
    return 0;
}