Submission #593181

#	Time	Username	Problem	Language	Result	Execution time	Memory
593181		yutabi	Wiring (IOI17_wiring)	C++14	100 / 100	53 ms	12824 KiB

wiring

#include "wiring.h"


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


#define pb push_back


typedef long long ll;
typedef pair <ll,int> ii;




long long min_total_length(std::vector<int> r, std::vector<int> b)
{
	vector <ii> s;

	for(int i=0;i<r.size();i++)
	{
		s.pb(ii(r[i],0));
	}

	for(int i=0;i<b.size();i++)
	{
		s.pb(ii(b[i],1));
	}

	sort(s.begin(),s.end());

	vector <ll> L (s.size());
	vector <ll> R (s.size());

	int last_r=-1;
	int last_b=-1;

	for(int i=0;i<s.size();i++)
	{
		if(s[i].second==0)
		{
			last_r=s[i].first;

			L[i]=last_b;
		}

		else
		{
			last_b=s[i].first;

			L[i]=last_r;
		}
	}

	last_r=-1;
	last_b=-1;

	for(int i=s.size()-1;i>=0;i--)
	{
		if(s[i].second==0)
		{
			last_r=s[i].first;

			R[i]=last_b;
		}

		else
		{
			last_b=s[i].first;

			R[i]=last_r;
		}
	}

	vector <ll> extra_lines;

	priority_queue <ll> pq_b;
	priority_queue <ll> pq_r;

	int el_color=s[0].second;

	ll ans=0;

	int start;

	for(int i=0;s.size();i++)
	{
		if(s[i].second!=el_color)
		{
			for(int j=0;j<i-1;j++)
			{
				extra_lines.pb(s[i].first);
			}

			start=i+1;

			break;
		}

		ans+=R[i]-s[i].first;
	}

	//printf("%lld\n",ans);

	for(int i=start;i<s.size();i++)
	{
		if(el_color==s[i].second)
		{
			extra_lines.clear();
		}

		if(el_color!=s[i].second && extra_lines.size())
		{
			ans+=s[i].first-extra_lines.back();

			if(s[i].second==0)
			{
				pq_r.push(s[i].first-extra_lines.back()+s[i].first);
			}

			else
			{
				pq_b.push(s[i].first-extra_lines.back()+s[i].first);
			}

			extra_lines.pop_back();

			continue;
		}

		int taken=0;

		if(s[i].second==0)
		{
			if(pq_b.size())
			{
				ll num=pq_b.top();
				num-=s[i].first;

				pq_b.pop();

				if(num>-(s[i].first-L[i]))
				{
					taken++;

					ans-=num;

					if(num<0)
					{
						pq_r.push(-num+s[i].first);
					}
				}

				while(pq_b.size() && pq_b.top()-s[i].first>0)
				{
					num=pq_b.top();
					num-=s[i].first;

					pq_b.pop();

					ans-=num;

					el_color=1;

					extra_lines.pb(s[i].first);
				}
			}
		}

		else
		{
			if(pq_r.size())
			{
				ll num=pq_r.top();
				num-=s[i].first;

				pq_r.pop();

				if(num>-(s[i].first-L[i]))
				{
					taken++;

					ans-=num;

					if(num<0)
					{
						pq_b.push(-num+s[i].first);
					}
				}

				while(pq_r.size() && pq_r.top()-s[i].first>0)
				{
					num=pq_r.top();
					num-=s[i].first;

					pq_r.pop();

					ans-=num;

					el_color=0;

					extra_lines.pb(s[i].first);
				}
			}
		}

		if(taken==0)
		{
			ans+=s[i].first-L[i];

			if(s[i].second==0)
			{
				pq_r.push(s[i].first-L[i]+s[i].first);
			}

			else
			{
				pq_b.push(s[i].first-L[i]+s[i].first);
			}
		}

		//printf("%d %lld\n",i,ans);

		if(i==8)
		{
			//printf("\n%d %d %d %d %d\n\n",el_color,extra_lines.size(),pq_r.size(),pq_b.size(),L[8]);
		}
	}


	return ans;
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:21:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for(int i=0;i<r.size();i++)
      |              ~^~~~~~~~~
wiring.cpp:26:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for(int i=0;i<b.size();i++)
      |              ~^~~~~~~~~
wiring.cpp:39:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for(int i=0;i<s.size();i++)
      |              ~^~~~~~~~~
wiring.cpp:106:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |  for(int i=start;i<s.size();i++)
      |                  ~^~~~~~~~~
wiring.cpp:106:18: warning: 'start' may be used uninitialized in this function [-Wmaybe-uninitialized]
  106 |  for(int i=start;i<s.size();i++)
      |                  ^

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