제출 #1297200

#제출 시각아이디문제언어결과실행 시간메모리
1297200danirasillaMalnaRISC (COI21_malnarisc)C++20
40 / 100
1 ms560 KiB
#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <map>
#include <iterator>
#include <set>
#include <random>
#include <unordered_map>
#include <queue>
#include <cassert>
#include <stack>
#include <numeric>
#include <deque>


using namespace std;
typedef long long ll;
typedef long double ld;
const ll md1 = 1'000'000'000;
const ll md2 = 998244353;
const ll mdd = 666013;

vector<pair<int, int>> ans[31];

int bitsort(int n, const vector<int>& a, int m) {
	if (n == 1)
		return m;
	int md = (n + 1) / 2;
	for (int i = 0; i + md < n; i++)
		ans[m].push_back({ a[i], a[i + md] });
	vector<int> nww(md);
	for (int i = 0; i < md; i++)
		nww[i] = a[i];
	int mn = bitsort(md, nww, m + 1);
	nww.resize(n - md);
	for (int i = md; i < n; i++)
		nww[i - md] = a[i];
	return max(mn, bitsort(n - md, nww, m + 1));
}

int solve(int n, const vector<int>& a, int m) {
	if (n == 1) {
		return m;
	}
	if (n == 2) {
		ans[m].push_back({ a[0], a[1] });
		return m + 1;
	}
	int md = (n + 1) / 2;
	vector<int> nww(md);
	for (int i = 0; i < md; i++)
		nww[i] = a[i];
	int nwm = solve(md, nww, m);
	nww.resize(n - md);
	for (int i = md; i < n; i++)
		nww[i - md] = a[i];
	reverse(nww.begin(), nww.end());
	nwm = max(nwm, solve(n - md, nww, m));
	return bitsort(n, a, nwm);
}

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

	int t = 1;
	//cin >> t;
	while (t--) {

		int n;
		cin >> n;
		vector<int> nww(n);
		for (int i = 0; i < n; i++)
			nww[i] = i;
		int m = solve(n, nww, 0);
		while (!ans[m].empty())
			m++;
		cout << m << "\n";
		for (int i = 0; i < m; i++) {
			for (auto w : ans[i])
				cout << "CMPSWP R" << w.first + 1 << " R" << w.second + 1 << " ";
			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...