Cod sursa(job #2540590)

Utilizator BogauuuBogdan Ivancu Bogauuu Data 7 februarie 2020 12:43:15
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>

using namespace std;

ifstream fin("radixsort.in");
ofstream fout("radixsort.out");

long long n,a,b,c,i,j,k,q,x,maxim,v[10000001],v1[10000001],d[260];

int main ()
{
    fin >> n >> a >> b >> c;
    v[1]=b;
    maxim=v[1];
    for (i=2;i<=n;i++)
    {
        v[i]=1LL*a*1LL*v[i-1]+1LL*b;
        v[i]%=c;
        maxim=max(maxim,v[i]);
    }
    while (maxim!=0)
    {
        k++;
        maxim/=256;
    }
    for (i=1;i<=k;i++)
    {
        for (j=1;j<=n;j++)
        {
            x=v[j]>>q;
            x=(x&255);
            d[x]++;
        }
        for (j=1;j<=255;j++) d[j]+=d[j-1];
        for (j=n;j>=1;j--)
        {
            x=v[j]>>q;
            x=(x&255);
            v1[d[x]]=v[j];
            d[x]--;
        }
        for (j=1;j<=n;j++) v[j]=v1[j];
        for (j=0;j<=256;j++) d[j]=0;
        q+=8;
    }
    for (i=1;i<=n;i+=10) fout << v[i] << " ";

    return 0;
}