Submission #532875

#	Time	Username	Problem	Language	Result	Execution time	Memory
532875		rk42745417	Rope (JOI17_rope)	C++17	0 / 100	2560 ms	208 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]--;

	function<int(vector<int>)> go = [&](vector<int> cur) {
		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]);
			res = min(res, go(tmp));
			tmp = cur;
			for(int j = 0; j < i; j++)
				tmp.push_back(cur[cur.size() - j - 1]);
			res = min(res, go(tmp));
		}
		return res;
	};
	for(int i = 0; i < m; i++)
		for(int j = 0; j < m; j++) {
			int r = go(vector<int> {i, j});
			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:26:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   26 |   if(cur.size() == n) {
      |      ~~~~~~~~~~~^~~~
rope.cpp:33:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   for(int i = 1; i <= cur.size(); i++) {
      |                  ~~^~~~~~~~~~~~~
rope.cpp:34:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |    if(cur.size() + i > n)
      |       ~~~~~~~~~~~~~~~^~~
rope.cpp:39:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |    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