#include "books.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vii> vvii;
typedef vector<vll> vvll;
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;
#define ffor(i, a, b) for (ll i = (a); i < (ll)(b); i++)
#define fford(i, a, b) for (ll i = (a); i > (ll)(b); i--)
#define rep(i, n) ffor(i, 0, n)
#define forin(x, a) for (auto &x: a)
#define all(a) a.begin(), a.end()
long long minimum_walk(std::vector<int> p, int s) {
int n = p.size();
vii seen(n);
vpii segs = {{s, s}};
ll res = 0;
rep(i, n) {
if (!seen[i]) {
seen[i] = true;
int lo = i, hi = i;
res += abs(p[i] - i);
int curr = p[i];
while (curr != i) {
lo = min(lo, curr);
hi = max(hi, curr);
seen[curr] = true;
res += abs(curr - p[curr]);
curr = p[curr];
}
if (lo != hi)
segs.emplace_back(lo, hi);
}
}
sort(all(segs));
reverse(all(segs));
if (segs.empty()) return res;
vpii merged = {segs.back()};
segs.pop_back();
while (!segs.empty()) {
if (segs.back().first <= merged.back().second) {
merged.back().second = max(merged.back().second, segs.back().second);
} else {
merged.emplace_back(segs.back());
}
segs.pop_back();
}
rep(i, merged.size() - 1) {
res += (merged[i + 1].first - merged[i].second) * 2;
}
forin(seg, merged) {
if (seg.first < s && s < seg.second) {
rep(i, n) {
if (p[s + i] != s + i || p[s - i] != s - i) {
res += 2 * i;
break;
}
}
}
}
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
256 KB |
Output is correct |
| 7 |
Correct |
1 ms |
256 KB |
Output is correct |
| 8 |
Correct |
1 ms |
292 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
272 KB |
Output is correct |
| 11 |
Correct |
1 ms |
204 KB |
Output is correct |
| 12 |
Correct |
1 ms |
288 KB |
Output is correct |
| 13 |
Correct |
1 ms |
204 KB |
Output is correct |
| 14 |
Correct |
1 ms |
204 KB |
Output is correct |
| 15 |
Correct |
1 ms |
292 KB |
Output is correct |
| 16 |
Correct |
2 ms |
288 KB |
Output is correct |
| 17 |
Correct |
1 ms |
204 KB |
Output is correct |
| 18 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
256 KB |
Output is correct |
| 7 |
Correct |
1 ms |
256 KB |
Output is correct |
| 8 |
Correct |
1 ms |
292 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
272 KB |
Output is correct |
| 11 |
Correct |
1 ms |
204 KB |
Output is correct |
| 12 |
Correct |
1 ms |
288 KB |
Output is correct |
| 13 |
Correct |
1 ms |
204 KB |
Output is correct |
| 14 |
Correct |
1 ms |
204 KB |
Output is correct |
| 15 |
Correct |
1 ms |
292 KB |
Output is correct |
| 16 |
Correct |
2 ms |
288 KB |
Output is correct |
| 17 |
Correct |
1 ms |
204 KB |
Output is correct |
| 18 |
Correct |
1 ms |
204 KB |
Output is correct |
| 19 |
Correct |
1 ms |
204 KB |
Output is correct |
| 20 |
Correct |
1 ms |
204 KB |
Output is correct |
| 21 |
Correct |
1 ms |
296 KB |
Output is correct |
| 22 |
Correct |
2 ms |
204 KB |
Output is correct |
| 23 |
Correct |
1 ms |
204 KB |
Output is correct |
| 24 |
Correct |
1 ms |
204 KB |
Output is correct |
| 25 |
Correct |
1 ms |
204 KB |
Output is correct |
| 26 |
Correct |
1 ms |
204 KB |
Output is correct |
| 27 |
Correct |
2 ms |
204 KB |
Output is correct |
| 28 |
Correct |
1 ms |
292 KB |
Output is correct |
| 29 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
256 KB |
Output is correct |
| 7 |
Correct |
1 ms |
256 KB |
Output is correct |
| 8 |
Correct |
1 ms |
292 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
272 KB |
Output is correct |
| 11 |
Correct |
1 ms |
204 KB |
Output is correct |
| 12 |
Correct |
1 ms |
288 KB |
Output is correct |
| 13 |
Correct |
1 ms |
204 KB |
Output is correct |
| 14 |
Correct |
1 ms |
204 KB |
Output is correct |
| 15 |
Correct |
1 ms |
292 KB |
Output is correct |
| 16 |
Correct |
2 ms |
288 KB |
Output is correct |
| 17 |
Correct |
1 ms |
204 KB |
Output is correct |
| 18 |
Correct |
1 ms |
204 KB |
Output is correct |
| 19 |
Correct |
1 ms |
204 KB |
Output is correct |
| 20 |
Correct |
1 ms |
204 KB |
Output is correct |
| 21 |
Correct |
1 ms |
296 KB |
Output is correct |
| 22 |
Correct |
2 ms |
204 KB |
Output is correct |
| 23 |
Correct |
1 ms |
204 KB |
Output is correct |
| 24 |
Correct |
1 ms |
204 KB |
Output is correct |
| 25 |
Correct |
1 ms |
204 KB |
Output is correct |
| 26 |
Correct |
1 ms |
204 KB |
Output is correct |
| 27 |
Correct |
2 ms |
204 KB |
Output is correct |
| 28 |
Correct |
1 ms |
292 KB |
Output is correct |
| 29 |
Correct |
1 ms |
204 KB |
Output is correct |
| 30 |
Correct |
313 ms |
18644 KB |
Output is correct |
| 31 |
Correct |
216 ms |
18640 KB |
Output is correct |
| 32 |
Correct |
129 ms |
18640 KB |
Output is correct |
| 33 |
Correct |
188 ms |
23288 KB |
Output is correct |
| 34 |
Correct |
185 ms |
23236 KB |
Output is correct |
| 35 |
Correct |
214 ms |
23500 KB |
Output is correct |
| 36 |
Correct |
227 ms |
21628 KB |
Output is correct |
| 37 |
Correct |
136 ms |
19076 KB |
Output is correct |
| 38 |
Correct |
131 ms |
18756 KB |
Output is correct |
| 39 |
Correct |
137 ms |
18772 KB |
Output is correct |
| 40 |
Correct |
262 ms |
18756 KB |
Output is correct |
| 41 |
Correct |
175 ms |
18656 KB |
Output is correct |
| 42 |
Correct |
153 ms |
18756 KB |
Output is correct |
| 43 |
Correct |
168 ms |
20896 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '2744' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
256 KB |
Output is correct |
| 7 |
Correct |
1 ms |
256 KB |
Output is correct |
| 8 |
Correct |
1 ms |
292 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
272 KB |
Output is correct |
| 11 |
Correct |
1 ms |
204 KB |
Output is correct |
| 12 |
Correct |
1 ms |
288 KB |
Output is correct |
| 13 |
Correct |
1 ms |
204 KB |
Output is correct |
| 14 |
Correct |
1 ms |
204 KB |
Output is correct |
| 15 |
Correct |
1 ms |
292 KB |
Output is correct |
| 16 |
Correct |
2 ms |
288 KB |
Output is correct |
| 17 |
Correct |
1 ms |
204 KB |
Output is correct |
| 18 |
Correct |
1 ms |
204 KB |
Output is correct |
| 19 |
Correct |
1 ms |
204 KB |
Output is correct |
| 20 |
Correct |
1 ms |
204 KB |
Output is correct |
| 21 |
Correct |
1 ms |
296 KB |
Output is correct |
| 22 |
Correct |
2 ms |
204 KB |
Output is correct |
| 23 |
Correct |
1 ms |
204 KB |
Output is correct |
| 24 |
Correct |
1 ms |
204 KB |
Output is correct |
| 25 |
Correct |
1 ms |
204 KB |
Output is correct |
| 26 |
Correct |
1 ms |
204 KB |
Output is correct |
| 27 |
Correct |
2 ms |
204 KB |
Output is correct |
| 28 |
Correct |
1 ms |
292 KB |
Output is correct |
| 29 |
Correct |
1 ms |
204 KB |
Output is correct |
| 30 |
Correct |
313 ms |
18644 KB |
Output is correct |
| 31 |
Correct |
216 ms |
18640 KB |
Output is correct |
| 32 |
Correct |
129 ms |
18640 KB |
Output is correct |
| 33 |
Correct |
188 ms |
23288 KB |
Output is correct |
| 34 |
Correct |
185 ms |
23236 KB |
Output is correct |
| 35 |
Correct |
214 ms |
23500 KB |
Output is correct |
| 36 |
Correct |
227 ms |
21628 KB |
Output is correct |
| 37 |
Correct |
136 ms |
19076 KB |
Output is correct |
| 38 |
Correct |
131 ms |
18756 KB |
Output is correct |
| 39 |
Correct |
137 ms |
18772 KB |
Output is correct |
| 40 |
Correct |
262 ms |
18756 KB |
Output is correct |
| 41 |
Correct |
175 ms |
18656 KB |
Output is correct |
| 42 |
Correct |
153 ms |
18756 KB |
Output is correct |
| 43 |
Correct |
168 ms |
20896 KB |
Output is correct |
| 44 |
Incorrect |
1 ms |
204 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '2744' |
| 45 |
Halted |
0 ms |
0 KB |
- |
