Submission #1068785

#TimeUsernameProblemLanguageResultExecution timeMemory
1068785AbitoWiring (IOI17_wiring)C++17
13 / 100
61 ms10316 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...