oj.uz

답안 #283226

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
283226 2020-08-25T11:39:21 Z MohamedAhmed04 고대 책들 (IOI17_books) C++14
12 / 100
 2000 ms 407032 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2117 ms 404144 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 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 -