Submission #42877

#	Time	Username	Problem	Language	Result	Execution time	Memory
42877		MatheusLealV	Wiring (IOI17_wiring)	C++14	20 / 100	342 ms	165204 KiB

wiring

#include <bits/stdc++.h>
#define f first
#include "wiring.h"
#define s second
#define BLUE 1
#define RED 2
#define N 100005
#define inf 2000000000000000000LL
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;

ll n, m, r[N], b[N], dp[500][500];

ll custo(vector<int> esq, vector<int> dir)
{
	if(esq.empty() || dir.empty()) return inf;

	if(dir.back() < esq.front()) swap(esq, dir);

	if(esq.back() > dir.front()) return inf;

	ll sum_red = 0, sum_blue = 0;

	for(auto x: esq) sum_red -= x;

	for(auto x: dir) sum_blue += x;

	sum_red += esq.size()*((ll)esq.back()), sum_blue -= dir.size()*((ll)dir.front());

	return max(esq.size(), dir.size())*(dir.front() - esq.back()) + sum_blue + sum_red;
}

ll solve_greedy()
{
	vector< pii > val;

	for(int i = 1; i <= n; i++) val.push_back({r[i], BLUE});

	for(int i = 1; i <= m; i++) val.push_back({b[i], RED});

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

	int ini = 0, grp = 0, cnt = 0;

	vector< int > aux[N], split[N];

	vector< vector<int> > perf;

	for(int i = 0; i < val.size(); i++)
	{
		if(i == val.size() - 1 || val[i].s != val[i + 1].s)
		{
			for(int j = ini; j <= i; j++) aux[ grp ].push_back(val[j].f);

			grp ++;

			ini = i + 1;
		}
	}

	for(int i = 0; i < grp; i ++)
	{
		if(i == 0 || i == grp - 1) split[cnt] = (aux[i]), cnt ++;

		else
		{
			if(aux[i].size() % 2 == 0)
			{
				for(int j = 0; j < aux[i].size(); j++)
				{
					if(j < aux[i].size()/2) split[cnt].push_back(aux[i][j]);

					else split[cnt + 1].push_back(aux[i][j]);
				}

				if(split[cnt].empty() || split[cnt + 1].empty()) cnt --;

				cnt += 2;
			}
			else
			{
				if(split[cnt - 1].size() >= ceil( aux[i + 1].size()/2.0 ))
				{
					for(int j = 0; j < aux[i].size(); j++)
					{
						if(j <= aux[i].size()/2) split[cnt].push_back(aux[i][j]);

						else split[cnt + 1].push_back(aux[i][j]);
					}
				}

				else
				{
					for(int j = 0; j < aux[i].size(); j++)
					{
						if(j < aux[i].size()/2) split[cnt].push_back(aux[i][j]);

						else split[cnt + 1].push_back(aux[i][j]);
					}
				}

				if(split[cnt].empty() || split[cnt + 1].empty()) cnt --;

				cnt += 2;
			}
		}
	}

	ll sum = 0;

	for(int i = 0; i < cnt; i++) if(!split[i].empty()) perf.push_back(split[i]);

	for(int i = 0; i < perf.size() - 1; i++) sum += custo(perf[i], perf[i + 1]);

	return sum;
}

ll solve(int i, int j)
{
	if(!i && !j) return 0LL;

	if(!i || !j) return inf;

	if(dp[i][j] != -1) return dp[i][j];

	return dp[i][j] = min(solve(i - 1, j), min(solve(i, j - 1), solve(i - 1, j - 1))) + abs(r[i] - b[j]);
}

ll dp2[N][70], cnt;

map<int, int> mapa;

int pos[N][2];

ll solve2(int i, int j)
{
	if(!i && !j) return 0LL;

	if(!i || !j || (abs(pos[i][0] - pos[j][1]) > 20)) return inf;

	int dj = 21 + pos[i][0] - pos[j][1];

	if(dp2[i][dj] != -1) return dp2[i][dj];

	return dp2[i][dj] = min(solve2(i - 1, j), min(solve2(i, j - 1), solve2(i - 1, j - 1))) + abs(r[i] - b[j]);
}

ll min_total_length(vector<int> esq, vector<int> dir)
{
	n = esq.size(), m = dir.size();

	vector<int> all;

	for(int i = 1; i <= n; i++) r[i] = esq[i - 1], all.push_back(esq[i - 1]);

	for(int i = 1; i <= m; i++) b[i] = dir[i - 1], all.push_back(dir[i - 1]);

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

	for(int i = 0; i < all.size(); i++)
	{
		if(!mapa[all[i]]) mapa[all[i]] = ++cnt;
	}

	for(int i = 1; i <= n; i++) pos[i][0]= mapa[r[i]];

	for(int j = 1; j <= m; j++) pos[j][1] = mapa[b[j]];

	memset(dp, -1, sizeof dp);

	memset(dp2, -1, sizeof dp2);

	if(esq.back() < dir.front()) return custo(esq, dir);

	if(n <= 1000) return solve(n, m);

	return min(solve2(n, m), solve_greedy());
}

Compilation message (stderr)

wiring.cpp: In function 'll solve_greedy()':
wiring.cpp:50:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < val.size(); i++)
                   ^
wiring.cpp:52:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i == val.size() - 1 || val[i].s != val[i + 1].s)
        ^
wiring.cpp:70:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0; j < aux[i].size(); j++)
                      ^
wiring.cpp:72:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      if(j < aux[i].size()/2) split[cnt].push_back(aux[i][j]);
           ^
wiring.cpp:85:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int j = 0; j < aux[i].size(); j++)
                       ^
wiring.cpp:87:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(j <= aux[i].size()/2) split[cnt].push_back(aux[i][j]);
            ^
wiring.cpp:95:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int j = 0; j < aux[i].size(); j++)
                       ^
wiring.cpp:97:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(j < aux[i].size()/2) split[cnt].push_back(aux[i][j]);
            ^
wiring.cpp:114:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < perf.size() - 1; i++) sum += custo(perf[i], perf[i + 1]);
                   ^
wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:161:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < all.size(); i++)
                   ^

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