Submission #532878

#	Time	Username	Problem	Language	Result	Execution time	Memory
532878		rk42745417	Rope (JOI17_rope)	C++17	0 / 100	2558 ms	204 KiB

rope

#include <bits/stdc++.h>
using namespace std;

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(0);
using ll = int64_t;
using ull = uint64_t;
using uint = uint32_t;
using ld = long double;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const ll LINF = ll(4e48) + ll(2e15);
const double EPS = 1e-9;
static int LamyIsCute = []() {
	EmiliaMyWife
	return 48763;
}();

signed main() {
	int n, m;
	cin >> n >> m;
	vector<int> arr(n), ans(m, INF);
	for(int i = 0; i < n; i++)
		cin >> arr[i], arr[i]--;

	vector<int> cur;
	function<int()> go = [&]() {
		if(cur.size() == n) {
			int w = 0;
			for(int i = 0; i < n; i++)
				w += cur[i] != arr[i];
			return w;
		}
		int res = INF;
		for(int i = 1; i <= cur.size(); i++) {
			if(cur.size() + i > n)
				break;
			vector<int> tmp;
			for(int j = i - 1; ~j; j--)
				tmp.push_back(cur[j]);
			for(int j = 0; j < cur.size(); j++)
				tmp.push_back(cur[j]);
			swap(tmp, cur);
			res = min(res, go());
			cur = tmp;
			for(int j = 0; j < i; j++)
				cur.push_back(tmp[tmp.size() - j - 1]);
			res = min(res, go());
			swap(tmp, cur);
		}
		return res;
	};
	for(int i = 0; i < m; i++)
		for(int j = 0; j < m; j++) {
			cur = {i, j};
			int r = go();
			ans[i] = min(ans[i], r);
			ans[j] = min(ans[j], r);
		}

	for(int i = 0; i < m; i++)
		cout << ans[i] << '\n';
}

Compilation message (stderr)

rope.cpp: In lambda function:
rope.cpp:27:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   27 |   if(cur.size() == n) {
      |      ~~~~~~~~~~~^~~~
rope.cpp:34:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   for(int i = 1; i <= cur.size(); i++) {
      |                  ~~^~~~~~~~~~~~~
rope.cpp:35:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   35 |    if(cur.size() + i > n)
      |       ~~~~~~~~~~~~~~~^~~
rope.cpp:40:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |    for(int j = 0; j < cur.size(); j++)
      |                   ~~^~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 30
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 20