oj.uz

Submission #594451

# Submission time Handle Problem Language Result Execution time Memory
594451 2022-07-12T13:13:41 Z FatihSolak Ancient Books (IOI17_books) C++17
12 / 100
 2000 ms 146932 KB 
#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.0 / 12.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 300 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 2 ms 296 KB Output is correct
16 Correct 1 ms 296 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Execution timed out 2068 ms 112996 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 300 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 2 ms 296 KB Output is correct
16 Correct 1 ms 296 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Execution timed out 2068 ms 112996 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 2083 ms 146932 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 300 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 2 ms 296 KB Output is correct
16 Correct 1 ms 296 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Execution timed out 2068 ms 112996 KB Time limit exceeded
20 Halted 0 ms 0 KB -