Cod sursa(job #2462663)

Utilizator preda.andreiPreda Andrei preda.andrei Data 27 septembrie 2019 18:31:28
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <vector>

using namespace std;

inline int GetByte(int num, int pos)
{
    return (num >> (pos << 3)) % 256;
}

void CountingSort(const vector<int> &vec, int byte_pos, vector<int> &sorted)
{
    vector<int> count(256, 0);
    for (const auto &num : vec) {
        count[GetByte(num, byte_pos)] += 1;
    }

    vector<int> index(256, 0);
    for (int i = 1; i < 256; i += 1) {
        index[i] = index[i - 1] + count[i - 1];
    }

    for (const auto &num : vec) {
        int byte = GetByte(num, byte_pos);
        sorted[index[byte]] = num;
        index[byte] += 1;
    }
}

void Sort(vector<int> &vec)
{
    vector<int> aux(vec.size());
    for (int i = 0; i < 4; i += 1) {
        if (i % 2 == 0) {
            CountingSort(vec, i, aux);
        } else {
            CountingSort(aux, i, vec);
        }
    }
}

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

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

    vector<int> vec(n);
    vec[0] = b;
    for (int i = 1; i < n; i += 1) {
        vec[i] = (1LL * vec[i - 1] * a + b) % c;
    }

    Sort(vec);

    for (int i = 0; i < n; i += 10) {
        fout << vec[i] << " ";
    }
    fout << "\n";

    return 0;
}