제출 #1340684

#제출 시각아이디문제언어결과실행 시간메모리
1340684domiMalnaRISC (COI21_malnarisc)C++20
100 / 100
1 ms344 KiB
#include <bits/stdc++.h>

#define int long long
#define fi first
#define se second

#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()

#define lsb(x) (x & (-x))
#define vi vector<int>
#define YES { cout << "Yes" << endl; return; }
#define NO { cout << "No" << endl; return; }

using ll = long long;
using pii = std::pair<int, int>;

using namespace std;

vector<vector<pii>> add(vector<vector<pii>> a, vector<vector<pii>> b) {
    vector<vector<pii>> res;
    for (int i = 0; i < max(sz(a), sz(b)); ++i) {
        res.push_back({});
        if (i < a.size()) {
            for (auto &it : a[i])
                res.back().push_back(it);
        }

        if (i < b.size()) {
            for (auto &it : b[i])
                res.back().push_back(it);
        }
    }

    return res;
}

vector<vector<pii>> merge(int st, int dr, int k, bool rev = 0) {
    if (st == dr) return {};
    if (st > dr) return {};

    int m = (st + dr) >> 1;
    vector<vector<pii>> res;
    res.push_back({});
    for (int i = 0; i < (1LL << (k - 1)); ++i) {
        int a = st + i;
        int b = (rev ? dr - i : m + i + 1);
        res.back().push_back({a, b});
    }

    auto merge_ans = add(merge(st, m, k - 1), merge(m + 1, dr, k - 1));
    for (auto &it : merge_ans)
        res.push_back(it);
    return res;
}

vector<vector<pii>> sort(int st, int dr, int k) {
    if (st == dr) return {};
    if (st > dr) return {};

    int m = (st + dr) >> 1;
    auto ans = add(sort(st, m, k - 1), sort(m + 1, dr, k - 1));
    auto merge_ans = merge(st, dr, k, 1);
    for (auto &it : merge_ans)
        ans.push_back(it);
    return ans;
}

int n, k;

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;

    while (n > (1LL << k)) ++k;

    auto ans = sort(1, (1LL << k), k);
    cout << sz(ans) << '\n';
    for (auto &line : ans) {
        auto empty = true;
        for (auto &[a, b] : line) {
            if (a <= n && b <= n) {
                cout << "CMPSWP R" << a << " R" << b << ' ';
                empty = false;
            }
        }

        if (empty) cout << "CMPSWP R1 R2";
        cout << '\n';
    }
    return 0;
}
#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...