Submission #559549

#	Time	Username	Problem	Language	Result	Execution time	Memory
559549		jamezzz	Wiring (IOI17_wiring)	C++17	0 / 100	47 ms	67748 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define pf printf
#define maxn 100005

int n,m;
vector<int> r,b;
deque<int> dq[maxn];
bool rem[maxn];

ll min_total_length(vector<int> _r,vector<int> _b){
	r=_r;b=_b;
	n=r.size(),m=b.size();
	if(n>m)swap(n,m),swap(r,b);
	int cur=0;
	for(int i=0;i<m;++i){
		while(cur!=n-1&&abs(b[i]-r[cur+1])<abs(b[i]-r[cur]))++cur;
		dq[cur].push_back(i);
	}
	ll ans=0;
	int pv=-1;
	for(int i=0;i<n;++i){
		//printf("now: %d\n",i);
		while(!dq[i].empty()&&rem[dq[i].front()]){
			//pf("used: %d\n",dq[i].front());
			dq[i].pop_front();
		}
		if(dq[i].empty()){
			int nx=pv+1;
			dq[i].push_back(nx);
			rem[nx]=true;
			//pf("steal: %d\n",nx);
		}
		for(int j=0;j<min((int)dq[i].size()-1,pv-i);++j){
			dq[i+1].push_front(dq[i].back());
			//pf("give: %d\n",dq[i].back());
			dq[i].pop_back();
		}
		for(int j:dq[i]){
			//pf("%d ",j);
			ans+=abs(r[i]-b[j]);
			pv=j;
		}
		//pf("\n");
	}
	return ans;
}

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