Submission #1061170

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061170		Muhammad_Aneeq	Wiring (IOI17_wiring)	C++17	30 / 100	917 ms	60660 KiB

wiring

// #include "wiring.h"
#include <set>
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
long long min_total_length(vector<int> r, vector<int> b) 
{
	if (r.back()<b.front())
	{
		long long x=min(r.size(),b.size());
		long long ans=0;
		for (long long i=0;i<x;i++)
			ans+=abs(b[i]-r[i]);
		for (long long i=x;i<r.size();i++)
			ans+=min(abs(b.back()-r[i]),abs(b[0]-r[i]));
		for (long long i=x;i<b.size();i++)
			ans+=min(abs(b[i]-r.front()),abs(b[i]-r.back()));
		return ans;
	}
	long long n=r.size(),m=b.size();
	if (n<=1000&&m<=1000)
	{
		map<pair<long long,long long>,long long>dp;
		set<vector<long long>>S;
		S.insert({0,0,0});
		dp[{0,0}]=0;
		while (S.size())
		{
			long long i=(*begin(S))[1],j=(*begin(S))[2],co=(*begin(S))[0];
			S.erase(*begin(S));
			if (dp[{i,j}]!=co)
				continue;
			if (i==n&&j==m)
				break;
			if (i==n||j==m)
				continue;
			if (dp[{i+1,j+1}]==0)
			{
				dp[{i+1,j+1}]=dp[{i,j}]+abs(r[i]-b[j]);
				S.insert({dp[{i+1,j+1}],i+1,j+1});
			}
			if (dp[{i+1,j}]==0)
			{
				dp[{i+1,j}]=dp[{i,j}]+abs(r[i]-b[j]);
				S.insert({dp[{i+1,j}],i+1,j});
			}
			if (dp[{i,j+1}]==0)
			{
				dp[{i,j+1}]=dp[{i,j}]+abs(r[i]-b[j]);
				S.insert({dp[{i,j+1}],i,j+1});
			}
			long long cost=dp[{i,j}]+abs(r[i]-b[j]);
			if (dp[{i+1,j+1}]>cost)
			{
				dp[{i+1,j+1}]=cost;
				S.insert({dp[{i+1,j+1}],i+1,j+1});
			}
			if (dp[{i+1,j}]>cost)
			{
				dp[{i+1,j}]=cost;
				S.insert({dp[{i+1,j}],i+1,j});
			}
			if (dp[{i,j+1}]>cost)
			{
				dp[{i,j+1}]=cost;
				S.insert({dp[{i,j+1}],i,j+1});
			}
		}
		return dp[{n,m}];
	}
	vector<int>red,blue;
	vector<pair<int,int>>d;

	for (int i=0;i<n;i++)
		d.push_back({r[i],0});
	for (int i=0;i<m;i++)
		d.push_back({b[i],1});
	sort(begin(d),end(d));
	for (int i=0;i<n+m;i++)
	{
		if (d[i].second==0)
			red.push_back(i);
		else
			blue.push_back(i);
	}
	map<pair<long long,long long>,long long>dp;
	set<vector<long long>>S;
	S.insert({0,0,0});
	dp[{0,0}]=0;
	while (S.size())
	{
		long long i=(*begin(S))[1],j=(*begin(S))[2],co=(*begin(S))[0];
		S.erase(*begin(S));

		if (dp[{i,j}]!=co)
			continue;
		if (i==n&&j==m)
			break;
		if (i==n||j==m)
			continue;
		if (abs(blue[j]-red[i])>6)
			continue;
		if (dp[{i+1,j+1}]==0)
		{
			dp[{i+1,j+1}]=dp[{i,j}]+abs(r[i]-b[j]);
			S.insert({dp[{i+1,j+1}],i+1,j+1});
		}
		if (dp[{i+1,j}]==0)
		{
			dp[{i+1,j}]=dp[{i,j}]+abs(r[i]-b[j]);
			S.insert({dp[{i+1,j}],i+1,j});
		}
		if (dp[{i,j+1}]==0)
		{
			dp[{i,j+1}]=dp[{i,j}]+abs(r[i]-b[j]);
			S.insert({dp[{i,j+1}],i,j+1});
		}
		long long cost=dp[{i,j}]+abs(r[i]-b[j]);
		if (dp[{i+1,j+1}]>cost)
		{
			dp[{i+1,j+1}]=cost;
			S.insert({dp[{i+1,j+1}],i+1,j+1});
		}
		if (dp[{i+1,j}]>cost)
		{
			dp[{i+1,j}]=cost;
			S.insert({dp[{i+1,j}],i+1,j});
		}
		if (dp[{i,j+1}]>cost)
		{
			dp[{i,j+1}]=cost;
			S.insert({dp[{i,j+1}],i,j+1});
		}
	}
	return dp[{n,m}];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:15:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |   for (long long i=x;i<r.size();i++)
      |                      ~^~~~~~~~~
wiring.cpp:17:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |   for (long long i=x;i<b.size();i++)
      |                      ~^~~~~~~~~

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