Cod sursa(job #3223059)

Utilizator Alex_DumitrascuAlex Dumitrascu Alex_Dumitrascu Data 12 aprilie 2024 11:23:55
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <bits/stdc++.h>
#define ll long long
using namespace std;

ifstream fin ("radixsort.in");
ofstream fout ("radixsort.out");
ll v[2][100000005], cnt[10];
int cif_count (int nr)
{
    int cnt=0;
    while (nr) {
        cnt++;
        nr/=10;
    }
    return cnt;
}
int radix_sort(int n, int maxi)
{
    int iter=cif_count(maxi);
    int imper=1;
    for (int q=1; q<=iter; q++) {
        for (int i=1; i<=n; i++) {
            int digit=(v[(q-1)&1][i]/imper)%10;
            cnt[digit]++;
        }
        for (int i=0; i<=9; i++) {
            cnt[i]+=cnt[i-1];
        }
        for (int i=n; i>=1; i--) {
            int digit=(v[(q-1)&1][i]/imper)%10;
            v[q&1][cnt[digit]]=v[(q-1)&1][i];
            cnt[digit]--;
        }
        for (int i=0; i<=9; i++) {
            cnt[i]=0;
        }
        imper*=10;
    }
    return iter;
}
int main()
{
    ll n, a, b, c, maxi=-1; fin>>n>>a>>b>>c;
    v[0][1]=b;
    for (int i=1; i<=n; i++) {
        v[0][i]=(a*v[0][i-1]+b)%c;
        maxi=max(v[0][i], maxi);

    }
    int iter=radix_sort(n, maxi);
    for (int i=1; i<=n; i+=10) {
        fout<<v[(iter&1)][i]<<' ';
    }
    return 0;
}