Submission #601097

#	Time	Username	Problem	Language	Result	Execution time	Memory
601097		DanShaders	Ancient Books (IOI17_books)	C++17	22 / 100	97 ms	17604 KiB

books

//Cgrader.cpp
#include "books.h"
#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second
#define all(x) begin(x), end(x)
#define sz(x) ((int) (x).size())
using ll = long long;
using ld = long double;

const int N = 1e3 + 10, INF = 0x3f3f3f3f;

int cc[N], cnt[N], clef[N], crig[N];
pair<int, int> q[N][N];
int dp[N][N];

ll minimum_walk(vector<int> p, int s) {
	int rl = 0, rr = sz(p);
	while (rl < s) {
		if (p[rl] == rl) {
			++rl;
		} else {
			break;
		}
	}
	while (rr > s + 1) {
		if (p[rr - 1] == rr - 1) {
			--rr;
		} else {
			break;
		}
	}
	p = vector(begin(p) + rl, begin(p) + rr);
	s -= rl;
	for (int &u : p) {
		u -= rl;
	}

	int n = sz(p), m = 0;
	ll ans = 0;
	fill(all(cc), -1);
	for (int i = 0; i < n; ++i) {
		ans += abs(p[i] - i);
		if (cc[i] == -1) {
			clef[m] = crig[m] = i;
			int j = i;
			while (cc[j] == -1) {
				cc[j] = m;
				cnt[m]++;
				crig[m] = max(crig[m], j);
				j = p[j];
			}
			++m;
		}
	}
	for (int i = 0; i < n; ++i) {
		q[i][i] = {clef[cc[i]], crig[cc[i]]};
		for (int j = i + 1; j < n; ++j) {
			q[i][j].x = min(q[i][j - 1].x, clef[cc[j]]);
			q[i][j].y = max(q[i][j - 1].y, crig[cc[j]]);
		}
	}
	for (int len = n - 1; len > 0; --len) {
		for (int i = 0; i <= n - len; ++i) {
			int j = i + len - 1;
			if (q[i][j] != pair{i, j}) {
				// cout << "at " << i << " " << j << ", extending to " << q[i][j].x << " " << q[i][j].y << endl;
				dp[i][j] = dp[q[i][j].x][q[i][j].y];
			} else {
				dp[i][j] = +INF;
				if (i) {
					dp[i][j] = dp[i - 1][j];
				}
				if (j != n - 1) {
					dp[i][j] = min(dp[i][j], dp[i][j + 1] + 2);
				}
			}

		}
	}
	return ans + dp[s][s];
}

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