Cod sursa(job #2446232)

Utilizator GabyD002Dobrita Gabriel GabyD002 Data 7 august 2019 14:56:30
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <bits/stdc++.h>
#define NM 10000005
#define get_byte(x) ((x>>(byte * 8))&255)
using namespace std;
ifstream f("radixsort.in");
ofstream g("radixsort.out");

int n,a,b,c,fr[300];
long long v[NM],sol[NM];

void Read();
void Solve();
void CountingSort(int);

int main()
{   Read();
    Solve();
    return 0;
}

void Read()
{   f>>n>>a>>b>>c;
    v[1]=b;
    for(int i=2; i<=n; i++)
        v[i]=(1LL*(a*v[i-1]+b))%c;
}

void Solve()
{   for(int i=0; i<4; i++)
        CountingSort(i);
    for(int i=1; i<=n; i+=10)
        g<<v[i]<<' ';
}

void CountingSort(int byte)
{   memset(fr,0,sizeof(fr));
    for(int i=1; i<=n; i++)
        fr[get_byte(v[i])]++;
    for(int i=1; i<256; i++)
        fr[i]+=fr[i-1];
    for(int i=n; i; i--)
        sol[fr[get_byte(v[i])]--]=v[i];
    for(int i=1; i<=n; i++)
        v[i]=sol[i];
}