Submission #1242429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242429		thelegendary08	Wiring (IOI17_wiring)	C++17	0 / 100	1094 ms	13640 KiB

wiring

#include "wiring.h"
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define vb vector<bool>
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int,int>
#define vpii vector<pii>
#define f0r(i,n) for(int i = 0; i<n; i++)
#define FOR(i, k, n) for(int i = k; i<n; i++)
#define vout(v) for(auto u : v)cout<<u<<' '; cout<<endl;
const int mxn = 1e5 + 5;
using namespace std;
vi par(mxn), sz(mxn);
int find(int x){
	if(x == par[x])return x;
	return par[x] = find(par[x]);
}
void unite(int a, int b){
	a = find(a); b = find(b);
	if(a == b)return;
	if(sz[a] < sz[b])swap(a,b);
	sz[a] += sz[b];
	par[b] = a;
}
long long min_total_length(std::vector<signed> r, std::vector<signed> b) {
	int n = r.size(); int m = b.size();
	vi v(n); vi w(m);
	f0r(i,n)v[i] = r[i];
	f0r(i, m)w[i] = b[i];
	/*
	vector<pair<int, pii>>edges;
	f0r(i, n){
		f0r(j, m){
			edges.pb(mp(abs(v[i] - w[j]), mp(i, j + n)));
		}
	}
	sort(edges.begin(), edges.end());
	f0r(i, n + m){
		par[i] = i; sz[i] = 1;
	}
	int ans = 0;
	f0r(i, edges.size()){
		int x = edges[i].second.first; int y = edges[i].second.second;
		if(sz[find(x)] == 1 && sz[find(y)] == 1){
			cout<<x<<' '<<y<<' '<<edges[i].first<<'\n';
			unite(x,y);
			ans += edges[i].first;
		}
	}
	f0r(i, edges.size()){
		int x = edges[i].second.first; int y = edges[i].second.second;
		if(sz[find(x)] == 1 || sz[find(y)] == 1){
			cout<<x<<' '<<y<<' '<<edges[i].first<<'\n';
			unite(x,y);
			ans += edges[i].first;
		}
	}
	*/
	vi lv(n);
	vi rv(n);
	vi lw(m); 
	vi rw(m);
	int p1 = 0; int p2 = 0;
	while(p1 < n || p2 < m){
		if(p1 == n){
			lw[p2] = p1-1;
			p2++;
		}
		else if(p2 == m){
			lv[p1] = p2-1;
			p1++;
		}
		else{
			if(v[p1] < w[p2]){
				lv[p1] = p2-1;
				p1++;
			}
			else{
				lw[p2] = p1-1;
				p2++;
			}
		}
	}
	p1 = n-1; p2 = m-1;
	while(p1 >= 0 || p2 >= 0){
		if(p1 == -1){
			rw[p2] = p1+1;
			p2--;
		}
		else if(p2 == -1){
			rv[p1] = p2+1;
			p1--;
		}
		else{
			if(v[p1] > w[p2]){
				rv[p1] = p2+1;
				p1--;
			}
			else{
				rw[p2] = p1+1;
				p2--;
			}
		}
	}
	int cnt = 0;
	set<int>s, t;
	f0r(i, n)s.insert(v[i]);
	f0r(i, m)t.insert(w[i]);
	int ans = 0;
	f0r(i, n){
		if(rv[i] == m)rv[i] = -1;
	}
	f0r(i, m){
		if(rw[i] == n)rw[i] = -1;
	}
	// vout(lw);
	// vout(rw);
	
	while(cnt < n + m){
		if(s.size() == 0){
			f0r(i, m){
				if(t.count(w[i])){
					int ret = 4e18;
					if(lw[i] != -1)ret = min(ret, w[i] - v[lw[i]]);
					if(rw[i] != -1)ret = min(ret, v[rw[i]] - w[i]);
					ans += ret;
				}
			}
			cnt = n + m;
		}
		else if(t.size() == 0){
			f0r(i, n){
				if(s.count(v[i])){
					int ret = 4e18;
					if(lv[i] != -1)ret = min(ret, v[i] - w[lv[i]]);
					if(rv[i] != -1)ret = min(ret, w[rv[i]] - v[i]);
					ans += ret;
				}
			}
			cnt = n + m;
		}
		else{
			for(auto A : s){
				auto it = upper_bound(t.begin(), t.end(), A);
				int nr = -4e18;
				if(it != t.end())nr = *it;
				int nl = -4e18;
				if(it != t.begin()){
					it--; nl = *it;
				}
				int x;
				if(abs(nl - A) < abs(nr - A)){
					x = nl;
				}
				else x = nr;
				int dis = min(abs(nl - A), abs(nr - A));
				it = upper_bound(s.begin(), s.end(), x);
				int mr = -4e18;
				if(it != s.end())mr = *it;
				int ml = -4e18;
				if(it != s.begin()){
					it--; ml = *it;
				}
				int y; 
				if(abs(ml - x) < abs(mr - x)){
					y = ml;
				}
				else y = mr;
				if(y == A){
					ans += abs(A - x);
					// cout<<A<<' '<<x<<endl;
					s.erase(A);
					t.erase(x);
					// cout<<s.size()<<' '<<t.size()<<"SDFSD"<<endl;
					cnt += 2; 
					break;
				}
				// cout<<x<<' '<<y<<endl;
			}
		}
		
	}
	return ans;
	
	/*
	int ans = 0;
	int mult = 1;
	f0r(i, n-1){
		ans += mult * (v[i+1] - v[i]);
		mult++;
	}
	ans += max(n, m) * (w[0] - v.back());
	mult = 1;
	for(int i = m-1; i>0; i--){
		ans += mult * (w[i] - w[i-1]);
		mult++;
	}
	return ans;
	*/
	return 0;
	
}

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