Submission #781278

#	Time	Username	Problem	Language	Result	Execution time	Memory
781278		GusterGoose27	Wiring (IOI17_wiring)	C++17	100 / 100	26 ms	10972 KiB

wiring

#include "wiring.h"

#include <bits/stdc++.h>

using namespace std;

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

const int MAXN = 2e5+5;
const ll inf = 1e18;
ll dp[MAXN][2];
ll pre[MAXN];
int nxt[MAXN]; // next thing of other color
int prv[MAXN]; // previous thing of same color
bool color[MAXN];
int pos[MAXN];
int n;

int _abs(int v) {
	return v < 0 ? -v : v;
}

ll min_total_length(vector<int> r, vector<int> b) {
	n = r.size()+b.size();
	int i = 0;
	int j = 0;
	while (i < r.size() || j < b.size()) {
		if (i == r.size()) {
			color[i+j] = 1;
			pos[i+j] = b[j];
			j++;
			continue;
		}
		if (j == b.size()) {
			color[i+j] = 0;
			pos[i+j] = r[i];
			i++;
			continue;
		}
		if (r[i] < b[j]) {
			color[i+j] = 0;
			pos[i+j] = r[i];
			i++;
			continue;
		}
		color[i+j] = 1;
		pos[i+j] = b[j];
		j++;
	}
	int occ[2];
	occ[0] = n;
	occ[1] = n;
	for (int i = n-1; i >= 0; i--) {
		occ[color[i]] = i;
		nxt[i] = occ[!color[i]];
	}
	bool hot[2];
	hot[0] = hot[1] = 0;
	for (int i = 0; i < n; i++) {
		pre[i] = hot[color[i]] ? pre[i-1] : 0;
		pre[i] += pos[i];
		if (!hot[color[i]]) occ[color[i]] = i;
		prv[i] = occ[color[i]];
		hot[color[i]] = 1;
		hot[!color[i]] = 0;
	}
	dp[n][0] = 0;
	for (int i = n-1; i >= 0; i--) {
		if (nxt[i] == n) {
			dp[i][0] = inf;
			dp[i][1] = pre[n-1]-((color[i-1] == color[i]) ? pre[i-1] : 0)-(ll)pos[prv[i]-1]*(n-i);
			continue;
		}
		int t = nxt[i];
		int cursz = t-i;
		int nxtsz = nxt[t]-t;
		if (cursz == 1) dp[i][0] = dp[t][1];
		else {
				if (cursz <= nxtsz) {
				ll cur_match = pre[2*t-i-2]-pre[t-2]+((color[i-1] == color[i]) ? pre[i-1] : 0);
				dp[i][0] = cur_match+dp[2*t-i-1][1];
			}
			else {
				if (nxtsz == 1) {
					ll match = (ll)pos[t]*(t-i)-pre[t-1]+((color[i-1] == color[i]) ? pre[i-1] : 0);
					dp[i][0] = min(dp[t][0]+match, dp[t+1][0]+match);
				}
				else {
					int num_match = nxtsz-1;
					ll cur_match = pre[t+num_match-1]-pre[t-1]+((color[i-1] == color[i]) ? pre[i-1] : 0)
					+ (ll)pos[t]*(t-i-num_match); // match them all to the leftmost thing
					dp[i][0] = min(dp[nxt[t]-1][0]+cur_match, dp[nxt[t]][0]+cur_match+pos[nxt[t]-1]-pos[t]);
				}
			}
			dp[i][0] = min(dp[i][0], pos[t]-pos[i]+dp[i+1][0]);
		}
		int p = prv[i]-1;
		if (p == -1) continue; // this will never be queried
		dp[i][1] = pos[i]-pos[p]+min(dp[i][0], dp[i+1][0]);
		if (i < t-1) dp[i][1] = min(dp[i][1], pos[i]-pos[p]+dp[i+1][1]);
	}
	return dp[0][0];
}

Compilation message (stderr)

wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:28:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  while (i < r.size() || j < b.size()) {
      |         ~~^~~~~~~~~~
wiring.cpp:28:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  while (i < r.size() || j < b.size()) {
      |                         ~~^~~~~~~~~~
wiring.cpp:29:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   if (i == r.size()) {
      |       ~~^~~~~~~~~~~
wiring.cpp:35:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   if (j == b.size()) {
      |       ~~^~~~~~~~~~~

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