#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
long long minimum_walk(vector<int> p, int s){
int n = (int)p.size();
ll ans = 0;
vector<int> cycle(n, -1);
vector<int> cmi, cma;
int numCycles = 0;
for(int i = 0; i < n; i++){
if(cycle[i] == -1 && p[i] != i){
int mi = i, ma = i;
int j = i;
do
{
mi = min(mi, j);
ma = max(ma, j);
cycle[j] = numCycles;
ans += abs(j-p[j]);
j = p[j];
}while(j != i);
numCycles++;
cmi.push_back(mi);
cma.push_back(ma);
}
}
int mi = s, ma = s;
int l = s, r = s;
vector<bool> vis(numCycles);
while(true){
int i = -1;
while(r <= ma){
if(cycle[r] != -1 && !vis[cycle[r]]){
i = r;
break;
}
else r++;
}
if(i == -1)
while(l >= mi){
if(cycle[l] != -1 && !vis[cycle[l]]){
i = l;
break;
}
else l--;
}
if(i == -1){
int costL = 2*n, costR = 2*n;
int candL = -1, candR = -1;
for(int j = l; j >= 0; j--){
if(cycle[j] != -1 && cma[cycle[j]] > ma){
costL = 2*(l+1-j);
candL = j;
break;
}
}
for(int j = r; j < n; j++){
if(cycle[j] != -1 && cmi[cycle[j]] < mi){
costR = 2*(j+1-r);
candR = j;
break;
}
}
if(costL < costR) i = candL;
else i = candR;
if(i != -1) ans += min(costL, costR);
if(i == -1){
int oldR = r, oldL = l;
while(r < n){
if(cycle[r] != -1 && !vis[cycle[r]]){
i = r;
ans += 2*(r+1-oldR);
break;
}
r++;
}
if(i == -1)
while(l >= 0){
if(cycle[l] != -1 && !vis[cycle[l]]){
i = l;
ans += 2*(oldL+1-l);
break;
}
l--;
}
}
}
if(i == -1) break;
vis[cycle[i]] = true;
mi = min(mi, cmi[cycle[i]]);
ma = max(ma, cma[cycle[i]]);
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Correct |
0 ms |
296 KB |
Output is correct |
| 14 |
Correct |
1 ms |
212 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| 16 |
Correct |
1 ms |
212 KB |
Output is correct |
| 17 |
Correct |
1 ms |
212 KB |
Output is correct |
| 18 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Correct |
0 ms |
296 KB |
Output is correct |
| 14 |
Correct |
1 ms |
212 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| 16 |
Correct |
1 ms |
212 KB |
Output is correct |
| 17 |
Correct |
1 ms |
212 KB |
Output is correct |
| 18 |
Correct |
1 ms |
212 KB |
Output is correct |
| 19 |
Correct |
1 ms |
212 KB |
Output is correct |
| 20 |
Correct |
1 ms |
272 KB |
Output is correct |
| 21 |
Correct |
1 ms |
212 KB |
Output is correct |
| 22 |
Correct |
1 ms |
296 KB |
Output is correct |
| 23 |
Correct |
1 ms |
212 KB |
Output is correct |
| 24 |
Correct |
1 ms |
212 KB |
Output is correct |
| 25 |
Correct |
1 ms |
212 KB |
Output is correct |
| 26 |
Correct |
1 ms |
212 KB |
Output is correct |
| 27 |
Correct |
1 ms |
212 KB |
Output is correct |
| 28 |
Correct |
1 ms |
212 KB |
Output is correct |
| 29 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Correct |
0 ms |
296 KB |
Output is correct |
| 14 |
Correct |
1 ms |
212 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| 16 |
Correct |
1 ms |
212 KB |
Output is correct |
| 17 |
Correct |
1 ms |
212 KB |
Output is correct |
| 18 |
Correct |
1 ms |
212 KB |
Output is correct |
| 19 |
Correct |
1 ms |
212 KB |
Output is correct |
| 20 |
Correct |
1 ms |
272 KB |
Output is correct |
| 21 |
Correct |
1 ms |
212 KB |
Output is correct |
| 22 |
Correct |
1 ms |
296 KB |
Output is correct |
| 23 |
Correct |
1 ms |
212 KB |
Output is correct |
| 24 |
Correct |
1 ms |
212 KB |
Output is correct |
| 25 |
Correct |
1 ms |
212 KB |
Output is correct |
| 26 |
Correct |
1 ms |
212 KB |
Output is correct |
| 27 |
Correct |
1 ms |
212 KB |
Output is correct |
| 28 |
Correct |
1 ms |
212 KB |
Output is correct |
| 29 |
Correct |
1 ms |
212 KB |
Output is correct |
| 30 |
Correct |
163 ms |
18764 KB |
Output is correct |
| 31 |
Correct |
153 ms |
18656 KB |
Output is correct |
| 32 |
Correct |
90 ms |
18764 KB |
Output is correct |
| 33 |
Execution timed out |
2045 ms |
20448 KB |
Time limit exceeded |
| 34 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '3586' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Correct |
0 ms |
296 KB |
Output is correct |
| 14 |
Correct |
1 ms |
212 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| 16 |
Correct |
1 ms |
212 KB |
Output is correct |
| 17 |
Correct |
1 ms |
212 KB |
Output is correct |
| 18 |
Correct |
1 ms |
212 KB |
Output is correct |
| 19 |
Correct |
1 ms |
212 KB |
Output is correct |
| 20 |
Correct |
1 ms |
272 KB |
Output is correct |
| 21 |
Correct |
1 ms |
212 KB |
Output is correct |
| 22 |
Correct |
1 ms |
296 KB |
Output is correct |
| 23 |
Correct |
1 ms |
212 KB |
Output is correct |
| 24 |
Correct |
1 ms |
212 KB |
Output is correct |
| 25 |
Correct |
1 ms |
212 KB |
Output is correct |
| 26 |
Correct |
1 ms |
212 KB |
Output is correct |
| 27 |
Correct |
1 ms |
212 KB |
Output is correct |
| 28 |
Correct |
1 ms |
212 KB |
Output is correct |
| 29 |
Correct |
1 ms |
212 KB |
Output is correct |
| 30 |
Correct |
163 ms |
18764 KB |
Output is correct |
| 31 |
Correct |
153 ms |
18656 KB |
Output is correct |
| 32 |
Correct |
90 ms |
18764 KB |
Output is correct |
| 33 |
Execution timed out |
2045 ms |
20448 KB |
Time limit exceeded |
| 34 |
Halted |
0 ms |
0 KB |
- |
