Submission #849310

#	Time	Username	Problem	Language	Result	Execution time	Memory
849310		42kangaroo	Rope (JOI17_rope)	C++17	100 / 100	1990 ms	256872 KiB

rope

//
// Created by 42kangaroo on 11/09/2023.
//
#include "bits/stdc++.h"

using namespace std;

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, c; cin >> n >> c;
	vector<int> colorNum(c);
	// count number of each color, and adjacent pairs of odd/even
	// put these pairs into a vec<vec<int>>
	vector<map<int,int>> adjO(c);
	vector<map<int,int>> adjE(c);
	int last = -1;
	for (int i = 0; i < n; ++i) {
		int a; cin >> a;
		--a;
		colorNum[a]++;
		if (last != -1 && last != a) {
			if (i%2) {adjO[last][a]++; adjO[a][last]++;}
			else {adjE[last][a]++; adjE[a][last]++;}
		}
		last = a;
	}
	// and sort it afterwards by num
	vector<int> o(c);
	std::iota(o.begin(), o.end(),0);
	std::sort(o.begin(), o.end(), [&](int l, int r){return colorNum[l] > colorNum[r];});
	// take max of both(odd/even) for each
	vector<map<int,int>> mins(c);
	for (int i = 0; i < c; ++i) {
		for (auto [k, v]: adjE[i]) {
			if (adjO[i].find(k) != adjO[i].end()) {
				mins[i][k] = min(adjO[i][k], adjE[i][k]);
			}
		}
	}
	// go down with a pointer in the sorted list and check those with connection the max without
	for (int i = 0; i < c; ++i) {
		int mi = n - colorNum[i];
		int j = 0;
		if (j < c && o[j] == i) j++;
		for (; j < c && mins[i].find(o[j]) != mins[i].end(); ++j) {
			mi = min(n - colorNum[i] - colorNum[o[j]] + mins[i][o[j]], mi);
			if (j < c - 1 && o[j + 1] == i) ++j;
		}
		if (j < c) {
			mi = min(n - colorNum[i] - colorNum[o[j]], mi);
		}
		cout << mi<< "\n";
	}
}

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