Submission #239458

#	Time	Username	Problem	Language	Result	Execution time	Memory
239458		Jatana	Wiring (IOI17_wiring)	C++17	100 / 100	122 ms	15720 KiB

wiring

#include "wiring.h"
#include <algorithm>
#include <queue>
#include <map>

#define le(v) ((int)v.size())

#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

ll min_total_length(vector<int> r, vector<int> b) {
	vector<int> pos[2];
	pos[0] = r;
	pos[1] = b;
	vector<pii> v;
	for (int x : r) {
		v.emplace_back(x, 0);
	}
	for (int x : b) {
		v.emplace_back(x, 1);
	}
	sort(v.begin(), v.end());
	vector<ll> dp(le(v), 1e18);
	map<int, int> mem;
	mem[0] = -1;
	int pr = 0;
	vector<ll> sum[2];
	sum[0].resize(le(v));
	sum[1].resize(le(v));
	for (int i = 0; i < le(v); i++) {
		if (i > 0) {
			sum[0][i] = sum[0][i - 1];
			sum[1][i] = sum[1][i - 1];
		}
		sum[v[i].y][i] += v[i].x;
		if (v[i].y == 1) pr++;
		else pr--;
		int op = 1 - v[i].y;
		int ind = lower_bound(pos[op].begin(), pos[op].end(), v[i].x) - pos[op].begin();
		ll close = 1e18;
		for (int d : {ind, ind - 1}) {
			if (0 <= d && d < le(pos[op])) {
				close = min(close, (ll)abs(pos[op][d] - v[i].x));
			}
		}
		dp[i] = (i == 0 ? 0 : dp[i - 1]) + close;
		if (mem.count(pr)) {
			int l = mem[pr] + 1;
			ll offset = sum[v[i].y][i] - ((l - 1) >= 0 ? sum[v[i].y][l - 1] : 0);
			offset -= sum[1 - v[i].y][i] - ((l - 1) >= 0 ? sum[1 - v[i].y][l - 1] : 0);
			// for (int j = l; j <= i; j++) {
			// 	if (v[j].y == v[i].y) {
			// 		offset += v[j].x;
			// 	} else offset -= v[j].x;
			// }
			dp[i] = min(dp[i], offset + ((l - 1 >= 0) ? dp[l - 1] : 0));
		}
		mem[pr] = i;
	}
	return dp.back();
}

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