Submission #1068785

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068785		Abito	Wiring (IOI17_wiring)	C++17	13 / 100	61 ms	10316 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define ep insert
using namespace std;
const int N=1e5+5;
int n,m,a[N],b[N];
long long min_total_length(std::vector<int32_t> r, std::vector<int32_t> c) {
	if (r.size()>c.size()) swap(r,c);
	n=r.size();	
	m=c.size();
	set<int> s;
	for (int i=1;i<=n;i++) a[i]=r[i-1];
	for (int i=1;i<=m;i++) b[i]=c[i-1],s.ep(b[i]);
	int ans=0;
	for (int i=1;i<=n;i++){
		auto it=s.lower_bound(a[i]);
		if (it!=s.begin()) --it;
		ans+=abs(a[i]-*it);
		s.erase(it);
	}
	set<int> z;
	for (int i=1;i<=n;i++) z.ep(a[i]);
	for (auto u:s){
		auto it=z.lower_bound(u);
		int x=INT_MAX;
		if (it!=z.end()) x=min(x,abs(u-*it));
		if (it!=z.begin()) --it,x=min(x,abs(u-*it));
		ans+=x; 
	}
	return ans;
}

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