Cod sursa(job #2665263)

Utilizator felixiPuscasu Felix felixi Data 30 octombrie 2020 14:33:15
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.73 kb
#pragma region GCC_CP_Directives
#ifndef ITS_PERSONAL
    #define __FAST_GCC_DIRECTIVE_1 GCC optimize("Ofast")
    #define __FAST_GCC_DIRECTIVE_2 GCC optimize ("unroll-loops")
    #define __FAST_GCC_DIRECTIVE_3 GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

    #pragma OPTIMIZE1
    #pragma OPTIMIZE2
    #pragma OPTIMIZE3

    #undef __FAST_GCC_DIRECTIVE_1
    #undef __FAST_GCC_DIRECTIVE_2
    #undef __FAST_GCC_DIRECTIVE_3
#endif
#pragma endregion GCC_CP_Directives

#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 base = (1 << 8))
{
    long long div = base;
    int elem = *max_element(v.begin(), v.end());
    vector<vector<int>> now(base, vector<int>()), prev = now;
    for (int val : v)
        prev[val % base].push_back(val);
    while (elem / div > 0) {
        for (auto& coada : now)
            coada.clear();
        for (auto& coada : prev)
            for (int val : coada)
                now[val / div % base].push_back(val);
        swap(prev, now);
        div *= base;
    }
    v.clear();
    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
}