#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1'000'005;
int cyc[MAXN], lc[MAXN], rc[MAXN];
void extend(int &cl, int &cr, int tl, int tr){
while (cl > tl || cr < tr){
if (cl > tl){
cl--;
tl = min(tl, lc[cyc[cl]]); tr = max(tr, rc[cyc[cl]]);
}
else{
cr++;
tl = min(tl, lc[cyc[cr]]); tr = max(tr, rc[cyc[cr]]);
}
}
}
ll minimum_walk(vector<int> p, int s) {
int nums = p.size();
int mn = s, mx = s;
memset(cyc, -1, sizeof(cyc));
ll ans = 0;
for (int i = 0; i < nums; i++) ans += abs(i - p[i]);
for (int i = 0; i < nums; i++)
if (cyc[i] == -1){
int curr = i, l = i, r = i;
do{
cyc[curr] = i; l = min(l, curr); r = max(r, curr);
curr = p[curr];
} while (curr != i);
lc[i] = l; rc[i] = r;
if (p[i] != i){
mn = min(mn, l); mx = max(mx, r);
}
}
int cl = lc[cyc[s]], cr = rc[cyc[s]];
while (cl > mn || cr < mx){
int lnl = cl, lnr = cr, le = 0;
while (lnl > mn && lnr <= cr){
extend(lnl, lnr, lnl - 1, lnr);
le++;
}
int rnl = cl, rnr = cr, re = 0;
while (rnr < mx && rnl >= cl){
extend(rnl, rnr, rnl, rnr + 1);
re++;
}
if (lnl == rnl && lnr == rnr){ // cross the middle
ans += 2 * min(le, re);
cl = lnl; cr = lnr;
}
else{
ans += 2 * (le + re);
cl = lnl; cr = rnr;
}
}
return ans;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
7768 KB |
Output is correct |
| 2 |
Correct |
2 ms |
7768 KB |
Output is correct |
| 3 |
Correct |
2 ms |
7772 KB |
Output is correct |
| 4 |
Correct |
2 ms |
7924 KB |
Output is correct |
| 5 |
Correct |
2 ms |
7772 KB |
Output is correct |
| 6 |
Correct |
2 ms |
7772 KB |
Output is correct |
| 7 |
Correct |
2 ms |
7768 KB |
Output is correct |
| 8 |
Correct |
2 ms |
7772 KB |
Output is correct |
| 9 |
Correct |
2 ms |
7772 KB |
Output is correct |
| 10 |
Correct |
2 ms |
7768 KB |
Output is correct |
| 11 |
Correct |
2 ms |
7768 KB |
Output is correct |
| 12 |
Correct |
2 ms |
7772 KB |
Output is correct |
| 13 |
Correct |
2 ms |
7772 KB |
Output is correct |
| 14 |
Correct |
2 ms |
7772 KB |
Output is correct |
| 15 |
Correct |
2 ms |
8024 KB |
Output is correct |
| 16 |
Correct |
2 ms |
7772 KB |
Output is correct |
| 17 |
Correct |
2 ms |
7768 KB |
Output is correct |
| 18 |
Correct |
2 ms |
7772 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
7768 KB |
Output is correct |
| 2 |
Correct |
2 ms |
7768 KB |
Output is correct |
| 3 |
Correct |
2 ms |
7772 KB |
Output is correct |
| 4 |
Correct |
2 ms |
7924 KB |
Output is correct |
| 5 |
Correct |
2 ms |
7772 KB |
Output is correct |
| 6 |
Correct |
2 ms |
7772 KB |
Output is correct |
| 7 |
Correct |
2 ms |
7768 KB |
Output is correct |
| 8 |
Correct |
2 ms |
7772 KB |
Output is correct |
| 9 |
Correct |
2 ms |
7772 KB |
Output is correct |
| 10 |
Correct |
2 ms |
7768 KB |
Output is correct |
| 11 |
Correct |
2 ms |
7768 KB |
Output is correct |
| 12 |
Correct |
2 ms |
7772 KB |
Output is correct |
| 13 |
Correct |
2 ms |
7772 KB |
Output is correct |
| 14 |
Correct |
2 ms |
7772 KB |
Output is correct |
| 15 |
Correct |
2 ms |
8024 KB |
Output is correct |
| 16 |
Correct |
2 ms |
7772 KB |
Output is correct |
| 17 |
Correct |
2 ms |
7768 KB |
Output is correct |
| 18 |
Correct |
2 ms |
7772 KB |
Output is correct |
| 19 |
Incorrect |
2 ms |
7768 KB |
3rd lines differ - on the 1st token, expected: '338572', found: '338576' |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
7768 KB |
Output is correct |
| 2 |
Correct |
2 ms |
7768 KB |
Output is correct |
| 3 |
Correct |
2 ms |
7772 KB |
Output is correct |
| 4 |
Correct |
2 ms |
7924 KB |
Output is correct |
| 5 |
Correct |
2 ms |
7772 KB |
Output is correct |
| 6 |
Correct |
2 ms |
7772 KB |
Output is correct |
| 7 |
Correct |
2 ms |
7768 KB |
Output is correct |
| 8 |
Correct |
2 ms |
7772 KB |
Output is correct |
| 9 |
Correct |
2 ms |
7772 KB |
Output is correct |
| 10 |
Correct |
2 ms |
7768 KB |
Output is correct |
| 11 |
Correct |
2 ms |
7768 KB |
Output is correct |
| 12 |
Correct |
2 ms |
7772 KB |
Output is correct |
| 13 |
Correct |
2 ms |
7772 KB |
Output is correct |
| 14 |
Correct |
2 ms |
7772 KB |
Output is correct |
| 15 |
Correct |
2 ms |
8024 KB |
Output is correct |
| 16 |
Correct |
2 ms |
7772 KB |
Output is correct |
| 17 |
Correct |
2 ms |
7768 KB |
Output is correct |
| 18 |
Correct |
2 ms |
7772 KB |
Output is correct |
| 19 |
Incorrect |
2 ms |
7768 KB |
3rd lines differ - on the 1st token, expected: '338572', found: '338576' |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
7772 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '3308' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
7768 KB |
Output is correct |
| 2 |
Correct |
2 ms |
7768 KB |
Output is correct |
| 3 |
Correct |
2 ms |
7772 KB |
Output is correct |
| 4 |
Correct |
2 ms |
7924 KB |
Output is correct |
| 5 |
Correct |
2 ms |
7772 KB |
Output is correct |
| 6 |
Correct |
2 ms |
7772 KB |
Output is correct |
| 7 |
Correct |
2 ms |
7768 KB |
Output is correct |
| 8 |
Correct |
2 ms |
7772 KB |
Output is correct |
| 9 |
Correct |
2 ms |
7772 KB |
Output is correct |
| 10 |
Correct |
2 ms |
7768 KB |
Output is correct |
| 11 |
Correct |
2 ms |
7768 KB |
Output is correct |
| 12 |
Correct |
2 ms |
7772 KB |
Output is correct |
| 13 |
Correct |
2 ms |
7772 KB |
Output is correct |
| 14 |
Correct |
2 ms |
7772 KB |
Output is correct |
| 15 |
Correct |
2 ms |
8024 KB |
Output is correct |
| 16 |
Correct |
2 ms |
7772 KB |
Output is correct |
| 17 |
Correct |
2 ms |
7768 KB |
Output is correct |
| 18 |
Correct |
2 ms |
7772 KB |
Output is correct |
| 19 |
Incorrect |
2 ms |
7768 KB |
3rd lines differ - on the 1st token, expected: '338572', found: '338576' |
| 20 |
Halted |
0 ms |
0 KB |
- |
