Cod sursa(job #2244664)

Utilizator cosmin.pascaruPascaru Cosmin cosmin.pascaru Data 23 septembrie 2018 13:23:36
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 2.52 kb
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <array>
#include <algorithm>
#include <vector>
#include <stack>
#include <set>
#include <assert.h>
#include <queue>
#include <chrono>
#include <memory>
#include <cstring>

using LL = long long;
using ULL = int long long;

const std::string _problemName = "radixsort";

#define USE_FILES

#ifdef USE_FILES

namespace std {
std::ifstream fin(_problemName + ".in");
std::ofstream fout(_problemName + ".out");
}

#define cin fin
#define cout fout
#endif

const int RADIX = 0xFF;
const int RADIX_COUNT = 4;
const int RADIX_NR_BITS = 8;
const int RADIX_VALUES_COUNT = (1 << RADIX_NR_BITS);

class RadixSorter {

public:

    void radixsort(std::vector<int>& v) {
        resize(v.size());

        // assert RADIX_COUNT % 2 == 0

        for (int idx = 0; idx < RADIX_COUNT; ++idx) {
            if (idx % 2 == 0) {
                countsort(v, aux_, idx);
            }
            else {
                countsort(aux_, v, idx);
            }
        }
    }

private:

    void countsort(const std::vector<int>& from, std::vector<int>& to, int radixIdx) {
        memset(buckets_, 0, sizeof(buckets_));

        for (int fromIdx = 0; fromIdx < size_; ++fromIdx) {
            int value = from[fromIdx];
            int radix = getRadix(value, radixIdx);

            ++buckets_[radix];
        }

        index_[0] = 0;
        for (int bucketIdx = 1; bucketIdx < RADIX_VALUES_COUNT; ++bucketIdx) {
            index_[bucketIdx] = index_[bucketIdx - 1] + buckets_[bucketIdx - 1];
        }

        for (int fromIdx = 0; fromIdx < size_; ++fromIdx) {
            int value = from[fromIdx];
            int radix = getRadix(value, radixIdx);
            int& index = index_[radix];

            to[index] = value;
            ++index;
        }
    }

    int getRadix(int value, int radixIdx) {
        return (value >> (RADIX_NR_BITS * radixIdx)) & RADIX;
    }

    void resize(int n) {
        size_ = n;
        if (aux_.size() < n) {
            aux_.resize(n);
        }
    }

private:

    int size_;
    std::vector<int> aux_;

    int buckets_[RADIX_VALUES_COUNT];
    int index_  [RADIX_VALUES_COUNT];
};



int main() {

    int n, a, b, c;
    std::cin >> n >> a >> b >> c;

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

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

    RadixSorter().radixsort(v);

    for (int idx = 0; idx < v.size(); idx += 10) {
        std::cout << v[idx] << ' ';
    }
    std::cout << '\n';

    return 0;
}