Submission #1297205

#TimeUsernameProblemLanguageResultExecution timeMemory
1297205danirasillaMalnaRISC (COI21_malnarisc)C++20
60 / 100
1 ms592 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++)
		if (a[i] >= 0 && a[i + md] >= 0)
			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));
}
bool wss = false;
int solve(int n, const vector<int>& a, int m) {
	bool sr = true;
	for (int i = 0; i < n; i++)
		if (a[i] >= 0)
			sr = false;
	wss = sr;
	if (n == 1 || sr) {
		return m;
	}
	if (n == 2) {
		ans[m].push_back({ a[0], a[1] });
		return m + 1;
	}
	int bl = 0;
	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];
	if (!wss) {
		reverse(nww.begin(), nww.end());
		nwm = max(nwm, solve(n - md, nww, m));
		return bitsort(n, a, nwm);
	}
	return solve(n - md, nww, m);
}

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;
		int sz = 1;
		while (sz < n)
			sz *= 2;
		vector<int> nww(sz);
		for (int i = 0; i < sz; i++)
			nww[i] = i + n - sz;
		int m = solve(sz, 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...