Submission #136577

#	Time	Username	Problem	Language	Result	Execution time	Memory
136577		wilwxk	Wiring (IOI17_wiring)	C++14	0 / 100	2 ms	380 KiB

wiring

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

const int MAXN=4e5+5;
map<int, int> mp;
int cor[MAXN];
ll dist[MAXN];
ll dp[MAXN][2];
int n, x, y;
ll respf;

void calc(vector<int> &ult, vector<int> &atual) {
	if(ult.empty()||atual.empty()) return;
	// printf("calc\n"); respf=0;
	// for(auto cur : ult) printf("%d ", cur); cout << endl;
	// for(auto cur : atual) printf("%d ", cur); cout << endl;


	for(auto cur : atual) respf+=abs(dist[cur]-dist[ult.back()]);
	for(auto cur : ult) respf+=abs(dist[cur]-dist[atual[0]]);
	respf-=abs(dist[ult.back()]-dist[atual[0]]);
	// printf("%lld\n", respf);
}

ll min_total_length(vector<int> R, vector<int> B) {
	respf=0;
	x=R.size(); y=B.size(); n=x+y;
	for(auto cur : R) mp[cur]=0;
	for(auto cur : B) mp[cur]=1;
	int conti=1; for(auto &mit : mp) {
		cor[conti]=mit.second;
		dist[conti]=mit.first;
		mit.second=conti++;
	}
	cor[n+1]=-1;
	vector<int> ult, cur;
	for(int i=1; i<=n; i++) {
		if(cor[i]==cor[i+1]) cur.push_back(i);
		else {
			cur.push_back(i);
			calc(ult, cur);
			ult.clear();
			swap(cur, ult);
		}
	}

	// respf=

	return respf;
}

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