Submission #998912

#	Time	Username	Problem	Language	Result	Execution time	Memory
998912		izanbf	Wiring (IOI17_wiring)	C++14	0 / 100	0 ms	348 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using ll = long long;

int closest(int x, vi& v) {
	int ans = 2e9;
	for (int y : v) {
		ans = min(ans, abs(x - y));
	}
	return ans;
}

ll min_total_length(vi r, vi b) {
	sort(r.begin(), r.end());
	sort(b.begin(), b.end());

	queue<int> red, blue;

	int i = 0, j = 0;
	int n = r.size(), m = b.size();
	ll ans = 0;

	cout << n << ' ' << m << endl;

	while (i < n and j < m) {
		if (r[i] < b[j]) { // r
			if (blue.empty()) {
				red.push(i);
				// cerr << "PUSH red " << i << endl;
			}
			else {
				ans += abs(r[i] - b[blue.front()]);
				// cerr << "a$ " << r[i] << ' ' << b[blue.front()] << ' ' << blue.front() << endl;
				blue.pop();
			}
			++i;
		}
		else { // b
			if (red.empty()) {
				blue.push(j);
				// cerr << "PUSH blue " << j << endl;
			}
			else {
				ans += abs(b[j] - r[red.front()]);
				// cerr << "b$ " << r[red.front()] << ' ' << b[j] << ' ' << red.front() << endl;
				red.pop();
			}
			++j;
		}
	}

	while (i < n) {
		if (blue.empty()) {
			red.push(i);
		}
		else {
			ans += abs(r[i] - b[blue.front()]);
			// cerr << "x$ " << r[i] << ' ' << b[blue.front()] << endl;
			blue.pop();
		}
		++i;
	}

	while (j < m) {
		if (red.empty()) {
			blue.push(j);
		}
		else {
			ans += abs(b[j] - r[red.front()]);
			// cerr << "x$ " << r[red.front()] << ' ' << b[j] << endl;
			red.pop();
		}
		++j;
	}

	// cout << red.size() << ' ' << blue.size() << endl;

	while (not red.empty()) {
		int x = r[red.front()];
		red.pop();
		ans += closest(x, b);
	}

	while (not blue.empty()) {
		int x = b[blue.front()];
		blue.pop();
		ans += closest(x, r);
	}

	return ans;
}

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