Submission #1227119

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227119		chaeryeong	Rope (JOI17_rope)	C++20	0 / 100	2595 ms	320 KiB

rope

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 1;
int n, m, c[N], mn[N];
void solve () {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> c[i];
	}
	for (int i = 1; i <= m; i++) {
		mn[i] = 1e9;
	}
	//Updates of the form:
	//	- sum[ == i][ == j] += x
	//	- sum[ == i][ != j] += x
	//  - sum[ != i][ == j] += x
	//  - sum[ != i][ != j] += x
	//and same for delta
	if (n % 2 == 1) {
/*		for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= m; j++) {
				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[i] = min(mn[i], sum);
			}
		}*/
		vector <vector <vector <int>>> sum(m + 1, vector <vector <int>> (m + 1, vector <int> (4)));
		vector <vector <vector <int>>> delta(m + 1, vector <vector <int>> (m + 1, vector <int> (4)));
		for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= m; j++) {
				for (int k = 0; k < 4; k++) {
					delta[i][j][k] = 1e9;
				}
			}
		}
		auto insert_sum = [&] (int k, int i, int j, int x) -> void {
			sum[i][j][k] += x;
		};
		auto insert_delta = [&] (int k, int i, int j, int x) -> void {
			delta[i][j][k] = min(delta[i][j][k], max(x, 0));
		};
		for (int i = 1; i < n; i += 2) {
			if (c[i] == c[i + 1]) {
				insert_sum(0, c[i], c[i], 0); insert_delta(0, c[i], c[i], 0);
				insert_sum(1, c[i], c[i], 0); insert_delta(1, c[i], c[i], -2);
				insert_sum(2, c[i], c[i], 0); insert_delta(2, c[i], c[i], 2);
				insert_sum(3, c[i], c[i], 2); insert_delta(3, c[i], c[i], 0);
			} else {
				insert_sum(0, c[i], c[i + 1], 1); insert_delta(0, c[i], c[i + 1], 0);
				insert_sum(1, c[i], c[i + 1], 1); insert_delta(1, c[i], c[i + 1], -1);
				insert_sum(2, c[i], c[i + 1], 1); insert_delta(2, c[i], c[i + 1], 1);
				insert_sum(3, c[i], c[i + 1], 2); insert_delta(3, c[i], c[i + 1], 0);
			}
		}
		insert_sum(0, c[n], c[n], 0); insert_delta(0, c[n], c[n], 0);
		insert_sum(1, c[n], c[n], 0); insert_delta(1, c[n], c[n], -1);
		insert_sum(2, c[n], c[n], 0); insert_delta(2, c[n], c[n], 1);
		insert_sum(3, c[n], c[n], 1); insert_delta(3, c[n], c[n], 0);
		for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= m; j++) {
				int s = sum[i][j][0];
				for (int k = 1; k <= m; j++) {
					if (j != k) {
						s += sum[i][k][1];
					}
					if (i != k) {
						s += sum[k][j][2];
					}
				}
				for (int k = 1; k <= m; k++) {
					for (int l = 1; l <= m; l++) {
						if (k != i && l != j) {
							s += sum[k][l][3];
						}
					}
				}
				int d = delta[i][j][0];
				for (int k = 1; k <= m; j++) {
					if (j != k) {
						d = min(d, delta[i][k][1]);
					}
					if (i != k) {
						d = min(d, delta[k][j][2]);
					}
				}
				for (int k = 1; k <= m; k++) {
					for (int l = 1; l <= m; l++) {
						if (k != i && l != j) {
							d = min(d, delta[k][l][3]);
						}
					}
				}
				mn[i] = min(mn[i], s + d);
			}
		}
	}
	if (n % 2 == 1) {
		for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= m; j++) {
					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[1] != i, c[1] != j);
					delta = min(delta, (c[1] != i) - (c[1] != j));
					delta = max(delta, 0);
					mn[i] = min(mn[i], sum + delta);
			}
		}
	}
	if (n % 2 == 0) {
		for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= m; j++) {
				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[i] = min(mn[i], sum + delta);
			}
		}
	}
	if (n % 2 == 0) {
		for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= m; j++) {
				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));
				}
				delta = max(delta, 0);
				mn[i] = min(mn[i], sum + delta);
			}
		}
	}	
	for (int i = 1; i <= m; i++) {
		cout << mn[i] << '\n';
	}
}
signed main () {
	ios::sync_with_stdio(0); cin.tie(0);
	int tc = 1; //cin >> tc;
	while (tc--) solve();
}

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