Cod sursa(job #2608085)

Utilizator felixiPuscasu Felix felixi Data 30 aprilie 2020 16:14:47
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <bits/stdc++.h>

using namespace std;

std::string RadixSort(std::vector<int>& v)
{
    const int BASE = 10;
    const int valMax = *std::max_element(v.begin(), v.end());
    const int valMin = *std::min_element(v.begin(), v.end());
    if (valMin < 0) {
        return std::string("Negative values don't work with Radix Sort");
    }
    std::queue<int> q[2][BASE];

    for( auto & x : v )
        q[0][x % BASE].push(x);
    int qind = 1, put = BASE;

    while(valMax >= put) {
        for( int i = 0;  i < BASE;  ++i ) {
            while( !q[1 ^ qind][i].empty() ) {
                int x = q[1 ^ qind][i].front();
                /// std::cerr << x / put % BASE << ' ';
                q[1 ^ qind][i].pop();
                q[qind][x / put % BASE].push(x);
            }
        }
        /// std::cerr << '\n';
        if( valMax / put < BASE )
            break;
        put *= BASE;
        qind ^= 1;
    }
    v.clear();
    for( int i = 0;  i < BASE;  ++i ) 
        while( !q[qind][i].empty() )
            v.push_back(q[qind][i].front()),
            q[qind][i].pop();
    return "";
}

int main()
{
    ifstream in("radixsort.in");
    ofstream out("radixsort.out");
    vector<int> v;
    int N, a,b,c;
    in >> N >> a >> b >> c;
    v.push_back(b);
    for (int i = 2; i <= N; ++i) {
        v.push_back((v.back() * a + b) % c);
    }
    RadixSort(v);
    for (int i = 0; i < (int)v.size(); i += 10){
        out << v[i] << ' ';
    }
    return 0;
}