Cod sursa(job #2224077)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 22 iulie 2018 18:29:08
Problema Radix Sort Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <fstream>
#include <vector>
#include <string>
#include <iostream>

using namespace std;

const string IN_FILE = "radixsort.in";
const string OUT_FILE = "radixsort.out";
const int BITS = 8;
const unsigned MASK = (1 << BITS) - 1;
const int MAX_BITS = 32;

void radixSort(vector<int>& values, const unsigned mask, const int shift) {
    if (int(values.size()) <= 1 || shift < 0) return;
    auto buckets = vector<vector<int>>(MASK + 1);
    for (const auto& v : values) {
        buckets[(v & mask) >> shift].push_back(v);
    }
    int i = 0;
    for (auto& b : buckets) {
        radixSort(b, mask >> BITS, shift - BITS);
        for (const auto& v : b) {
            values[i++] = v;
        }
    }
}

void radixSort(vector<int>& values) {
    radixSort(values, MASK << (MAX_BITS - BITS), MAX_BITS - BITS);
}

vector<int> generateInput() {
    ifstream in(IN_FILE);
    int n, a, b, c;
    in >> n >> a >> b >> c;
    in.close();
    auto values = vector<int>(n);
    values[0] = b;
    for (int i = 1; i < n; i++) {
        values[i] = (1LL * a * values[i - 1] + b) % c;
    }
    return values;
}

void writeOutput(const vector<int>& values) {
    ofstream out(OUT_FILE);
    for (int i = 0; i < int(values.size()); i += 10) {
        out << values[i] << (i + 10 < int(values.size()) ? " " : "\n");
    }
    out.close();
}

int main() {
    auto values = generateInput();
    radixSort(values);
    writeOutput(values);
    return 0;
}