Submission #594451

#	Time	Username	Problem	Language	Result	Execution time	Memory
594451		FatihSolak	Ancient Books (IOI17_books)	C++17	12 / 100	2083 ms	146932 KiB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;
map<pair<vector<int>,int>,int> mp;
map<pair<vector<int>,int>,bool> vis;
int n;
long long minimum_walk(vector<int> p, int s) {
	n = p.size();
	deque<pair<vector<int>,int>> q;
	q.push_front({p,0});
	mp[{p,0}] = 0;
	while(q.size()){
		auto tp = q.front();
		q.pop_front();
		if(vis[tp])continue;
		vis[tp] = 1;
		auto p = tp.first;
		auto pos = tp.second;
		int cost = mp[{p,pos}];
		set<int> hand;
		for(int i = -1;i<n;i++){
			hand.insert(i);
		}
		for(auto u:p){
			hand.erase(u);
		}
		int on_hand = *hand.begin();
		if(pos + 1 != n && (!mp.count({p,pos+1}) || mp[{p,pos+1}] > cost + 1)){
			q.push_back({p,pos+1});
			mp[{p,pos+1}] = cost + 1;
		}
		if(pos - 1 != -1 && (!mp.count({p,pos-1}) || mp[{p,pos-1}] > cost + 1)){
			q.push_back({p,pos-1});
			mp[{p,pos-1}] = cost + 1;
		}
		swap(p[pos],on_hand);
		if(!mp.count({p,pos}) || mp[{p,pos}] > cost){
			q.push_front({p,pos});
			mp[{p,pos}] = cost;
		}
	}
	vector<int> v;
	for(int i = 0;i<n;i++){
		v.push_back(i);
	}
	return mp[{v,s}];
}

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