Submission #166531

#	Time	Username	Problem	Language	Result	Execution time	Memory
166531		Eae02	Wiring (IOI17_wiring)	C++14	13 / 100	95 ms	14560 KiB

wiring

#include "wiring.h"

#include <bits/stdc++.h>
#define all(x) begin(x),end(x)
using namespace std;
using ll = long long;

vector<pair<ll, bool>> nodes;

vector<ll> prevDiff, nextDiff;

vector<ll> matchRMemo;
ll matchR(ll i) {
	if (matchRMemo[i] != -1)
		return matchRMemo[i];
	
	ll dst = nextDiff[i] - i;
	ll midx = nextDiff[i] + dst - 1;
	if (midx >= nextDiff[nextDiff[i]])
		midx = nextDiff[i];
	
	ll ans = nodes[midx].first - nodes[i].first;
	if (i + 1 != nodes.size() && nodes[i + 1].second == nodes[i].second)
		ans += matchR(i + 1);
	
	//cout << "MR @" << i << " = " << ans << "\n";
	
	return matchRMemo[i] = ans;
}

vector<ll> memo;
ll dp(ll i) {
	if (i >= memo.size())
		return 0;
	if (memo[i] != -1)
		return memo[i];
	
	ll ans = LLONG_MAX;
	
	if (nextDiff[i] != nodes.size()) { // match right
		ll dst = nextDiff[i] - i;
		ll nidx = min(nextDiff[i] + dst, nextDiff[nextDiff[i]]);
		ans = min(ans, dp(nidx) + matchR(i));
	}
	
	if (prevDiff[i] != -1) { // match left
		ans = min(ans, dp(i + 1) + nodes[i].first - nodes[prevDiff[i]].first);
	}
	
	return memo[i] = ans;
}

ll min_total_length(std::vector<int> r, std::vector<int> b) {
	for (int x : r)
		nodes.emplace_back(x, true);
	for (int x : b)
		nodes.emplace_back(x, false);
	
	sort(all(nodes));
	
	prevDiff.resize(nodes.size(), -1);
	for (ll i = 1; i < nodes.size(); i++) {
		if (nodes[i].second == nodes[i - 1].second)
			prevDiff[i] = prevDiff[i - 1];
		else
			prevDiff[i] = i - 1;
	}
	
	nextDiff.resize(nodes.size() + 1, nodes.size());
	for (ll i = nodes.size() - 2; i >= 0; i--) {
		if (nodes[i].second == nodes[i + 1].second)
			nextDiff[i] = nextDiff[i + 1];
		else
			nextDiff[i] = i + 1;
	}
	
	//for (ll x : distL)
	//	cout << x << " ";
	//cout << "\n";
	
	matchRMemo.resize(nodes.size(), -1);
	memo.resize(nodes.size(), -1);
	
	return dp(0);
}

Compilation message (stderr)

wiring.cpp: In function 'll matchR(ll)':
wiring.cpp:23:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (i + 1 != nodes.size() && nodes[i + 1].second == nodes[i].second)
      ~~~~~~^~~~~~~~~~~~~~~
wiring.cpp: In function 'll dp(ll)':
wiring.cpp:33:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (i >= memo.size())
      ~~^~~~~~~~~~~~~~
wiring.cpp:40:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (nextDiff[i] != nodes.size()) { // match right
wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:62:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (ll i = 1; i < nodes.size(); i++) {
                 ~~^~~~~~~~~~~~~~

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