Submission #1340389

#TimeUsernameProblemLanguageResultExecution timeMemory
1340389jajceslavMalnaRISC (COI21_malnarisc)C++20
100 / 100
1 ms344 KiB
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ll long long
#define ull unsigned long long
#define lll __int128_t
#define ulll __uint128_t
#define ld long double
#define lld __float128

#define fi first
#define se second
#define mp make_pair

#define fast ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

template<typename T>
using V = vector<T>;
template<typename T>
using VV = V<V<T>>;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

template<typename T, typename U>
bool chmax(T &x, U v) {return (v > x)? x=v,1 : 0;}
template<typename T, typename U>
bool chmin(T &x, U v) {return (v < x)? x=v,1 : 0;}

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rnd64(chrono::steady_clock::now().time_since_epoch().count());

// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")

// #define DEBUG

#ifdef DEBUG

#define _main "\e[36m"
#define _reset "\e[39m\n"

template<typename T>
inline void __print(T x) {cerr << x;}
template<typename T, typename U>
inline void __print(pair<T,U> x)
{
    cerr << "("; __print(x.fi); cerr << ", "; __print(x.se); cerr << ")";
}

inline void _print() {}
template<typename T, typename... U>
inline void _print(T x, U... y)
{
    __print(x);
    if(sizeof...(y)) cerr << ", ";
    _print(y...);
}

template<typename T>
inline void _print_arr(T x) {__print(x);}
template<typename T, typename... U>
inline void _print_arr(T x, int size, U... len)
{
    cerr << "[";
    bool has = sizeof...(len);
    for(int i = 0; i < size; i++)
    {
        if(i) cerr << "," << (has? "\n" : " ");
        _print_arr(x[i], len...);
    }
    cerr << "]";
}

#define _source source_location::current()
#define debug_pref(a) cerr << _main << _source.file_name() << ":" << _source.line() << ":" << _source.column() << " [" << a << "]";
#define debug(a...) {debug_pref(#a); cerr << " = ["; _print(a); cerr << "]" << _reset;}
#define debug_arr(a, sz...) {debug_pref(#a); cerr << " = "; _print_arr(a, sz); cerr << _reset;}

#endif
#ifndef DEBUG
#define debug(a...)
#define debug_arr(a, sz...)
#endif

vector<vector<pair<int, int> > > add(vector<vector<pair<int, int> > > a, vector<vector<pair<int, int> > > b)
{
    vector<vector<pair<int, int> > > ans;
    for(int i = 0; i < max(a.size(), b.size()); i++)
    {
        ans.push_back({});
        if(i < a.size()) {
            for(auto x : a[i])
                ans.back().push_back(x);
        }

        if(i < b.size()) {
            for(auto x : b[i])
                ans.back().push_back(x);
        }
    }
    return ans;
}

vector<vector<pair<int, int> > > merge(int l, int r, int k, bool rev = 0)
{
    if(k == 0)
        return {};
    if(r < l)
        return {};

    int m = (l+r)/2;
    vector<vector<pair<int, int> > > ans;
    ans.push_back({});

    for(int i = 0; i < (1 << (k-1)); i++)
    {
        int a = l+i;
        int b = rev ? r-i : m+i+1;
        ans.back().push_back(mp(a, b));
    }

    auto merge_ans = add(merge(l, m, k-1), merge(m+1, r, k-1));
    for(auto x : merge_ans)
        ans.push_back(x);
    return ans;
}

vector<vector<pair<int, int> > > sort(int l, int r, int k)
{
    if(k == 0)
        return {};
    if(r < l)
        return {};
    
    int m = (l+r) / 2;
    auto ans = add(sort(l, m, k-1), sort(m+1, r, k-1));
    auto merge_ans = merge(l, r, k, 1);
    for(auto x : merge_ans)
        ans.push_back(x);
    return ans;
}

int main()
{
    int n; cin >> n;
    int k = 0;
    while(n > (1 << k))
        k++;

    auto ans = sort(1, (1 << k), k);
    cout << ans.size() << '\n';
    for(auto vc : ans)
    {
        bool pr = 0;
        for(auto p : vc) {
            if(p.fi <= n && p.se <= n) {
                cout << "CMPSWP R" << p.fi << " R" << p.se << " ";
                pr = 1;
            }
        }
        if(!pr)
            cout << "CMPSWP R1 R2 ";
        cout << '\n';
    }
} 
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...