Cod sursa(job #2244645)

Utilizator cosmin.pascaruPascaru Cosmin cosmin.pascaru Data 23 septembrie 2018 12:43:08
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.33 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>

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

const std::string _problemName = "radixsort";

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

#define USE_FILES

#ifdef USE_FILES
#define cin fin
#define cout fout
#endif

const int RADIX_COUNT = 4;
const int RADIX = 0xFF;
const int RADIX_NR_BITS = 8;

struct RadixSorter {

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

        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) {
        for (int fromIdx = 0; fromIdx < size_; ++fromIdx) {
            int radix = getRadix(from[fromIdx], radixIdx);
            ++buckets_[radix];
        }

        index_[0] = 0;
        for (int bucketIdx = 1; bucketIdx < (1 << RADIX_NR_BITS); ++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);
            
            to[index_[radix]] = value;
            ++index_[radix];
        }
    }

    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_[1 << RADIX_NR_BITS];
    int index_  [1 << RADIX_NR_BITS];
};



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