Submission #748838

#	Time	Username	Problem	Language	Result	Execution time	Memory
748838		wenqi	Ancient Books (IOI17_books)	C++17	0 / 100	1 ms	292 KiB

books

#include "books.h"
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>

using namespace std;
using ll = long long;

bool seen[1000005];
vector<int> P;
vector<int> t;

ll dfs(int i)
{
	if (seen[i])
		return 0;
	seen[i] = true;
	t.push_back(i);
	return abs(i - P[i]) + dfs(P[i]);
}

ll minimum_walk(vector<int> p, int s)
{
	P = p;
	ll sum = 0;
	int n = p.size();
	vector<vector<int>> q;
	multiset<int> ms;
	int mx = 0;
	priority_queue<pair<int, pair<int, int>>> pq;
	for (int i = 0; i < n; i++)
	{
		if (seen[i] or i == p[i])
			continue;
		t.clear();
		sum += dfs(i);
		sort(t.begin(), t.end());
		pq.push({-t[0], {q.size(), 0}});
		q.push_back(t);
		ms.insert(t[0]);
		mx = max(mx, t[0]);
	}
	if (q.empty())
		return sum;
	ll ans = 1e18;
	while (true)
	{
		auto [x, pr] = pq.top();
		auto [a, b] = pr;
		pq.pop();

		int w = *ms.begin();
		ans = min(ans, sum + 2 * max(0, s - w) + 2 * max(0, mx - s));

		if (q[a].size() - 1 == b)
			break;

		ms.erase(ms.find(-x));
		int h = q[a][++b];

		ms.insert(h);
		mx = max(mx, h);
		pq.push({-h, {a, b}});
	}
	return ans;
}

Compilation message (stderr)

books.cpp: In function 'll minimum_walk(std::vector<int>, int)':
books.cpp:56:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'std::tuple_element<1, std::pair<int, int> >::type' {aka 'int'} [-Wsign-compare]
   56 |   if (q[a].size() - 1 == b)
      |       ~~~~~~~~~~~~~~~~^~~~

• Subtask 1: 0 / 12
• Subtask 2: 0 / 10
• Subtask 3: 0 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30