Submission #41001

#	Time	Username	Problem	Language	Result	Execution time	Memory
41001		alenam0161	Ancient Books (IOI17_books)	C++14	50 / 100	232 ms	111888 KiB

books

#include "books.h"
#include <vector>
#include <algorithm>

using namespace std;
const int N = 1e6 + 7;
int group[N];
int mx[N];
bool used[N];
long long minimum_walk(std::vector<int> p, int s) {
	long long ans = 0;
	for (int i = 0; i < p.size(); ++i) {
		int to = i;
		if (used[to])continue;
		while (true) {
			group[to] = i;
			mx[i] = max(mx[i], to);
			ans += abs(p[to] - to);
			used[to] = true;
			if (used[p[to]])break;
			to = p[to];
		}
	}
	int Mx = 0;
	for (int i = 0; i < p.size(); ++i) {
		if (Mx == -1) { ans += 2; Mx = mx[i]; }
		else {
			Mx = max(Mx, mx[i]);
		}
		if (Mx == i)Mx = -1;
	}
	for (int i = p.size() - 1; i > 0; i--) { if (p[i] != i)break; ans -= 2; }

	return ans;
}

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:12:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < p.size(); ++i) {
                    ^
books.cpp:25:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < p.size(); ++i) {
                    ^

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