Submission #407107

#	Time	Username	Problem	Language	Result	Execution time	Memory
407107		8e7	Wiring (IOI17_wiring)	C++14	100 / 100	80 ms	8992 KiB

wiring

#include "wiring.h"

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#define ll long long
#define maxn 200005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
ll ab(ll x) {
	return x > 0 ? x : -x;
}
int col[maxn];
const ll inf = 1<<30;
priority_queue<ll, vector<ll>, greater<ll> > pq[2];
long long min_total_length(std::vector<int> r, std::vector<int> b) {
	int n = r.size(), m = b.size();
	vector<ll> a;
	int ind = 0, cnt = 0;
	for (int i = 0;i <n;i++) {
		while (ind < m && b[ind] < r[i]) a.push_back(b[ind++]), col[cnt++] = 1;
		a.push_back(r[i]), col[cnt++] = 0;
	}
	while (ind < m) a.push_back(b[ind++]), col[cnt++] = 1;
	ll na = -inf, nb = -inf, ans = 0;
	for (int i = 0;i < n + m;i++) {
		int num = 0;
		while (pq[col[i]].size() && a[i] + pq[col[i]].top() <= 0) {
			ans += a[i] + pq[col[i]].top();
			num++;
			pq[col[i]].pop();
		}	
		if (!num) {
			ll v1 = pq[col[i]].size() ? a[i] + pq[col[i]].top() : 1LL<<45, v2 = a[i] - (col[i] ? na : nb);
			if (v1 < v2) {
				ans += v1;
				pq[col[i]].pop();
				pq[col[i] ^ 1].push(-v1 - a[i]);
			} else {
				ans += v2;
				pq[col[i] ^ 1].push(-v2 - a[i]);
			}
		} else {
			for (int h = 0;h < num - 1;h++){
				pq[col[i]].push(-a[i]);
			}
		}
		if (col[i] == 0) na = a[i];
		else nb = a[i];
	}	
	return ans;
}

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