Submission #1077469

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077469		Elias	Wiring (IOI17_wiring)	C++17	17 / 100	1090 ms	27452 KiB

wiring

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#ifdef _DEBUG
long long min_total_length(std::vector<int> r, std::vector<int> b);
#else
#include "wiring.h"
#endif

vector<pair<int, int>> all;
map<int, ll> mem;

/// @brief  Assume r is sorted backwards and b forwards
/// @param r
/// @param b
ll match(vector<int> r, vector<int> b)
{
	int n = r.size();
	int m = b.size();

	ll total = 0;

	for (int i = 0; i < max(n, m); i++)
	{
		ll x = r.back();
		ll y = b.back();

		total += abs(x - y);

		if (r.size() > 1)
			r.pop_back();
		if (b.size() > 1)
			b.pop_back();
	}

	return total;
}

long long solve(int i)
{
	if (mem.count(i))
		return mem[i];

	if (i == all.size())
		return mem[i] = 0;

	vector<int> r;
	vector<int> b;

	int index = i;
	while (index < all.size() && all[index].second == all[i].second)
	{
		r.push_back(all[index].first);
		index++;
	}

	reverse(r.begin(), r.end());

	ll result = INT64_MAX / 10;

	while (index < all.size() && all[index].second != all[i].second)
	{
		b.push_back(all[index].first);

		ll cost = match(r, b);
		result = min(result, cost + min(solve(index), solve(index + 1)));

		index++;
	}

	return mem[i] = result;
}

long long min_total_length(std::vector<int> r, std::vector<int> b)
{
	int n = r.size();
	int m = b.size();

	for (int i : r)
		all.push_back({i, -1});

	for (int i : b)
		all.push_back({i, 1});

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

	return solve(0);
}

#ifdef _DEBUG

int main()
{
	int n, m;
	assert(2 == scanf("%d %d", &n, &m));

	vector<int> r(n), b(m);
	for (int i = 0; i < n; i++)
		assert(1 == scanf("%d", &r[i]));
	for (int i = 0; i < m; i++)
		assert(1 == scanf("%d", &b[i]));

	long long res = min_total_length(r, b);
	printf("%lld\n", res);
	return 0;
}

#endif

Compilation message (stderr)

wiring.cpp: In function 'long long int solve(int)':
wiring.cpp:50:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  if (i == all.size())
      |      ~~^~~~~~~~~~~~~
wiring.cpp:57:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  while (index < all.size() && all[index].second == all[i].second)
      |         ~~~~~~^~~~~~~~~~~~
wiring.cpp:67:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  while (index < all.size() && all[index].second != all[i].second)
      |         ~~~~~~^~~~~~~~~~~~
wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:82:6: warning: unused variable 'n' [-Wunused-variable]
   82 |  int n = r.size();
      |      ^
wiring.cpp:83:6: warning: unused variable 'm' [-Wunused-variable]
   83 |  int m = b.size();
      |      ^

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