Cod sursa(job #2865165)

Utilizator alexmorosanuMorosanu Alexandru alexmorosanu Data 8 martie 2022 15:47:53
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include <cstring>
#include <cmath>
#define RADIX 0xFF
#define RADIX_SIZE 8
#define TOTAL_BYTES sizeof(a[0])
#define get_byte(x) ((x>>(byte*8))&RADIX)
using namespace std;
ifstream f("radixsort.in");
ofstream g("radixsort.out");
int a[10000001],n;
void countsort(int x[],int y[],int byte)
{
    int c[1<<RADIX_SIZE],ind[1<<RADIX_SIZE];
    memset(c,0,sizeof(c));
    ind[0]=0;
    for(int i=0;i<n;i++)
        c[get_byte(x[i])]++;
    for(int i=1;i<1<<RADIX_SIZE;i++)
        ind[i]=ind[i-1]+c[i-1];
    for(int i=0;i<n;i++)
        y[ind[get_byte(x[i])]++]=x[i];
}
void radixsort()
{
    int *t=new int[n];
    for(int i=0;i<TOTAL_BYTES;i++)
        if(i%2==0)
            countsort(a,t,i);
        else
            countsort(t,a,i);
}
long long x,y,z,i,l;
char c[20];
int main()
{
    f>>n>>x>>y>>z;
    a[0]=y%z;
    for(i=1;i<n;i++)
        a[i]=(1LL*a[i-1]*x%z+y)%z;
    radixsort();
    for(i=0;i<n;i=i+10)
    {
        memset(c,0,sizeof(c));
        l=log10(a[i]);
        while(a[i])
        {
            c[l]=a[i]%10+'0';
            l--;
            a[i]=a[i]/10;
        }
        g<<c<<" ";
    }
    return 0;
}