Cod sursa(job #2714726)

Utilizator bostanlucastefanBostan Luca-Stefan bostanlucastefan Data 2 martie 2021 13:25:50
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>
#define fq 10000002
#define BASE (1<<8)
#define MASK (BASE-1)

using namespace std;

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

int n,a,b,c,i;
int v[fq],aux[fq];
int f[BASE],ind[BASE];

void radixsort(int n,int b,int v[],int aux[])
{
    int i;
    if(b!=32)
    {
        for(i=0; i<BASE; i++)
            f[i]=0;
        for(i=0; i<n; i++)
        {
            int ii=v[i]>>b&(MASK);
            f[ii]++;
        }

        ind[0]=0;
        for(i=1; i<BASE; i++)
            ind[i]=ind[i-1]+f[i-1];
        for(i=0; i<n; i++)
        {
            int ii=v[i]>>b&(MASK);
            aux[ind[ii]++]=v[i];
        }
        radixsort(n,b+8,aux,v);
    }
}

int main()
{
    fin>>n>>a>>b>>c; v[0]=b;
    for(i=0; i<n; i++)
        v[i]=((long long)a*v[i-1]+b)%c;

    radixsort(n,0,v,aux);

    for(i=0; i<n; i+=10)
        fout<<v[i]<<' ';
    fout<<'\n';
    return 0;
}