Submission #624196

#	Time	Username	Problem	Language	Result	Execution time	Memory
624196		Clan328	Wiring (IOI17_wiring)	C++17	17 / 100	1085 ms	6952 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;

vi mapper, bits;

ll cost(int i, int j) {
	vi r, b;
	for (int k = i; k <= j; k++) {
		if (bits[k] != bits[i]) b.push_back(mapper[k]);
		else r.push_back(mapper[k]);
	}

	int n = r.size(), m = b.size();

	// for (int k = 0; k < n; k++) {
	// 	cout << r[k] << " ";
	// }
	// cout << endl;
	// for (int k = 0; k < m; k++) {
	// 	cout << b[k] << " ";
	// }
	// cout << endl;

	ll res = 0;
	if (n <= m) {
		int idx = n-1;
		for (int i = 0; i < m; i++) {
			if (idx < 0) res += b[i]-r[n-1];
			else {
				res += b[i]-r[idx];
				idx--;
			}
		}
	} else {
		int idx = m-1;
		for (int i = 0; i < n; i++) {
			if (idx < 0) res += b[0]-r[i];
			else {
				res += b[idx]-r[i];
				idx--;
			}
		}
	}

	return res;
}

ll min_total_length(vi r, vi b) {
	int n = r.size(), m = b.size();
	// n = 19;

	// 0 Red 1 Blue
	bits = vi(n+m);
	mapper = vi(n+m);
	int idxR = 0, idxB = 0;
	while (idxR < n || idxB < m) {
		if (idxR < n && idxB < m) {
			bits[idxR+idxB] = (r[idxR] > b[idxB]);
			mapper[idxR+idxB] = min(r[idxR], b[idxB]);
			if (r[idxR] < b[idxB]) idxR++;
			else idxB++;
		} else if (idxR < n) {
			bits[idxR+idxB] = 0;
			mapper[idxR+idxB] = r[idxR];
			idxR++;
		} else {
			bits[idxR+idxB] = 1;
			mapper[idxR+idxB] = b[idxB];
			idxB++;
		}
	}

	vector<ll> dp(n+m, LLONG_MAX);
	int start = 0, end = 0, i = 0;
	while (bits[i] == bits[0]) {
		end++;
		i++;
	}

	for ( ; i < n+m; i++) {
		for (int j = start; j < end; j++) {
			if ((j > 0 && dp[j-1] != LLONG_MAX) || (j == 0)) {
				dp[i] = min(dp[i], (j > 0 ? dp[j-1] : 0) +cost(j, i));
			// cout << j << " " << i << " " << dp[j-1] <<endl;
			}
			if (dp[j] != LLONG_MAX) dp[i] = min(dp[j] +cost(j, i), dp[i]);
		}

		// cout << i << " " << start << " " << end << endl;

		if (i < n+m-1 && bits[i] != bits[i+1]) {
			start = end;
			end = i+1;
		}
		// cout << dp[i] << endl;
	}

	// cout << dp[36] << endl;

	return dp[n+m-1];
}

• Subtask 1: 7 / 7
• Subtask 2: 0 / 13
• Subtask 3: 10 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45