Submission #1048713

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048713		Gromp15	Ancient Books (IOI17_books)	C++17	70 / 100	400 ms	1048576 KiB

books

#include <bits/stdc++.h>
#include "books.h"
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
using namespace std;
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

template<typename op>
struct sparse_table {
	op x;
	vector<vector<int>> table;
	sparse_table(const vector<int>& a, op t) : table(__lg(sz(a)) + 1, vector<int>(sz(a))), x(t) {
		for (int i = 0; i < sz(a); i++) table[0][i] = a[i];
		for (int i = 1; i <= __lg(sz(a)); i++) {
			for (int j = 0; j < sz(a); j++) {
				if (j + (1 << i) - 1 >= sz(a)) break;
				table[i][j] = x(table[i-1][j], table[i-1][j+(1<<(i-1))]);
			}
		}
	}
	int query(int l, int r) {
		int h = __lg(r-l+1);
		return x(table[h][l], table[h][r-(1<<h)+1]);
	}
};
long long minimum_walk(std::vector<int> p, int s) {
	if (!s) {
		int n = p.size();
		vector<bool> vis(n);
		vector<long long> cost(n);
		vector<int> to(n);
		long long ans = 0;
		for (int i = 0; i < n; i++) if (i != p[i] && !vis[i]) {
			int right = i;
			int tmp = i;
			while (!vis[tmp]) {
				ckmax(right, tmp);
				ans += abs(tmp - p[tmp]), vis[tmp] = 1, tmp = p[tmp];
			}
			to[i] = right;
		}
		int on = 0;
		fill(all(vis), 0);
		for (int i = 0; i < n; i++) if (i != p[i] && !vis[i]) {
			int tmp = i;
			while (!vis[tmp]) vis[tmp] = 1, tmp = p[tmp];
			if (i <= on) ckmax(on, to[i]);
			else ans += 2 * (i - on), on = to[i];
		}
		return ans;
	}
	int n = p.size();
	vector<int> L(n), R(n);
	long long ans = 0;
	vector<bool> vis(n);
	for (int i = 0; i < n; i++) if (!vis[i]) {
		int right = i;
		int tmp = i;
		vector<int> cur;
		while (!vis[tmp]) {
			cur.emplace_back(tmp);
			ckmax(right, tmp);
			ans += abs(tmp - p[tmp]), vis[tmp] = 1, tmp = p[tmp];
		}
		for (int v : cur) L[v] = i, R[v] = right;
	}
	sparse_table mn(L, [&](int x, int y) { return min(x, y); });
	sparse_table mx(R, [&](int x, int y) { return max(x, y); });
	vector<vector<long long>> dp(n, vector<long long>(n, 1e18));
	dp[s][s] = 0;
	for (int len = 1; len < n; len++) {
		for (int l = 0; l+len-1 < n; l++) {
			int r = l+len-1;
			ckmin(dp[mn.query(l, r)][mx.query(l, r)], dp[l][r]);
			if (l) ckmin(dp[l-1][r], dp[l][r] + 2);
			if (r+1 < n) ckmin(dp[l][r+1], dp[l][r] + 2);
		}
	}
	int l = n, r = -1;
	for (int i = 0; i < n; i++) if (i != p[i]) ckmin(l, i), r = i;
	if (l == n) return 0;
	long long best = 1e18;
	for (int i = 0; i <= l; i++) for (int j = r; j < n; j++) ckmin(best, dp[i][j]);
	return best + ans;
}

Compilation message (stderr)

books.cpp: In instantiation of 'sparse_table<op>::sparse_table(const std::vector<int>&, op) [with op = minimum_walk(std::vector<int>, int)::<lambda(int, int)>]':
books.cpp:68:60:   required from here
books.cpp:12:22: warning: 'sparse_table<minimum_walk(std::vector<int>, int)::<lambda(int, int)> >::table' will be initialized after [-Wreorder]
   12 |  vector<vector<int>> table;
      |                      ^~~~~
books.cpp:11:5: warning:   'minimum_walk(std::vector<int>, int)::<lambda(int, int)> sparse_table<minimum_walk(std::vector<int>, int)::<lambda(int, int)> >::x' [-Wreorder]
   11 |  op x;
      |     ^
books.cpp:13:2: warning:   when initialized here [-Wreorder]
   13 |  sparse_table(const vector<int>& a, op t) : table(__lg(sz(a)) + 1, vector<int>(sz(a))), x(t) {
      |  ^~~~~~~~~~~~
books.cpp: In instantiation of 'sparse_table<op>::sparse_table(const std::vector<int>&, op) [with op = minimum_walk(std::vector<int>, int)::<lambda(int, int)>]':
books.cpp:69:60:   required from here
books.cpp:12:22: warning: 'sparse_table<minimum_walk(std::vector<int>, int)::<lambda(int, int)> >::table' will be initialized after [-Wreorder]
   12 |  vector<vector<int>> table;
      |                      ^~~~~
books.cpp:11:5: warning:   'minimum_walk(std::vector<int>, int)::<lambda(int, int)> sparse_table<minimum_walk(std::vector<int>, int)::<lambda(int, int)> >::x' [-Wreorder]
   11 |  op x;
      |     ^
books.cpp:13:2: warning:   when initialized here [-Wreorder]
   13 |  sparse_table(const vector<int>& a, op t) : table(__lg(sz(a)) + 1, vector<int>(sz(a))), x(t) {
      |  ^~~~~~~~~~~~

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