Cod sursa(job #2717016)

Utilizator MateGMGozner Mate MateGM Data 6 martie 2021 09:20:58
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 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;
}