Submission #1181163

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181163		jbareja	Rope (JOI17_rope)	C++20	15 / 100	423 ms	1736 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;

bool check(vector<int>& vec) {
	vector<pair<int,int>> intervals;
	int last = 0;
	for (int i=2; i<=N+1; i++) if (vec[i] != vec[i-1]) {
		intervals.push_back({ (i-1) - (last+1) + 1, vec[i-1] });
		last = i-1;
	}
	for (int i=1; i<intervals.size()-1; i++) if (intervals[i].first % 2 != 0) return false;
	return true;
}

int cost(int mask, int a, int b) {
	vector<int> vec = {0};
	int ans = 0;
	for (int i=1; i<=N; i++) {
		if (mask % 2) vec.push_back(a);
		else vec.push_back(b);
		mask /= 2;
		if (C[i] != vec[i]) ans++;
	}
	if (!check(vec)) return -1;
	return ans;
}

void cnt(int a, int b) {
	for (int mask=0; mask<(1<<N); mask++) {
		int temp = cost(mask, a, b);
		if (temp == -1) continue;
		ans[a] = min(ans[a], temp);
		ans[b] = min(ans[b], temp);
	}
}

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++) cnt(i,j);

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

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