Submission #1227116

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227116		chaeryeong	Rope (JOI17_rope)	C++20	45 / 100	2593 ms	840 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 () {
	/*{
		int x; cin >> x;
		for (int i = 0; i < (1 << x); i++) {
			vector <int> c(x, 0);
			for (int j = 0; j < x; j++) {
				c[j] = (i >> j) & 1;
			}
			int p[2] = {};
			bool flag = 0;
			if (x % 2 == 1) {
				p[0] = p[1] = 0;
				for (int j = 0; j < x - 1; j++) {
					int k = j;
					while (k + 1 < x - 1 && c[k + 1] == c[j]) {
						k++;
					}
					int u = (k - j + 1) & 1;
					p[u]++;
					j = k;
				}
				flag |= p[1] == 0;
				p[0] = p[1] = 0;
				for (int j = 1; j < x; j++) {
					int k = j;
					while (k + 1 < x && c[k + 1] == c[j]) {
						k++;
					}
					int u = (k - j + 1) & 1;
					p[u]++;
					j = k;
				}
				flag |= p[1] == 0;
			} else {
				p[0] = p[1] = 0;
				for (int j = 0; j < x; j++) {
					int k = j;
					while (k + 1 < x && c[k + 1] == c[j]) {
						k++;
					}
					int u = (k - j + 1) & 1;
					p[u]++;
					j = k;
				}
				flag |= p[1] == 0;
				p[0] = p[1] = 0;
				for (int j = 1; j < x - 1; j++) {
					int k = j;
					while (k + 1 < x - 1 && c[k + 1] == c[j]) {
						k++;
					}
					int u = (k - j + 1) & 1;
					p[u]++;
					j = k;
				}
				flag |= p[1] == 0;
			}
			if (good(c)) {
				assert(flag);
				for (auto k : c) {
					cout << k << " ";
				}
				cout << '\n';
			} else {
				assert(!flag);
			}
		}
		return;
	}*/
	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++) {
			if (n % 2 == 1) {
				{
					int sum = 0;
					int delta = 1e9;
					for (int k = 1; k < n; k += 2) {
						sum += min((c[k] != i) + (c[k + 1] != i), (c[k] != j) + (c[k + 1] != j));
						delta = min(delta, (c[k] != i) + (c[k + 1] != i) - (c[k] != j) - (c[k + 1] != j));
					}
					sum += min(c[n] != i, c[n] != j);
					delta = min(delta, (c[n] != i) - (c[n] != j));
					delta = max(delta, 0);
					mn = min(mn, sum + delta);


					sum = 0;
					delta = 1e9;
					for (int k = 2; k <= n; k += 2) {
						sum += min((c[k] != i) + (c[k + 1] != i), (c[k] != j) + (c[k + 1] != j));
						delta = min(delta, (c[k] != i) + (c[k + 1] != i) - (c[k] != j) - (c[k + 1] != j));
					}
					sum += min(c[1] != i, c[1] != j);
					delta = min(delta, (c[1] != i) - (c[1] != j));
					delta = max(delta, 0);
					mn = min(mn, sum + delta);
				}
			} else {
				{
					int sum = 0;
					int delta = 1e9;
					for (int k = 2; k < n; k += 2) {
						sum += min((c[k] != i) + (c[k + 1] != i), (c[k] != j) + (c[k + 1] != j));
						delta = min(delta, (c[k] != i) + (c[k + 1] != i) - (c[k] != j) - (c[k + 1] != j));
					}
					sum += min(c[n] != i, c[n] != j);
					sum += min(c[1] != i, c[1] != j);
					delta = min(delta, (c[1] != i) - (c[1] != j));
					delta = min(delta, (c[n] != i) - (c[n] != j));
					delta = max(delta, 0);
					mn = min(mn, sum + delta);


					sum = 0;
					delta = 1e9;
					for (int k = 1; k <= n; k += 2) {
						sum += min((c[k] != i) + (c[k + 1] != i), (c[k] != j) + (c[k + 1] != j));
						delta = min(delta, (c[k] != i) + (c[k + 1] != i) - (c[k] != j) - (c[k + 1] != j));
					}

					delta = max(delta, 0);
					mn = min(mn, sum + delta);
				}
			}
		}
		cout << mn << '\n';
	}
/*	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: 30 / 30
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 20