Cod sursa(job #3266699)

Utilizator Alexbora13Bora Ioan Alexandru Alexbora13 Data 9 ianuarie 2025 21:52:33
Problema Radix Sort Scor 30
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");

const int NMAX = 10000000;
const int MOD = 10;

int N, A, B, C;
int n;
int v[NMAX + 1];
int sol[NMAX + 1];

void countSort(int exp)
{
    vector<int> freq(10, 0);
    for (int i = 1; i <= n; i++)
        freq[(v[i] / exp) % MOD]++;
    for (int i = 1; i < 10; i++)
        freq[i] += freq[i - 1];
    for (int i = n; i >= 1; i--)
    {
        sol[freq[(v[i] / exp) % MOD]] = v[i];
        freq[(v[i] / exp) % MOD]--;
    }
    for (int i = 1; i <= n; i++)
        v[i] = sol[i];
}

void radixSort()
{
    int maxi = 0;
    for (int i = 1; i <= n; i++)
        maxi = max(maxi, v[i]);
    for (int p = 1; maxi / p > 0; p *= MOD)
    {
        countSort(p);
    }
}

int main()
{
    fin >> N >> A >> B >> C;
    n = N;
    v[1] = B;
    for (int i = 2; i <= N; i++)
        v[i] = (A * v[i - 1] + B) % C;
    radixSort();
    for (int i = 1; i <= n; i += 10)
        fout << v[i] << ' ';
    return 0;
}