Cod sursa(job #2224080)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 22 iulie 2018 18:35:13
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 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 int MASK = (1 << BITS) - 1;
const int MAX_BITS = 32;

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

void radixSort(vector<int>& values) {
    for (int shift = 0; shift < MAX_BITS; shift += BITS) {
        radixSort(values, shift);
    }
}

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;
}