Submission #140036

#	Time	Username	Problem	Language	Result	Execution time	Memory
140036		arthurconmy	Ancient Books (IOI17_books)	C++14	12 / 100	2092 ms	569220 KiB

books

#include <bits/stdc++.h>

#ifndef ARTHUR_LOCAL
	#include "books.h"
#endif

using namespace std;

using ll = long long;

bool vis[4][4][4][4][4][4]; // where person is, what carrying, what's in each place

map<vector<int>,vector<pair<vector<int>,bool>>> adj;

ll minimum_walk(vector<int> P, int s) 
{
	int n = P.size();

	vector<int> first_thing = {0,-1};

	for(auto p:P) first_thing.push_back(p);

	for(int w=0; w<n; w++)
	{
		for(int c=-1; c<n; c++)
		{
			vector<int> perm;
			for(int i=0; i<n; i++) perm.push_back(i);

			do
			{
				vector<int> cur = {w,c};
				for(auto p:perm) cur.push_back(p);

				// transition left

				if(w>0)
				{
					auto trans = cur;
					trans[0]=trans[0]-1;

					adj[cur].push_back(make_pair(trans,1));
					adj[trans].push_back(make_pair(cur,1));
				}

				if(w<n-1)
				{
					auto trans = cur;
					trans[0]=trans[0]+1;

					adj[cur].push_back(make_pair(trans,1));
					adj[trans].push_back(make_pair(cur,1));
				}

				// the pick up transition

				if(c==-1)
				{
					auto trans = cur;

					trans[1]=trans[2+trans[0]];

					adj[cur].push_back(make_pair(trans,0));
					adj[trans].push_back(make_pair(cur,0));
				}

				else
				{
					auto trans = cur;

					int pos=-69;

					for(int i=0; i<n; i++)
					{
						if(trans[i+2]==trans[1]) pos=i;
					}

					trans[1] = trans[2+trans[0]];
					trans[2+trans[0]] = cur[1];

					trans[2+pos] = cur[2+cur[0]];

					adj[cur].push_back(make_pair(trans,0));
					adj[trans].push_back(make_pair(cur,0));
				}

			} while(next_permutation(perm.begin(),perm.end()));
		}
	}

	// for(auto a:adj)
	// {
	// 	for(auto i:a.first) cout << i << " ";
	// 	cout << endl;

	// 	cout << a.second.size() << endl;
	// }

	priority_queue<pair<int,vector<int>>> PQ;

	map<vector<int>,int> dis;

	for(auto a:adj)
	{
		dis[a.first]=int(1e9);
	}

	PQ.push(make_pair(0,first_thing));

	while(!PQ.empty())
	{
		vector<int> cur = PQ.top().second;
		int cur_dis = - PQ.top().first;
		PQ.pop();

		//cout << "TRIGGERED" << endl;

		if(dis[cur]!=int(1e9)) continue;
		dis[cur]=cur_dis;

		//for(auto a:cur) cout << a << " ";
		//cout << endl << cur_dis << endl;

		for(auto u:adj[cur])
		{
			if(dis[u.first] != int(1e9)) continue;

			PQ.push(make_pair(-cur_dis-int(u.second),u.first));
		}
	}

	int ans=int(1e9);

	for(int w=0; w<1; w++)
	{
		int c=-1;

		vector<int> ending={w,c};
		for(int i=0; i<n; i++) ending.push_back(i);
	
		ans=min(ans,dis[ending]);
	}

	return ans;
	// cout << ans << endl;

	// vis[where][carry][state[2]][int(n>=2)*state[3%n]][int(n>=3)*state[4%n]][int(n>=4)*state[5%n]]=1; // ew...
}

#ifdef ARTHUR_LOCAL
	int main()
	{
		cout << minimum_walk({0,2,3,1},0) << endl;
	}
#endif

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