Submission #1227112

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227112		chaeryeong	Rope (JOI17_rope)	C++20	15 / 100	2122 ms	327680 KiB

rope

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 1;
int n, m, c[N];
map <vector <int>, int> dp;
int good (vector <int> a) {
	if (a.size() <= 2) {
		return 1;
	}
	if (dp.count(a)) {
		return dp[a];
	}
	bool ret = 0;
	for (int i = 1; i < (int)a.size(); i++) {
		vector <int> c;
		if (i >= (int)a.size() - i) {
			for (int j = i - 1; j >= 0; j--) {
				c.push_back(a[j]);
			}
		} else {
			for (int j = i; j < (int)a.size(); j++) {
				c.push_back(a[j]);
			}
		}
		bool flag = 1;
		for (int j = i - 1; j >= 0; j--) {
			if (i + (i - j) - 1 >= (int)a.size()) {
				break;
			}
			if (a[i + (i - j) - 1] != a[j]) {
				flag = 0;
				break;
			}
		}
		if (!flag) {
			continue;
		}
		ret |= flag && good(c);
	}
	return dp[a] = ret;
}
void solve () {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> c[i];
	}
	for (int i = 1; i <= m; i++) {
		int mn = 1e9;
		for (int j = 1; j <= m; j++) {
			for (int k = 0; k < (1 << n); k++) {
				vector <int> a(n);
				int cnt = 0;
				for (int l = 0; l < n; l++) {
					if ((k >> l) & 1) {
						cnt += (i != c[l + 1]);
					} else {
						cnt += (j != c[l + 1]);
					}
					a[l] = (k >> l) & 1;
				}
				if (good(a)) {
					mn = min(mn, cnt);
				}
			}
		}
		cout << mn << '\n';
	}
}	
signed main () {
	ios::sync_with_stdio(0); cin.tie(0);
	int tc = 1; //cin >> tc;
	while (tc--) solve();
}

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