Cod sursa(job #3147756)

Utilizator Robert_MitriRobert Mitri Robert_Mitri Data 26 august 2023 22:02:41
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>
#define max_sz 10000001
using namespace std;
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");

long long n,a,b,c;

int v[max_sz];
int aux[max_sz];
int f[10];

void counting_sort(int exp)
{
    for(int i=0;i<=9;i++)
        f[i]=0;
    for(int i=1;i<=n;i++)
        f[(v[i]/exp)%10]++;
    for(int i=1;i<=9;i++)
        f[i]+=f[i-1];
    for(int i=n;i>=1;i--)
        aux[f[(v[i]/exp)%10]] = v[i],f[(v[i]/exp)%10]--;
    for(int i=1;i<=n;i++)
        v[i]=aux[i];
}
void radix_sort()
{
    int maxim = 0;
    for(int i=1;i<=n;i++)
        if(v[i]>maxim)
            maxim=v[i];

    for(int i=1;maxim/i>0;i*=10)
        counting_sort(i);

}

int main()
{
    fin>>n>>a>>b>>c;
    v[1]=b;
    for(int i=2;i<=n;i++)
        v[i]=(1LL*a*v[i-1]+b)%c;
    radix_sort();
    for(int i=1;i<=n;i+=10)
        fout<<v[i]<<' ';

}