Cod sursa(job #2482741)

Utilizator BogdanRuleaBogdan Rulea BogdanRulea Data 28 octombrie 2019 19:59:29
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
#define NMAX 10000001
#define RADIX 0xFF
#define Radix_size 8
#define Get_byte(x) ((x>>(byte*8)&RADIX))
#define Total_Bytes sizeof(numb[0])
int n,a,b,c,numb[NMAX];
void countsort(int * A,int * B,int byte)
{
    int counter[1<<Radix_size];
    int index[1<<Radix_size];
    memset(counter,0,sizeof(counter));
    for(int i=0;i<n;i++)
        ++counter[Get_byte(A[i])];
    index[0]=0;
    for(int i=1;i<1<<Radix_size;i++)
    {
        index[i]=index[i-1]+counter[i-1];
    }
    for(int i=0;i<n;i++)
        B[index[Get_byte(A[i])]++]=A[i];
}
void Radix_sort()
{
    int *tmp=new int[n];
    for(int i=0;i<Total_Bytes;i++)
    {
        if(i%2==0)
            countsort(numb,tmp,i);
        else
            countsort(tmp,numb,i);
    }
}
void read()
{
    fin>>n>>a>>b>>c;
    numb[0]=b%c;
    for(int i=1;i<n;i++)
        numb[i]=(1LL * a *numb[i-1]%c+b)%c;
}
void write()
{
    for(int i=0;i<n;i+=10)
    {
        fout<<numb[i]<<" ";
    }
}
int main()
{
    read();
    Radix_sort();
    write();
    return 0;
}