Submission #283226

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
283226	2020-08-25T11:39:21 Z	MohamedAhmed04	Ancient Books (IOI17_books)	C++14	12 / 100	2000 ms	407032 KB

books

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

using namespace std ;

const int inf = 1e9 ;
const int MAX = 1e6 + 10 ;

int n ;

int to[MAX] ;
int vis[MAX] ;
long long cost[MAX] ;

map< vector<int> , int>dist ;

long long minimum_walk(std::vector<int> p, int s) 
{
	n = p.size() ;
	vector<int>perm ;
	for(int i = 0 ; i < n ; ++i)
		perm.push_back(i) ;
	do
	{
		for(int i = 0 ; i < n ; ++i)
		{
			perm.push_back(i) ;
			dist[perm] = inf ;
			for(int j = 0 ; j < n ; ++j)
			{
				int a = perm[j] ;
				perm[j] = -1 ;
				dist[perm] = inf ;
				// for(auto &k : perm)
				// 	cout<<k<<" " ;
				// cout<<"\n" ;
				perm[j] = a ;
			}
			perm.pop_back() ;
		}
	}while(next_permutation(perm.begin() , perm.end())) ;
	priority_queue< pair<int , vector<int> > , vector< pair<int , vector<int> > > , greater< pair<int , vector<int> > > >q ;
	vector<int>st , need ;
	for(int i = 0 ; i < n ; ++i)
		st.push_back(i) ;
	need = st ;
	for(int i = 0 ; i < n ; ++i)
		need[p[i]] = i ;
	st.push_back(0) ;
	dist[st] = 0 ;
	q.push({0 , st}) ;
	while(q.size())
	{
		pair<int , vector<int> >pp = q.top() ;
		q.pop() ;
		vector<int>v = pp.second ;
		int cost = pp.first ;
		if(cost > dist[v])
			continue ;
		int pos = -1 ;
		for(int i = 0 ; i < n ; ++i)
		{
			if(v[i] == -1)
			{
				pos = i ;
				break ;
			}
		}
		if(pos == -1)
		{
			vector<int>v2 = v ;
			for(int i = 0 ; i < n ; ++i)
			{
				v2[i] = -1 ;
				v2[n] = i ;
				int cost2 = cost + abs(v.back() - i) ;
				if(cost2 < dist[v2])
				{
					dist[v2] = cost2 ;
					q.push({cost2 , v2}) ;
				}
				v2[i] = v[i] ;
				v2[n] = v[n] ;
			}
		}
		else
		{
			int x ;
			for(int i = 0 ; i < n ; ++i)
			{
				bool flag = false ;
				for(int j = 0 ; j < n ; ++j)
				{
					if(v[j] == i)
						flag = true ;
				}
				if(!flag)
					x = i ;
			}
			vector<int>v2 = v ;
			for(int i = 0 ; i < n ; ++i)
			{
				v2[i] = x ;
				v2[n] = i ;
				int cost2 = cost + abs(v.back() - i) ;
				if(cost2 < dist[v2])
				{
					dist[v2] = cost2 ;
					q.push({cost2 , v2}) ;
				}
				v2[i] = v[i] ;
				v2[n] = v[n] ;
			}
		}
	}
	int ans = inf ;
	for(int i = 0 ; i < n ; ++i)
	{
		need.push_back(i) ;
		ans = min(ans , dist[need] + i) ;
		need.pop_back() ;
	}
	return ans ;
}

Compilation message

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:104:11: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
  104 |     v2[i] = x ;

Subtask #1

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	0 ms	256 KB	Output is correct
12	Correct	1 ms	256 KB	Output is correct
13	Correct	1 ms	384 KB	Output is correct
14	Correct	1 ms	256 KB	Output is correct
15	Correct	2 ms	432 KB	Output is correct
16	Correct	2 ms	384 KB	Output is correct
17	Correct	1 ms	384 KB	Output is correct
18	Correct	1 ms	384 KB	Output is correct

Subtask #2

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	0 ms	256 KB	Output is correct
12	Correct	1 ms	256 KB	Output is correct
13	Correct	1 ms	384 KB	Output is correct
14	Correct	1 ms	256 KB	Output is correct
15	Correct	2 ms	432 KB	Output is correct
16	Correct	2 ms	384 KB	Output is correct
17	Correct	1 ms	384 KB	Output is correct
18	Correct	1 ms	384 KB	Output is correct
19	Execution timed out	2128 ms	407032 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-

Subtask #3

0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	0 ms	256 KB	Output is correct
12	Correct	1 ms	256 KB	Output is correct
13	Correct	1 ms	384 KB	Output is correct
14	Correct	1 ms	256 KB	Output is correct
15	Correct	2 ms	432 KB	Output is correct
16	Correct	2 ms	384 KB	Output is correct
17	Correct	1 ms	384 KB	Output is correct
18	Correct	1 ms	384 KB	Output is correct
19	Execution timed out	2128 ms	407032 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	2117 ms	404144 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	0 ms	256 KB	Output is correct
12	Correct	1 ms	256 KB	Output is correct
13	Correct	1 ms	384 KB	Output is correct
14	Correct	1 ms	256 KB	Output is correct
15	Correct	2 ms	432 KB	Output is correct
16	Correct	2 ms	384 KB	Output is correct
17	Correct	1 ms	384 KB	Output is correct
18	Correct	1 ms	384 KB	Output is correct
19	Execution timed out	2128 ms	407032 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-