Cod sursa(job #2665259)

Utilizator felixiPuscasu Felix felixi Data 30 octombrie 2020 14:24:12
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.44 kb
// #ifndef ITS_PERSONAL
//     #pragma GCC optimize("Ofast")
//     #pragma GCC optimize ("unroll-loops")
//     #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// #endif

#include <bits/stdc++.h>

using namespace std;

/// MACROs
#define FOR(i,a,b) for(int i = (a); i <= (b); ++i)

// Meta constants
const bool MULTIPLE_CASES = 0;
const bool PRINT_CASE_MSG = 0;

const int DOUBLE_PRECISION = 6;  // 0 - don't set fixed precision, 

ifstream in("radixsort.in");
ofstream out("radixsort.out");

// type definitions
using i64 = long long;
using pii = pair<int, int>;

// Problem constants
const int INF  = (1 << 30);
const int NMAX = 1e5;

void radix_sort(vector<int>& v, const int bits = 8)
{
    const int base = (1 << bits);
    vector<vector<int>> now(base, vector<int>()), prev = now;
    while( !v.empty() )
        prev[v.back() % base].push_back(v.back()),
        v.pop_back();
    v.shrink_to_fit();
    for (int i = 0, shift = 0; i < 4; ++i, shift += bits) {
        for (auto& coada : now)
            coada.clear();
        for (auto& coada : prev)
            for (int val : coada)
                now[(val >> shift) % base].push_back(val);
        swap(prev, now);
    }

    for (auto& coada : prev)
        for (int val : coada)
            v.push_back(val);
}

void solve()
{
    vector<int> v;
    int N, A, B, C;
    in >> N >> A >> B >> C;
    v.push_back(B);
    FOR(i, 2, N) {
        v.push_back((1LL * A * v.back() + B) % C);
    }
    radix_sort(v);
    for (int i = 0; i < N; i += 10) 
        out << v[i] << ' ';
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    #ifdef ITS_PERSONAL
        auto _time_begin = std::chrono::high_resolution_clock::now();
    #endif

    if (DOUBLE_PRECISION > 0)
        cout << setprecision(DOUBLE_PRECISION) << fixed;

    auto testMessage = [](int id) {
        return "Case #" + to_string(id) + ": ";
    };

    int T = 1;
    if (MULTIPLE_CASES)
        cin >> T;

    for (int t = 1; t <= T; ++t) {
        cout << (PRINT_CASE_MSG ? testMessage(t) : "");
        solve();
    }

    #ifdef ITS_PERSONAL
        auto _time_end = std::chrono::high_resolution_clock::now();
		cerr << setprecision(4) << fixed;
		cerr << "Execution time: " << std::chrono::duration_cast<std::chrono::duration<double>>(_time_end - _time_begin).count() << " seconds" << endl;
    #endif
}