Submission #66644

#	Time	Username	Problem	Language	Result	Execution time	Memory
66644		Eae02	Wiring (IOI17_wiring)	C++14	30 / 100	1083 ms	11896 KiB

wiring

#include "wiring.h"

#include <bits/stdc++.h>

struct Section
{
	int connCount;
	const int* connPositions;
	uint64_t* memo;
};

std::vector<Section> sections;

uint64_t minLen(int sectIndex, int numWires)
{
	const Section& section = sections[sectIndex];
	if (section.memo[numWires] != 0)
		return section.memo[numWires];
	
	int toPrev = 0;
	if (sectIndex > 0)
		toPrev = section.connPositions[0] - sections[sectIndex - 1].connPositions[sections[sectIndex - 1].connCount - 1];
	
	uint64_t lMin = UINT64_MAX;
	if (sectIndex == sections.size() - 1)
	{
		lMin = (uint64_t)std::max(section.connCount - numWires, 0) * (uint64_t)toPrev;
		for (int i = 0; i < section.connCount; i++)
		{
			lMin += section.connPositions[i] - section.connPositions[0];
		}
	}
	else
	{
		int nextBegin = sections[sectIndex + 1].connPositions[0];
		
		uint64_t lp = 0;
		uint64_t ln = 0;
		for (int i = 0; i < section.connCount; i++)
			ln += nextBegin - section.connPositions[i];
		
		for (int b = 0; true; b++)
		{
			if (lp + ln < lMin)
			{
				uint64_t l = lp + ln + minLen(sectIndex + 1, section.connCount - b);
				lMin = std::min(lMin, l);
			}
			
			if (b == section.connCount || sectIndex == 0)
				break;
			
			ln -= nextBegin - section.connPositions[b];
			lp += section.connPositions[b] - section.connPositions[0];
			if (b >= numWires)
				lp += toPrev;
		}
	}
	
	section.memo[numWires] = lMin;
	return lMin;
}

uint64_t g_memo[5000000];

long long min_total_length(std::vector<int> r, std::vector<int> b)
{
	const int BLUE = 0;
	const int RED = 1;
	
	sections.reserve(r.size() + b.size());
	
	int sectionColor = -1;
	int ri = 0;
	int bi = 0;
	while (ri < r.size() || bi < b.size())
	{
		if ((ri == r.size() ? INT32_MAX : r[ri]) < (bi == b.size() ? INT32_MAX : b[bi]))
		{
			if (sectionColor != RED)
			{
				sections.emplace_back();
				sections.back().connCount = 0;
				sections.back().connPositions = &r[ri];
				sectionColor = RED;
			}
			ri++;
		}
		else
		{
			if (sectionColor != BLUE)
			{
				sections.emplace_back();
				sections.back().connCount = 0;
				sections.back().connPositions = &b[bi];
				sectionColor = BLUE;
			}
			bi++;
		}
		
		sections.back().connCount++;
	}
	
	uint64_t* memo = g_memo;
	int maxWires = 0;
	for (Section& section : sections)
	{
		section.memo = memo;
		memo += maxWires + 1;
		maxWires = section.connCount;
	}
	
	return minLen(0, 0);
}

Compilation message (stderr)

wiring.cpp: In function 'uint64_t minLen(int, int)':
wiring.cpp:25:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (sectIndex == sections.size() - 1)
      ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:76:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (ri < r.size() || bi < b.size())
         ~~~^~~~~~~~~~
wiring.cpp:76:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (ri < r.size() || bi < b.size())
                          ~~~^~~~~~~~~~
wiring.cpp:78:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if ((ri == r.size() ? INT32_MAX : r[ri]) < (bi == b.size() ? INT32_MAX : b[bi]))
        ~~~^~~~~~~~~~~
wiring.cpp:78:50: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if ((ri == r.size() ? INT32_MAX : r[ri]) < (bi == b.size() ? INT32_MAX : b[bi]))
                                               ~~~^~~~~~~~~~~

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