Submission #1181307

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181307		jbareja	Rope (JOI17_rope)	C++20	55 / 100	2082 ms	327680 KiB

rope

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr int MAX_N = 1e6+7;
constexpr int MAX_M = 5e3+7;

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

int C[MAX_N];
int ans[MAX_M];
int cnt_color[MAX_M];

unordered_map<ll,int> M_1; // < posortowana para, ilość > - licząc od pierwszego
unordered_map<ll,int> M_2; // < posortowana para, ilość > - licząc od drugiego
int with_one_1[MAX_M];
int with_one_2[MAX_M];
int with_any_1[MAX_M];
int with_any_2[MAX_M];
int cnt_pairs_1 = 0;
int cnt_pairs_2 = 0;
int last1 = 0;
int first2 = 0;
int last2 = 0;

long long hsh_pair(pair<int,int> p) {
	if (p.first > p.second) swap(p.first, p.second);
	return (ll)p.first + (ll)p.second * 1'000'007LL;
}

int cost(int a, int b) {
	// cout << "\n COST ( " << a << " , " << b << " )\n";

	int pairs_ab_1 = M_1[hsh_pair({a,b})];
	int cost1 = with_one_1[a] + with_one_1[b] - pairs_ab_1 + 2 * (cnt_pairs_1 - with_any_1[a] - with_any_1[b] + pairs_ab_1) + (last1 != a && last1 != b && last1 != 0);

	// cout << "pairs_ab_1 = " << pairs_ab_1 << "\n";
	// cout << "with_one_1[" << a << "] = " << with_one_1[a] << "\n";
	// cout << "with_one_1[" << b << "] = " << with_one_1[b] << "\n";
	// cout << "cnt_pairs_1 = " << cnt_pairs_1 << "\n";
	// cout << "with_any_1[" << a << "] = " << with_any_1[a] << "\n";
	// cout << "with_any_1[" << b << "] = " << with_any_1[b] << "\n";
	// cout << "last1 = " << last1 << "\n";
	// cout << "cost1 = " << cost1 << "\n";
	// cout << "\n";

	int pairs_ab_2 = M_2[hsh_pair({a,b})];
	int cost2 = with_one_2[a] + with_one_2[b] - pairs_ab_2 + 2 * (cnt_pairs_2 - with_any_2[a] - with_any_2[b] + pairs_ab_2) + (first2 != a && first2 != b && first2 != 0) + (last2 != a && last2 != b && last2 != 0);

	// cout << "pairs_ab_2 = " << pairs_ab_2 << "\n";
	// cout << "with_one_2[" << a << "] = " << with_one_2[a] << "\n";
	// cout << "with_one_2[" << b << "] = " << with_one_2[b] << "\n";
	// cout << "cnt_pairs_2 = " << cnt_pairs_2 << "\n";
	// cout << "with_any_2[" << a << "] = " << with_any_2[a] << "\n";
	// cout << "with_any_2[" << b << "] = " << with_any_2[b] << "\n";
	// cout << "first2 = " << first2 << "\n";
	// cout << "last2 = " << last2 << "\n";
	// cout << "cost2 = " << cost2 << "\n";
	// cout << "\n";

	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);
	// with_one_1.assign(M+1, 0);
	// with_one_2.assign(M+1, 0);
	// with_any_1.assign(M+1, 0);
	// with_any_2.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+1<=N; i+=2) {
		M_1[hsh_pair({ C[i], C[i+1] })]++;
		cnt_pairs_1++;
		if (C[i] == C[i+1]) with_any_1[C[i]]++;
		else with_one_1[C[i]]++, with_one_1[C[i+1]]++, with_any_1[C[i]]++, with_any_1[C[i+1]]++;
	}
	if (N % 2 == 1) last1 = C[N];

	first2 = C[1];
	for (int i=2; i+1<=N; i+=2) {
		M_2[hsh_pair({ C[i], C[i+1] })]++;
		cnt_pairs_2++;
		if (C[i] == C[i+1]) with_any_2[C[i]] ++;
		else with_one_2[C[i]]++, with_one_2[C[i+1]]++, with_any_2[C[i]]++, with_any_2[C[i+1]]++;
	}
	if (N % 2 == 0) last2 = C[N];

	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: 10 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 20