Cod sursa(job #2972500)

Utilizator HandoMihnea-Vicentiu Hando Data 29 ianuarie 2023 16:27:11
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.21 kb
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ar array
#define vt vector
#define pq priority_queue
#define pu push
#define pub push_back
#define em emplace
#define emb emplace_back

#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define allp(x, l, r) x.begin() + l, x.begin() + r
#define len(x) (int)x.size()

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <class T, size_t N>
void re(array <T, N>& x);
template <class T> 
void re(vt <T>& x);

template <class T> 
void re(T& x) {
    cin >> x;
}

template <class T, class... M> 
void re(T& x, M&... args) {
    re(x); re(args...);
}

template <class T> 
void re(vt <T>& x) {
    for(auto& it : x)
        re(it);
}

template <class T, size_t N>
void re(array <T, N>& x) {
    for(auto& it : x)
        re(it);
}

template <class T, size_t N>
void wr(array <T, N> x);
template <class T> 
void wr(vt <T> x);

template <class T> 
void wr(T x) {
    cout << x;
}

template <class T, class ...M>  void wr(T x, M... args) {
    wr(x), wr(args...);
}

template <class T> 
void wr(vt <T> x) {
    for(auto it : x)
        wr(it, ' ');
}

template <class T, size_t N>
void wr(array <T, N> x) {
    for(auto it : x)
        wr(it, ' ');
}


inline void Open(const string Name) {
    #ifndef ONLINE_JUDGE
        (void)!freopen((Name + ".in").c_str(), "r", stdin);
        (void)!freopen((Name + ".out").c_str(), "w", stdout);
    #endif
}

void solve() {
    const int byte = 0xFF;
    function <void(int b, vt <int>&, vt <int>&)> radix;
    int n, a, b, c; re(n, a, b, c);
    vt <int> v{b};
    for (int i = 1; i < n; ++i) {
        v.emb((1LL * a * v.back() + b) % c);
    }

    /* knowing that the numbers are integeres we will split them into 4 buckets of a byte 
       the main ideea of radix sort is that after sorting the numbers by all the buckets we will get a sorted array.
       The reason radix sort works is because it takes advantage of the fact that sorting by the bytes 
       first is equivalent to sorting by the entire key, since the relative order of elements with different bytes 
       will be determined by the next byte. By repeating the process for byte, radix sort ensures that the final order of elements is correct.
    */
    radix = [](int x, vt <int>& a, vt <int>& b) {
        vt <int> cnt(byte + 1);
        for (int i = 0; i < len(a); ++i)
            ++cnt[byte & (a[i] >> x * 8)];

        vt <int> idx(byte + 1);
        for (int i = 1; i <= byte; ++i)
            idx[i] = idx[i - 1] + cnt[i - 1];

        for (int i = 0; i < len(a); ++i)
            b[idx[byte & (a[i] >> x * 8)]++] = a[i];
    };

    vt <int> tmp(n);
    for (int i = 0; i < 4; ++i)
        if (i % 2 == 0)
            radix(i, v, tmp);
        else
            radix(i, tmp, v);

    for (int i = 0; i < n; i += 10)
        wr(v[i], ' ');

}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    Open("radixsort");

    int t = 1;
    for(;t;t--) {
        solve();
    }
    
    return 0;
}