Submission #170198

#	Time	Username	Problem	Language	Result	Execution time	Memory
170198		dennisstar	Wiring (IOI17_wiring)	C++11	100 / 100	78 ms	11896 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define ryan bear
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef vector<int> vim;

int R[100010], B[100010];

ll min_total_length(vim r, vim b) {
	int n=r.size(), m=b.size();
	vector<ll> D(n+m+1), sr(n+m+1), sb(n+m+1);
	vim lst(200010);
	vector<pii> ar;
	ar.push_back({0, 0});
	for (int i:r) ar.push_back({i, 0});
	for (int i:b) ar.push_back({i, 1});
	sort(ar.begin(), ar.end());
	fill(lst.begin(), lst.end(), -1);
	for (int i=1; i<=n+m; i++) {
		sr[i]=sr[i-1], sb[i]=sb[i-1];
		if (ar[i].se==0) sr[i]+=ar[i].fi;
		else sb[i]+=ar[i].fi;
	}

	int x=0;
	lst[100000]=0;
	R[0]=-(1<<30);
	for (int i=0; i<n; i++) R[i+1]=r[i];
	R[n+1]=(2e9);
	B[0]=-(1<<30);
	for (int i=0; i<m; i++) B[i+1]=b[i];
	B[m+1]=(2e9);
	for (int i=1; i<=n+m; i++) {
		x+=(ar[i].se==0?1:-1);
		int ls=lst[x+100000];
		if (ar[i].se==0) {
			int lb=lower_bound(B, B+m+1, ar[i].fi)-B;
			D[i]=D[i-1]+min((ll)B[lb]-ar[i].fi, (ll)ar[i].fi-B[lb-1]);
		}
		else {
			int lb=lower_bound(R, R+n+1, ar[i].fi)-R;
			D[i]=D[i-1]+min((ll)R[lb]-ar[i].fi, (ll)ar[i].fi-R[lb-1]);
		}
		if (ls!=-1) D[i]=min(D[i], D[ls]+(ll)abs((sr[i]-sr[ls])-(sb[i]-sb[ls])));
		lst[x+100000]=i;
	}
	return D.back();
}

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