Cod sursa(job #2496928)

Utilizator melutMelut Zaid melut Data 21 noiembrie 2019 20:55:21
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
#include <fstream>
#include <vector>


using namespace std;


char const in_file[] = "radixsort.in";
char const out_file[] = "radixsort.out";


ifstream Read(in_file);
ofstream Write(out_file);


void RadixSort(
    vector<uint32_t> &vec,
    uint32_t const max_value
) {
    uint8_t bitmask = (1 << 8) - 1;
    vector<uint32_t> sol(vec.size());
    vector<uint32_t> cnt(bitmask);
    uint8_t byte_value;
    uint32_t i;

    for (uint8_t bit = 0; (1ULL << bit) - 1 < max_value; bit += 8) {
        fill(cnt.begin(), cnt.end(), 0);

        for (i = 0; i < vec.size(); ++i) {
            byte_value = (vec[i] >> bit) & bitmask;
            ++cnt[byte_value];
        }

        for (i = 1; i < cnt.size(); ++i) {
            cnt[i] += cnt[i - 1];
        }

        for (i = vec.size() - 1; (int)i >= 0; --i) {
            byte_value = (vec[i] >> bit) & bitmask;
            --cnt[byte_value];
            sol[cnt[byte_value]] = vec[i];
        }

        vec = sol;
    }

    for (i = 0 ; i < sol.size(); i += 10) {
        Write << sol[i] << ' ';
    }
}


void Solve() {
    uint32_t n;
    uint32_t A;
    uint32_t B;
    uint32_t C;

    Read >> n;
    Read >> A;
    Read >> B;
    Read >> C;

    vector<uint32_t> vec(n);
    uint32_t max_value = 0;

    vec[0] = B % C;
    for (uint32_t i = 1; i < n; ++i) {
        vec[i] = (1ULL * vec[i - 1] * A + B) % C;
        max_value = max(max_value, vec[i]);
    }

    RadixSort(vec, max_value);
}


int main() {
    Solve();

    Read.close();
    Write.close();

    return 0;
}