oj.uz

Submission #532878

# Submission time Handle Problem Language Result Execution time Memory
532878 2022-03-04T07:02:53 Z rk42745417 Rope (JOI17_rope) C++17
0 / 100
 2500 ms 204 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2558 ms 204 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2558 ms 204 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2558 ms 204 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2558 ms 204 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2558 ms 204 KB Time limit exceeded
2 Halted 0 ms 0 KB -