Cod sursa(job #2496885)

Utilizator melutMelut Zaid melut Data 21 noiembrie 2019 19:58:03
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 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
) {
    vector<uint32_t> sol(vec.size());
    vector<uint32_t> cnt(10);
    uint32_t digit;
    uint32_t i;

    for (uint64_t pow = 1; pow <= max_value; pow *= 10) {
        fill(cnt.begin(), cnt.end(), 0);

        for (i = 0; i < vec.size(); ++i) {
            ++cnt[(vec[i] / pow) % 10];
        }

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

        for (i = vec.size() - 1; (int)i >= 0; --i) {
            digit = (vec[i] / pow) % 10;

            --cnt[digit];
            sol[cnt[digit]] = 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;
    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;
}