Submission #72622

#	Time	Username	Problem	Language	Result	Execution time	Memory
72622		idan_izmirli	Wiring (IOI17_wiring)	C++14	0 / 100	3 ms	432 KiB

wiring

#include "wiring.h"

using namespace std;

long long best[200000][3][2];
long long next_different[200000];
long long last_different[200000];

long long inline mmin(long long a,long long b)
{
	if(a<b)
	{
		return a;
	}
	return b;
}

long long min_total_length(std::vector<int> r, std::vector<int> b) {
	int r_idx=0,b_idx=0,place=0;
	bool red;
	long long next_of_kind[2];
	long long last_of_kind[2];
	vector<pair<int,int>> pole(r.size()+b.size());
	while((r_idx<r.size())||(b_idx<b.size()))
	{
		if(r_idx>=r.size())
		{
			red=false;
		}
		else if(b_idx>=b.size())
		{
			red=true;
		}
		else
		{
			red=r[r_idx]<b[b_idx];
		}
		if(red)
		{
			pole[place]=make_pair(0,r[r_idx]);
			r_idx++;
		}
		else
		{
			pole[place]=make_pair(1,b[b_idx]);
			b_idx++;
		}
		place++;
	}
	next_of_kind[0]=3000000000;
	next_of_kind[1]=next_of_kind[0];
	last_of_kind[0]=-next_of_kind[0];
	last_of_kind[1]=last_of_kind[0];
	for(int i=0;i<pole.size();i++)
	{
		last_of_kind[pole[i].first]=pole[i].second;
		last_different[i]=last_of_kind[1-pole[i].first];
	}
	for(int i=pole.size()-1;i>=0;i--)
	{
		next_of_kind[pole[i].first]=pole[i].second;
		next_different[i]=next_of_kind[1-pole[i].first];
	}
	for(int i=0;i<pole.size();i++)
	{
		if(i==0)
		{
			best[i][0][0]=next_different[i]-pole[i].second;
			best[i][1][0]=pole[i].second-last_different[i];
			best[i][2][0]=best[i][0][0];
			best[i][0][1]=best[i][0][0];
			best[i][1][1]=best[i][1][0];
			best[i][2][1]=best[i][2][0];
		}
		else
		{
			if(pole[i].first==pole[i-1].first)
			{
				best[i][0][0]=mmin(best[i-1][2][0]+next_different[i]-pole[i].second,best[i-1][0][1]+pole[i].second-last_different[i]);
				best[i][1][0]=best[i-1][1][1]+pole[i].second-last_different[i];
				best[i][0][1]=mmin(best[i-1][2][1]+next_different[i]-pole[i].second,best[i-1][0][1]+pole[i].second-last_different[i]);
				best[i][1][1]=best[i][1][0];
			}
			else
			{
				best[i][0][0]=best[i-1][2][0]+next_different[i]-pole[i].second;
				best[i][1][0]=best[i-1][0][0];
				if(i==1)
				{
					best[i][0][1]=next_different[i]-pole[i].second;
					best[i][1][1]=pole[i].second-last_different[i];
				}
				else
				{
					if(pole[i].first==pole[i-2].first)
					{
						best[i][0][1]=best[i-2][2][0]+next_different[i]-pole[i].second;
						best[i][1][1]=best[i-2][2][0]+pole[i].second-last_different[i];
					}
					else
					{
						best[i][0][1]=best[i-2][2][0]+next_different[i]-pole[i].second;
						best[i][1][1]=best[i-2][0][0];
					}
				}
			}
			best[i][2][0]=mmin(best[i][0][0],best[i][1][0]);
			best[i][2][1]=mmin(best[i][0][1],best[i][1][1]);
		}
	}
	return best[pole.size()-1][2][0];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:24:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while((r_idx<r.size())||(b_idx<b.size()))
         ~~~~~^~~~~~~~~
wiring.cpp:24:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while((r_idx<r.size())||(b_idx<b.size()))
                           ~~~~~^~~~~~~~~
wiring.cpp:26:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(r_idx>=r.size())
      ~~~~~^~~~~~~~~~
wiring.cpp:30:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   else if(b_idx>=b.size())
           ~~~~~^~~~~~~~~~
wiring.cpp:54:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<pole.size();i++)
              ~^~~~~~~~~~~~
wiring.cpp:64:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<pole.size();i++)
              ~^~~~~~~~~~~~

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