Cod sursa(job #2930067)

Utilizator 100pCiornei Stefan 100p Data 27 octombrie 2022 14:05:48
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <bits/stdc++.h>
#define MAX 10000000
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define FILES freopen("radixsort.in","r",stdin);\
              freopen("radixsort.out","w",stdout);
using namespace std;
int n, v[MAX + 5], cat, p = 1, a, b, c, nr[10], put[MAX + 5], indi[10];
void radixSort(int p)
{
    for(int i = 0;i <= 9; ++i)
        nr[i] = 0;
    for(int i = 1;i <= n; ++i)
        nr[(v[i] / p) % 10]++;
    for(int i = 1;i <= 9; ++i)
        indi[i] = nr[i], nr[i] += nr[i-1];
    for(int i = 1;i <= n; ++i){
        int digit = (v[i] / p) % 10;
        put[nr[digit] - indi[digit] + 1] = v[i], indi[digit]--;
        if(p == 10)
            cout << v[i] << '\n';
    }
    for(int i = 1;i <= n; ++i)
        v[i] = put[i];
    for(int i = 1;i <= n; ++i)
        cout << v[i] << ' ', put[i] = 0;
    cout << "\n\n\n";
}
int main()
{
    fastio
    cin >> n >> a >> b >> c;
    v[1] = b;
    for(int i = 2;i <= n; ++i)
        v[i] = (v[i-1] * a + b) % c;
    cat = (int)(log10(c)) + 1;
    for(int i = 1; i <= cat; ++i, p *= 10)
        radixSort(p);
    for(int i = 1;i <= n; i += 10)
        cout << v[i] << ' ';
}