Submission #379780

#	Time	Username	Problem	Language	Result	Execution time	Memory
379780		eagle30	Wiring (IOI17_wiring)	C++14	100 / 100	126 ms	35436 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
const int inf=2000000000;
int n;
pair<int, int> a[1000000];
set<int> si1, si2;
int getnear(int x){
	int ret=2e9;
	if(a[x].second == 1){
		auto p=si1.lower_bound(a[x].first);
		if(p!=si1.end()){
			ret=min(ret, *p-a[x].first);
		}
		if(p!=si1.begin()){
			p--;
			ret=min(ret, a[x].first-*p);
		}
	}
	else{
		auto p=si2.lower_bound(a[x].first);
		if(p!=si2.end()){
			ret=min(ret, *p-a[x].first);
		}
		if(p!=si2.begin()){
			p--;
			ret=min(ret, a[x].first-*p);
		}
	}
	return ret;
}
long long suma[1000000], sumb[1000000];
long long dp[1000000], mat[1000000], prv[1000000];
long long min_total_length(std::vector<int> red, std::vector<int> blue) {
	int p=red.size();
	int q=blue.size();
	for(int i=1; i<=p; i++){
		a[i].first=red[i-1];
		si1.insert(red[i-1]);
		a[i].second=-1;
	}
	for(int i=1; i<=q; i++){
		a[i+p].first=blue[i-1];
		si2.insert(blue[i-1]);
		a[i+p].second=1;
	}
	n=p+q;
	sort(a+1, a+n+1);
	for(int i=0; i<1000000; i++)
        mat[i]=-1;
    for(int i=0; i<1000000; i++)
        prv[i]=-1;
	prv[n]=0;
	int cur=n;
	for(int i=1; i<=n; i++){
		suma[i]=suma[i-1];
		sumb[i]=sumb[i-1];
		if(a[i].second==-1){
			suma[i]+=a[i].first;
			cur++;
		}
		else{
			sumb[i]+=a[i].first;
			cur--;
		}
		if(prv[cur]>=0){
			mat[i]=prv[cur];
		}
		prv[cur]=i;
	}
	for(int i=1; i<=n; i++){
		dp[i]=dp[i-1]+getnear(i);
		if(~mat[i]){
			dp[i]=min(dp[i], dp[mat[i]]+abs(suma[i]-suma[mat[i]]-sumb[i]+sumb[mat[i]]));
		}
	}
	return dp[n];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:51:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   51 |     for(int i=0; i<1000000; i++)
      |     ^~~
wiring.cpp:53:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   53 |  prv[n]=0;
      |  ^~~

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