Submission #420352

#	Time	Username	Problem	Language	Result	Execution time	Memory
420352		AugustinasJucas	Wiring (IOI17_wiring)	C++14	0 / 100	1 ms	292 KiB

wiring

#include <bits/stdc++.h>
#include "wiring.h"
using namespace std;
vector<int> r, b;
const int inf = 1e9;
long long linf = 1e18;
pair<int, int> closest(int a, vector<int> &b){
	auto desn = lower_bound(b.begin(), b.end(), a) - b.begin();
	if(desn == (int)b.size()){
		return {b[desn-1], inf};
	}else if(desn == 0){
		return {-inf, b[desn]};
	}else{
		return {b[desn-1], b[desn]};
	}
}
long long min_total_length(vector<int> R, vector<int> B) {
	vector<pair<int, int> > visi;
	long long pl = 0;
	for(auto x : R) visi.push_back({x, 0});
	for(auto x : B) visi.push_back({x, 1});
	sort(visi.begin(), visi.end());
	for(int i = 0; i < (int) visi.size(); i++){
		if((i == 0 && visi[1].second == visi[0].second) || (i == (int)visi.size()-1 && visi[visi.size()-2].second == visi[visi.size()-1].second) || (visi[i-1].second == visi[i+1].second && visi[i].second == visi[i+1].second)){
			pair<int, int> pos;
			if(visi[i].second == 0) pos = closest(visi[i].first, B);
			if(visi[i].second == 1) pos = closest(visi[i].first, R);
			pl += min(abs(pos.first - visi[i].first), abs(pos.second - visi[i].first));
			continue;
		}

		if(visi[i].second == 0) r.push_back(visi[i].first);
		else b.push_back(visi[i].first);
	}
	//cout << "r[0] = " << r[0] << ", b[0] = " << b[0] << endl;
	pl += abs(r[0] - b[0]);
	return pl;
}

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