#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}];
}
| # |
결과 |
실행 시간 |
메모리 |
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 |
| # |
결과 |
실행 시간 |
메모리 |
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 |
- |
| # |
결과 |
실행 시간 |
메모리 |
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 |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
2083 ms |
146932 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
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 |
- |
