Cod sursa(job #3291599)

Utilizator Luca_georgescuLucageorgescu Luca_georgescu Data 5 aprilie 2025 10:20:50
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda cex_9 Marime 1.08 kb
#include <bits/stdc++.h>
#define int long long

using namespace std;

ifstream f("radixsort.in");
ofstream g("radixsort.out");

const int nmax=1e7;

int maxi=-1,n,x,y,z;
int a[nmax+5];
int aux[nmax+5];

void countsort(int n, int exp)
{
    int fr[15];
    memset(fr,0,sizeof(fr));
    memset(aux,0,sizeof(aux));

    for (int i=1; i<=n; i++ )
    {
        int cif=(a[i]/exp)%10;
        fr[cif]++;
    }

    for (int i=1; i<=9; i++ )
        fr[i]+=fr[i-1]; // sp

    for (int i=n; i>=1; i-- )
    {
        int cif=(a[i]/exp)%10;
        aux[fr[cif]]=a[i];
        fr[cif]--;
    }

    for (int i=1; i<=n; i++ )
        a[i]=aux[i];
}

void radix()
{
    int exp=1;
    while ( maxi/exp>0 )
    {
        countsort(n,exp);
        exp*=10;
    }
}
signed main()
{
    ///////// a    b    c
    f >> n >> x >> y >> z;

    a[1]=y;
    maxi=a[1];
    for (int i=2; i<=n; i++ )
    {
        a[i]=(1LL*x*a[i-1]+y)%z;
        maxi=max(maxi,a[i]);
    }

    radix();
    for (int i=1; i<=n; i+=10 )
        g << a[i] << " ";
    return 0;
}