oj.uz

Submission #140036

# Submission time Handle Problem Language Result Execution time Memory
140036 2019-08-01T23:16:40 Z arthurconmy Ancient Books (IOI17_books) C++14
12 / 100
 2000 ms 569220 KB 
#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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 632 KB Output is correct
2 Correct 5 ms 632 KB Output is correct
3 Correct 4 ms 632 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 4 ms 632 KB Output is correct
6 Correct 4 ms 632 KB Output is correct
7 Correct 4 ms 632 KB Output is correct
8 Correct 5 ms 632 KB Output is correct
9 Correct 4 ms 632 KB Output is correct
10 Correct 3 ms 632 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 3 ms 396 KB Output is correct
13 Correct 5 ms 620 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 4 ms 636 KB Output is correct
16 Correct 5 ms 760 KB Output is correct
17 Correct 5 ms 632 KB Output is correct
18 Correct 4 ms 632 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 632 KB Output is correct
2 Correct 5 ms 632 KB Output is correct
3 Correct 4 ms 632 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 4 ms 632 KB Output is correct
6 Correct 4 ms 632 KB Output is correct
7 Correct 4 ms 632 KB Output is correct
8 Correct 5 ms 632 KB Output is correct
9 Correct 4 ms 632 KB Output is correct
10 Correct 3 ms 632 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 3 ms 396 KB Output is correct
13 Correct 5 ms 620 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 4 ms 636 KB Output is correct
16 Correct 5 ms 760 KB Output is correct
17 Correct 5 ms 632 KB Output is correct
18 Correct 4 ms 632 KB Output is correct
19 Execution timed out 2088 ms 569220 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 632 KB Output is correct
2 Correct 5 ms 632 KB Output is correct
3 Correct 4 ms 632 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 4 ms 632 KB Output is correct
6 Correct 4 ms 632 KB Output is correct
7 Correct 4 ms 632 KB Output is correct
8 Correct 5 ms 632 KB Output is correct
9 Correct 4 ms 632 KB Output is correct
10 Correct 3 ms 632 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 3 ms 396 KB Output is correct
13 Correct 5 ms 620 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 4 ms 636 KB Output is correct
16 Correct 5 ms 760 KB Output is correct
17 Correct 5 ms 632 KB Output is correct
18 Correct 4 ms 632 KB Output is correct
19 Execution timed out 2088 ms 569220 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2092 ms 567656 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 632 KB Output is correct
2 Correct 5 ms 632 KB Output is correct
3 Correct 4 ms 632 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 4 ms 632 KB Output is correct
6 Correct 4 ms 632 KB Output is correct
7 Correct 4 ms 632 KB Output is correct
8 Correct 5 ms 632 KB Output is correct
9 Correct 4 ms 632 KB Output is correct
10 Correct 3 ms 632 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 3 ms 396 KB Output is correct
13 Correct 5 ms 620 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 4 ms 636 KB Output is correct
16 Correct 5 ms 760 KB Output is correct
17 Correct 5 ms 632 KB Output is correct
18 Correct 4 ms 632 KB Output is correct
19 Execution timed out 2088 ms 569220 KB Time limit exceeded
20 Halted 0 ms 0 KB -