oj.uz

Submission #421504

# Submission time Handle Problem Language Result Execution time Memory
421504 2021-06-09T08:32:20 Z Drew_ MalnaRISC (COI21_malnarisc) C++17
67.6284 / 100
 6 ms 588 KB 
#include <iostream>
#include <vector>
#include <bitset>
#include <random>
#include <algorithm>
using namespace std;
 
#define pb push_back
#define ii pair<int, int>
#define f1 first
#define s2 second
 
bitset<169> used;
// mt19937 RNG(69);
int main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
 
	int n;
	cin >> n;
 
	vector<ii> rem[100];
	const auto gen = [&](const auto &self, int l, int r, int h) -> void
	{
		if (l >= r)
			return;

		int mid = (l + r) >> 1;
		self(self, l, mid, h);
		self(self, mid+1, r, h);

		for (int i = l; i <= mid; ++i)
			for (int j = mid+1; j <= r; ++j)
				rem[h].pb({i, j});
		return;
	};

	int x = n;
	while ((x & -x) != x)
		x += (x & -x);
	gen(gen, 1, x, 0);

	// for (int i = 1; i <= n; ++i)
	// 	for (int j = i+1; j <= n; ++j)
	// 		rem.pb({i, j});
 
	vector<vector<ii>> res;
	for (int i = 0; i < 1; ++i)
	{
		while (!rem[i].empty())
		{
			//shuffle(rem.begin(), rem.end(), RNG);

			used.reset();
			vector<ii> out, nxt;
			for (auto [a, b] : rem[i])
			{
				if (a > n || b > n)
					continue;

				if (!used[a] && !used[b])
					out.pb({a, b}), used[a] = used[b] = true;
				else nxt.pb({a, b});
			}
	 
			res.pb(out);
			rem[i] = nxt;
		}
	}
	
	cout << res.size() << '\n';
	for (auto &out : res)
	{
		for (int i = 0; i < (int)out.size(); ++i)
			cout << "CMPSWP R" << out[i].f1 << " R" << out[i].s2 << " \n"[i+1 == (int)out.size()];
	}
 
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #2
7.6666666667 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 204 KB Partially correct

Subtask #3
8.4444444444 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 204 KB Partially correct

Subtask #4
7.6666666667 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 332 KB Partially correct

Subtask #5
6.4567901235 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 332 KB Partially correct

Subtask #6
7.213592233 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 332 KB Partially correct

Subtask #7
3.9824561404 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 460 KB Partially correct

Subtask #8
4.803030303 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 460 KB Partially correct

Subtask #9
5.4429530201 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 460 KB Partially correct

Subtask #10
5.9518072289 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 6 ms 588 KB Partially correct