Submission #142816

#	Time	Username	Problem	Language	Result	Execution time	Memory
142816		babo	Wiring (IOI17_wiring)	C++14	13 / 100	79 ms	19576 KiB

wiring

#include <bits/stdc++.h>
#define inf 2000000000
#define all(x) (x).begin(),(x).end()
#define L long long

using namespace std;

struct S{
	L loc,det,chk,lev,milen;
}a[200020];
L dp[200020][2];

vector<L>v[200020];
L n,m;

L min_total_length(vector<int>r, vector<int>b){
	sort(all(r));
	sort(all(b));
	n=r.size();
	m=b.size();
	L i,ret=0;
	for(i=0;i<n;i++)
	{
		a[i]=(S){r[i],1,0};
	}
	for(i=n;i<n+m;i++)
	{
		a[i]=(S){b[i-n],2,0};
	}
	sort(a,a+n+m,[](S a,S b){
		return a.loc<b.loc;
	});

	L lev=100010;
	for(i=0;i<n+m;i++)
	{
		a[i].lev=lev;
		v[lev].push_back(i);
		if(a[i].det==1&&a[i+1].det==1) lev++;
		if(a[i].det==2&&a[i+1].det==2) lev--;
		//printf("%lld %lld\n",a[i].det,a[i].loc);
	}

	for(i=0;i<n+m;i++)
	{
		L mi=inf;
		vector<int>::iterator it;
		if(a[i].det==1)
		{
			it=lower_bound(all(b),a[i].loc);
			if(it!=b.end())
				mi=min(mi,*it-a[i].loc);
			it=upper_bound(all(b),a[i].loc);
			if(it!=b.begin())
				mi=min(mi,a[i].loc-*(prev(it)));
		}
		else
		{
			it=lower_bound(all(r),a[i].loc);
			if(it!=r.end())
				mi=min(mi,*it-a[i].loc);
			it=upper_bound(all(r),a[i].loc);
			if(it!=r.begin())
				mi=min(mi,a[i].loc-*(prev(it)));
		}
		a[i].milen=mi;
		//printf("%lld ",a[i].milen);
	}
	//puts("");
	for(lev=0;lev<200020;lev++)
	{
		if(v[lev].size()%2==0)
		{
			for(i=0;i<v[lev].size();i+=2)
			{
				ret+=a[v[lev][i+1]].loc-a[v[lev][i]].loc;
			}
		}
		else
		{
			for(i=0;i<=v[lev].size();i++)
				dp[i][0]=dp[i][1]=inf;
			dp[0][0]=0;
			for(i=0;i<=v[lev].size();i++)
			{
				if(i>=2) dp[i][0]=min(dp[i][0],dp[i-2][0]+a[v[lev][i-1]].loc-a[v[lev][i-2]].loc);
				if(i>=1) dp[i][1]=min(dp[i][1],dp[i-1][0]+a[v[lev][i-1]].milen);
				if(i>=2) dp[i][1]=min(dp[i][1],dp[i-2][1]+a[v[lev][i-1]].loc-a[v[lev][i-2]].loc);
			}
			//for(i=0;i<=v[lev].size();i++)
			//	printf("%lld %lld\n",dp[i][0],dp[i][1]);
			ret+=dp[v[lev].size()][1];
		}
	}
	return ret;
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:74:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(i=0;i<v[lev].size();i+=2)
            ~^~~~~~~~~~~~~~
wiring.cpp:81:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(i=0;i<=v[lev].size();i++)
            ~^~~~~~~~~~~~~~~
wiring.cpp:84:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(i=0;i<=v[lev].size();i++)
            ~^~~~~~~~~~~~~~~

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