Cod sursa(job #3182555)

Utilizator Cristi3956Pop Cristian Cristi3956 Data 9 decembrie 2023 10:07:42
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
int a,b,c,n,v[10000001];
int maxarr(int a[], int n)
{
    int max=a[0];
    for(int i=1;i<n;i++)
        if(a[i]>max)
            max=a[i];
    return max;
}
void countingsort(int a[], int n, int loc)
{
    const int max = 10;
    int sortat[n];
    int frec[max];
    for(int i=0;i<max;i++)
        frec[i]=0;
    for(int i=0;i<n;i++)
        frec[(a[i]/loc)%10]++;
    for(int i=1;i<max;i++)
        frec[i]+=frec[i - 1];
    for (int i=n-1;i>=0;i--)
    {
        sortat[frec[(a[i]/loc)%10]-1]=a[i];
        frec[(a[i]/loc)%10]--;
    }
    for (int i=0;i<n;i++)
    a[i]=sortat[i];
}
void radixsort(int a[], int n)
{
    int max=maxarr(a, n);
    for(int loc=1;max/loc>0;loc*=10)
    countingsort(a,n,loc);
}
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;
    radixsort(v,n);
    for(int i=1;i<n;i+=10)
        fout<<v[i]<<" ";
    return 0;
}