Submission #1181247

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181247		jbareja	Rope (JOI17_rope)	C++20	45 / 100	2586 ms	836 KiB

rope

#include <bits/stdc++.h>

using namespace std;

int N; // liczba węzłów
int M; // liczba kolorów

vector<int> C;
vector<int> ans;
vector<int> cnt_color;

int cost(int a, int b) {
	int cost1 = 0;
	for (int i=1; i+1<=N; i+=2) {
		int cnt_not_ab = 0;
		if (C[i] != a && C[i] != b) cost1++, cnt_not_ab++;
		if (C[i+1] != a && C[i+1] != b) cost1++, cnt_not_ab++;
		if (cnt_not_ab == 0 && C[i] != C[i+1]) cost1++;
	}
	if (N % 2 == 1 && C[N] != a && C[N] != b) cost1++;

	int cost2 = 0;
	if (C[1] != a && C[1] != b) cost2++;
	for (int i=2; i+1<=N; i+=2) {
		int cnt_not_ab = 0;
		if (C[i] != a && C[i] != b) cost2++, cnt_not_ab++;
		if (C[i+1] != a && C[i+1] != b) cost2++, cnt_not_ab++;
		if (cnt_not_ab == 0 && C[i] != C[i+1]) cost2++;
	}
	if (N % 2 == 0 && C[N] != a && C[N] != b) cost2++;

	return min(cost1, cost2);
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> N >> M;
	C.assign(N+2, 0);
	ans.assign(M+1, 0);
	cnt_color.assign(M+1, 0);

	for (int i=1; i<=N; i++) {
		cin >> C[i];
		cnt_color[C[i]]++;
	}

	for (int i=1; i<=M; i++) ans[i] = N - cnt_color[i];

	for (int i=1; i<=M-1; i++) for (int j=i+1; j<=M; j++) {
		int temp = cost(i,j);
		ans[i] = min(ans[i], temp);
		ans[j] = min(ans[j], temp);
	}

	for (int i=1; i<=M; i++) cout << ans[i] << '\n';
}

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