Cod sursa(job #1240327)

Utilizator gabrieligabrieli gabrieli Data 11 octombrie 2014 01:06:17
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include <algorithm>
#include <fstream>
#include <iterator>

using namespace std;

const size_t BASE = 128;

inline size_t number_of_digits(size_t n) {
    size_t i;
    for (i = 0; n; ++i, n /= BASE);
    return i;
}

inline size_t get_digit(size_t n, size_t d) {
    for (; d > 0; --d, n /= BASE);
    return n % BASE;
}

void counting_sort(
            vector<size_t>& v,
            const size_t digit,
            vector<size_t>& counter,
            vector<size_t>& storage) {
    
    fill(counter.begin(), counter.end(), 0);
    
    for_each(v.begin(), v.end(), [&counter, digit] (const size_t& x) {
        ++counter[ get_digit(x, digit) ];
    });
    
    partial_sum(counter.begin(), counter.end(), counter.begin());
    
    for_each(v.rbegin(), v.rend(), [&counter, &storage, digit] (const size_t& x) {
        storage[ --counter[ get_digit(x, digit) ] ] = x;
    });
    
    copy(storage.begin(), storage.end(), v.begin());
}

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

    size_t n, a, b, c;    
    fin >> n >> a >> b >> c;
    
    vector<size_t> v;
    generate_n( back_inserter(v), n, [&a, &b, &c] () {
                    static size_t r = b;
                    size_t t = r;
                    r = (a * r + b) % c;
                    return t;
                });
    
    vector<size_t> counter(BASE);
    vector<size_t> temp_storage(v.size());
 
    for (size_t digit = 0; digit < number_of_digits(c); ++digit)
        counting_sort(v, digit, counter, temp_storage);
   
    for (size_t i = 0; i < v.size(); i += 10)
        fout << v[i] << ' ';
    fout << endl;
       
    return 0;
}