Submission #409771

#	Time	Username	Problem	Language	Result	Execution time	Memory
409771		dreezy	Wiring (IOI17_wiring)	C++17	0 / 100	1082 ms	7192 KiB

wiring

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pi pair<int,int>
#define pb push_back

const int maxn = 1e5 + 5;
bool rpaired[maxn];
bool bpaired[maxn];
ll min_total_length(vector<int> r, vector<int> b){
	//for each point calculate the closest one
	//pair all the closest ones first
	
	ll ans = 0;
	
	
	
	int n = r.size();
	int m = b.size();
	
	if( n <m){
	set<int> bset(b.begin(), b.end());
		for(int i =0; i<n; i++){
			auto left = lower_bound(bset.begin(), bset.end(), r[i]);		
			bool canleft = left != bset.begin();
			if(canleft)
				left = prev(left);
			auto right = upper_bound(bset.begin(), bset.end(), r[i]);
			bool canright = right != bset.end();
			
			if(canleft && canright){
				if( r[i] - *left <= *right - r[i]){
					ans+= r[i] - *left;
					bset.erase(left);
				}
				else{
					ans+= *right - r[i];
					bset.erase(right);
				}	
			}
			else if(canleft){
				ans+= r[i] - *left;
				bset.erase(left);
			}
			else {
				ans+= *right - r[i];
				bset.erase(right);
			}
		}
		
		for(int bpoint : bset){
			auto left = lower_bound(r.begin(), r.end(), bpoint);		
			bool canleft = left != r.begin();
			if(canleft)
				left = prev(left);
			auto right = upper_bound(r.begin(), r.end(), bpoint);
			bool canright = right != r.end();
			
			if(canleft && canright){
				if( bpoint - *left <= *right -bpoint){
					ans+= bpoint - *left;
				}
				else{
					ans+= *right - bpoint;
				}	
			}
			else if(canleft){
				ans+= bpoint - *left;
			}
			else {
				ans+= *right - bpoint;
			}
		}
	}
	else{
		set<int> rset(r.begin(), r.end());
		for(int i =0; i<m; i++){
			auto left = lower_bound(rset.begin(), rset.end(), b[i]);		
			bool canleft = left != rset.begin();
			if(canleft)
				left = prev(left);
			auto right = upper_bound(rset.begin(), rset.end(), b[i]);
			bool canright = right != rset.end();
			
			if(canleft && canright){
				if( b[i] - *left <= *right - b[i]){
					ans+= b[i] - *left;
					rset.erase(left);
				}
				else{
					ans+= *right - b[i];
					rset.erase(right);
				}	
			}
			else if(canleft){
				ans+= b[i] - *left;
				rset.erase(left);
			}
			else {
				ans+= *right - b[i];
				rset.erase(right);
			}
		}
		
		for(int rpoint : rset){
			auto left = lower_bound(b.begin(), b.end(), rpoint);		
			bool canleft = left != b.begin();
			if(canleft)
				left = prev(left);
			auto right = upper_bound(b.begin(), b.end(), rpoint);
			bool canright = right != b.end();
			
			if(canleft && canright){
				if( rpoint - *left <= *right -rpoint){
					ans+= rpoint - *left;
				}
				else{
					ans+= *right - rpoint;
				}	
			}
			else if(canleft){
				ans+= rpoint - *left;
			}
			else {
				ans+= *right - rpoint;
			}
		}
	}
	
	
	
	return ans;
}

/*
int main(){
	int n, m; cin >> n >> m;
	
	vector<int> r(n), b(m);
	
	 for(int i =0; i<n;i++) cin >> r[i];
	 for(int i = 0; i<m;i++) cin >> b[i];
	cout << min_total_length(r, b)<<endl;
}
*/

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