Submission #1184483

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184483		alterio	Ancient Books (IOI17_books)	C++20	12 / 100	2106 ms	1114112 KiB

books

#include "books.h"
#include <bits/stdc++.h>

using namespace std;

map<pair<vector<int>, pair<int, int>>, int> memo;

int ans, START;

void solve(vector<int> p, int spot, int hold, int moves) {
	if (moves >= ans) return;
	if (memo.count({p, {spot, hold}}) && memo[{p, {spot, hold}}] <= moves) return;
	memo[{p, {spot, hold}}] = moves;
	bool ok = 1;
	for (int i = 0; i < p.size(); i++) if (p[i] != i) ok = 0;
	if (ok) {
		ans = min(ans, moves + abs(START - spot));
		return;
	}
	bool done = 0;
	if (p[spot] != spot) swap(p[spot], hold), done = 1;
	solve(p, spot, hold, moves);
	if (done) swap(p[spot], hold);
	if (spot - 1 >= 0) solve(p, spot - 1, hold, moves + 1);
	if (spot + 1 < p.size()) solve(p, spot + 1, hold, moves + 1);
}

long long minimum_walk(vector<int> p, int s) {
	START = s;
	ans = 1e9;
	solve(p, s, -1, 0);
	return ans;
}

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