oj.uz

Submission #421449

# Submission time Handle Problem Language Result Execution time Memory
421449 2021-06-09T07:34:09 Z Berted MalnaRISC (COI21_malnarisc) C++14
100 / 100
 1 ms 296 KB 
#include <iostream>
#include <vector>
#define vi vector<int>
#define pii pair<int, int>
#define fst first
#define snd second
#define vpi vector<pii>


using namespace std;

int N;
vector<vpi> ans;

int solve(int L, int R)
{
	int ret = 0;
	//cerr << L << " " << R << "\n";
	if (L < R)
	{
		int sz = R - L + 1, MSB = 0;
		for (int j = 1 << 6; j; j >>= 1) 
		{
			if (sz & j) {MSB = j; break;}
		}
		if (MSB == sz) {MSB /= 2;}
		ret = max(ret, max(solve(L, L + MSB - 1), solve(L + MSB, R)));
		
		if (ans.size() <= ret) ans.push_back(vpi());
		for (int i = 0; i + L + MSB <= R; i++) {ans[ret].push_back({L + i, L + MSB + i});}
		ret++;

		for (int s = MSB >> 1; s; s >>= 1)
		{
			if (ans.size() <= ret) ans.push_back(vpi());
			for (int i = L + MSB; i <= R; i += 2 * s)
			{
				for (int j = i; j < i + s && j <= R; j++)
				{
					ans[ret].push_back({j - s, j});
				}
			}
			for (int i = L + MSB - s - 1; i - s >= L; i -= 2 * s)
			{
				for (int j = i; j > i - s && j - s >= L; j--)
				{
					ans[ret].push_back({j - s, j});
				}
			}
			ret++;
		}
	}
	//cerr << "DONE: " << L << " " << R << "\n";
	return ret;
}

int main()
{
	cin >> N;
	/*
	for (int i = 0; i < N; i++)
	{
		ans.push_back(vpi());
		for (int j = i % 2 + 1; j + 1 <= N; j += 2)
		{
			ans.back().push_back({j, j + 1});
		}
	}*/

	solve(1, N);

	cout << ans.size() << "\n";
	for (auto &V : ans)
	{
		for (int i = 0; i < V.size(); i++)
		{
			cout << "CMPSWP R" << V[i].fst << " R" << V[i].snd << " \n"[i + 1 == V.size()];
		}
	}
	return 0;
}

Compilation message

malnarisc.cpp: In function 'int solve(int, int)':
malnarisc.cpp:29:18: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |   if (ans.size() <= ret) ans.push_back(vpi());
      |       ~~~~~~~~~~~^~~~~~
malnarisc.cpp:35:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   35 |    if (ans.size() <= ret) ans.push_back(vpi());
      |        ~~~~~~~~~~~^~~~~~
malnarisc.cpp: In function 'int main()':
malnarisc.cpp:75:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |   for (int i = 0; i < V.size(); i++)
      |                   ~~^~~~~~~~~~
malnarisc.cpp:77:70: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |    cout << "CMPSWP R" << V[i].fst << " R" << V[i].snd << " \n"[i + 1 == V.size()];
      |                                                                ~~~~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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