Cod sursa(job #2586727)

Utilizator raluca1234Tudor Raluca raluca1234 Data 21 martie 2020 13:54:33
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <vector>
#include <fstream>
#include <iostream>

void radix_sort(std::vector<int>& v) {
    std::vector<int> count(256);    // The 256 elements are initialized with zero values.
    std::vector<int> temp((int)v.size());

    for (int shamt = 0; shamt <= 31; shamt += 8) {  // shamt stands for shift amount
        for (auto& x : v)
            count[(x >> shamt) & 255]++;

        for (int i = 1; i < 256; i++)
            count[i] += count[i - 1];

        for (int i = (int)v.size() - 1; i >= 0; i--) {
            temp[--count[(v[i] >> shamt) & 255]] = v[i];
        }

        v = temp;
        std::fill(count.begin(), count.end(), 0);   // reinitialize count vector with zero
  }
}

int main() {
    std::ifstream fin("radixsort.in");
    std::ofstream fout("radixsort.out");

    int n, a, b, c;
    fin >> n >> a >> b >> c;

    std::vector<int> v(n);

    v[0] = b;
    for (int i = 1; i < n; i++) {
        v[i] = (1ll * a * v[i - 1] + b) % c;
    }

    radix_sort(v);

    for (int i = 0; i < (int)v.size(); i += 10)
        fout << v[i] << ' ';
    fout << '\n';
}