#include "books.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 11;
struct range{
int l, r;
bool extend(range rg){
bool changed = false;
if(rg.l < l) changed = true, l = rg.l;
if(rg.r > r) changed = true, r = rg.r;
return changed;
}
friend bool operator!= (const range& s, const range& t){
return s.l != t.l || s.r != t.r;
}
};
bool vis[MAXN];
range cyc[MAXN];
long long minimum_walk(vector<int> p, int s) {
int n = p.size();
bool all_eq = true;
for(int i = 0; i < n; i++) if(p[i] != i) all_eq = false;
if(all_eq) return 0;
int al = 0, ar = n - 1; while(p[al] == al) al++; while(p[ar] == ar) ar--;
long long ans = 0;
for(int i = 0; i < n; i++){
ans += abs(p[i] - i);
}
for(int i = 0; i < n; i++){
if(!vis[i]){
vector<int> c = {i}; int x = p[i]; range r = {i, i};
while(x != c[0]){
r.extend({x, x});
c.push_back(x);
vis[x] = true;
x = p[x];
}
for(auto j : c) cyc[j] = r;
}
}
for(int i = s - 1; i >= 0; i--){
cyc[i].extend(cyc[i + 1]);
}
for(int i = s + 1; i < n; i++){
cyc[i].extend(cyc[i - 1]);
}
{
range cur = cyc[s], nxt;
do{
nxt = cur;
nxt.extend(cyc[nxt.l]);
nxt.extend(cyc[nxt.r]);
}while(cur != nxt);
cyc[s] = nxt;
}
for(int i = s - 1; i >= 0; i--){
cyc[i].extend(cyc[i + 1]);
range cur = cyc[i], nxt;
do{
nxt = cur;
nxt.extend(cyc[nxt.l]);
nxt.extend(cyc[nxt.r]);
}while(cur != nxt);
cyc[i] = nxt;
}
for(int i = s + 1; i < n; i++){
cyc[i].extend(cyc[i - 1]);
range cur = cyc[i], nxt;
do{
nxt = cur;
nxt.extend(cyc[nxt.l]);
nxt.extend(cyc[nxt.r]);
}while(cur != nxt);
cyc[i] = nxt;
}
int c = 0;
while(cyc[c].r < ar){
c = cyc[c].r; ++c; ans += 2;
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
224 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 |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
312 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
1 ms |
212 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| 16 |
Correct |
0 ms |
212 KB |
Output is correct |
| 17 |
Correct |
0 ms |
212 KB |
Output is correct |
| 18 |
Correct |
0 ms |
312 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
224 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 |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
312 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
1 ms |
212 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| 16 |
Correct |
0 ms |
212 KB |
Output is correct |
| 17 |
Correct |
0 ms |
212 KB |
Output is correct |
| 18 |
Correct |
0 ms |
312 KB |
Output is correct |
| 19 |
Execution timed out |
2084 ms |
212 KB |
Time limit exceeded |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
224 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 |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
312 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
1 ms |
212 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| 16 |
Correct |
0 ms |
212 KB |
Output is correct |
| 17 |
Correct |
0 ms |
212 KB |
Output is correct |
| 18 |
Correct |
0 ms |
312 KB |
Output is correct |
| 19 |
Execution timed out |
2084 ms |
212 KB |
Time limit exceeded |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2062 ms |
212 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
224 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 |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
312 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
1 ms |
212 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| 16 |
Correct |
0 ms |
212 KB |
Output is correct |
| 17 |
Correct |
0 ms |
212 KB |
Output is correct |
| 18 |
Correct |
0 ms |
312 KB |
Output is correct |
| 19 |
Execution timed out |
2084 ms |
212 KB |
Time limit exceeded |
| 20 |
Halted |
0 ms |
0 KB |
- |
