Submission #782482

#	Time	Username	Problem	Language	Result	Execution time	Memory
782482		GusterGoose27	Ancient Books (IOI17_books)	C++17	50 / 100	109 ms	27588 KiB

books

#include "books.h"

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6+5;

typedef long long ll;
typedef pair<int, int> pii;
bool vis[MAXN];
int uf[MAXN];
pii range[MAXN];
// vector<int> in_comp[MAXN];
int par[MAXN];
// int dist[MAXN];

int n;

int _abs(int v) {
	return v < 0 ? -v : v;
}

int find(int i) {
	return uf[i] == i ? i : uf[i] = find(uf[i]);
}

void merge(int i, int j) {
	i = find(i);
	j = find(j);
	// if (i == j) return;
	assert(i != j);
	uf[i] = j;
	range[i].first = min(range[i].first, range[j].first);
	range[i].second = max(range[i].second, range[j].second);
}

ll minimum_walk(vector<int> p, int s) {
	ll ans = 0;
	n = p.size();
	for (int i = 0; i < n; i++) ans += _abs(p[i]-i);
	if (ans == 0) return 0;
	vector<pii> intervals;
	for (int i = 0; i < n; i++) {
		if (vis[i]) continue;
		int cur = i;
		int l = i, r = i;
		do {
			l = min(l, cur);
			r = max(r, cur);
			uf[cur] = i;
			// in_comp[i].push_back(cur);
			vis[cur] = 1;
			cur = p[cur];
		} while (cur != i);
		if (r > l || i == s) intervals.push_back(pii(l, r));
		range[i] = pii(l, r);
	}
	sort(intervals.begin(), intervals.end()); // they are probably already sorted
	// fill(dist, dist+n, MAXN);
	int curr = intervals[0].second;
	vector<int> stck;
	for (int i = 0; i < intervals.size(); i++) {
		while (!stck.empty() && stck.back() < intervals[i].first) {
			int v = stck.back(); stck.pop_back();
			if (stck.empty()) par[find(v)] = -1;
			else par[find(v)] = find(stck.back());
		}
		while (!stck.empty() && stck.back() < intervals[i].second) {
			int v = stck.back(); stck.pop_back();
			merge(v, intervals[i].second);
		}
		stck.push_back(intervals[i].second);
		// assert(curr != intervals[i].first);
		if (curr > intervals[i].first) {
			curr = max(curr, intervals[i].second);
			continue;
		}
		ans += 2*(intervals[i].first-curr);
		curr = intervals[i].second;
	}
	for (int i = 1; i < stck.size(); i++) par[find(stck[i])] = find(stck[i-1]);
	par[find(stck[0])] = -1;
	// return 0;
	int dist = 0;
	s = find(s);
	while (par[s] != -1) {
		int nxt = find(par[s]);
		dist += min(range[nxt].second-range[s].second, range[s].first-range[nxt].first);
		s = nxt;
	}
	return ans+2*dist;
}

Compilation message (stderr)

books.cpp: In function 'll minimum_walk(std::vector<int>, int)':
books.cpp:63:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |  for (int i = 0; i < intervals.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~~~
books.cpp:82:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |  for (int i = 1; i < stck.size(); i++) par[find(stck[i])] = find(stck[i-1]);
      |                  ~~^~~~~~~~~~~~~

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