Submission #166523

#	Time	Username	Problem	Language	Result	Execution time	Memory
166523		Eae02	Wiring (IOI17_wiring)	C++17	Compilation error	0 ms	0 KiB

wiring

#include "wiring.h"
#include "grader.cpp"

#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> distL, 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 (distL[i] != -1) { // match left
		ans = min(ans, dp(i + 1) + distL[i]);
	}
	
	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));
	
	distL.resize(nodes.size(), -1);
	for (ll i = 1; i < nodes.size(); i++) {
		distL[i] = nodes[i].first - nodes[i - 1].first;
		if (nodes[i].second == nodes[i - 1].second)
			distL[i] += distL[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;
	}
	
	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:24: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:34:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (i >= memo.size())
      ~~^~~~~~~~~~~~~~
wiring.cpp:41: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:63:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (ll i = 1; i < nodes.size(); i++) {
                 ~~^~~~~~~~~~~~~~
/tmp/cc5EeFU0.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccUNtTjV.o:wiring.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status