This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "books.h"
#include <iostream>
#define ll long long
using namespace std;
bool ok = 0;
vector <ll> p;
ll n, l, r, x, y, qx, qy, ql, qr, a, b, f = 0, mn = 0, mx = 0;
void branch() {
while (true) {
for (int i=x; i>=qx; --i) {
qx = min(qx, p[i]);
qy = max(qy, p[i]);
}
for (int i=y; i<=qy; ++i) {
qx = min(qx, p[i]);
qy = max(qy, p[i]);
}
if (x == qx && y == qy) break;
x = qx, y = qy;
}
}
long long minimum_walk(std::vector<int> A, int s) {
for (auto u : A) p.push_back(u);
n = p.size();
for (int i=0; i<n; ++i) {
f += abs(i-p[i]);
}
l = n, r = -1;
for (int i=0; i<n; ++i) {
if (p[i] != i) {
l = i;
break;
}
}
for (int i=n-1; i>=0; --i) {
if (p[i] != i) {
r = i;
break;
}
}
if (l == n) return 0;
x = y = qx = qy = s;
branch();
while (true) {
ok = a = b = 0;
mn = 1e18, mx = -1e18;
for (int i=x-1; i>=l; --i) {
qx = i;
mn = min(mn, (ll)p[i]);
if (p[i] > y) {
a += 2;
ok = 1;
break;
}
if (mn == i) a += 2;
}
for (int i=y+1; i<=r; ++i) {
qy = i;
mx = max(mx, (ll)p[i]);
if (p[i] < x) {
b += 2;
break;
}
if (mx == i) b += 2;
}
if (!ok) {
f += a + b;
break;
}
else {
f += min(a, b);
branch();
}
}
return f;
}
Compilation message (stderr)
books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:47:10: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
47 | ok = a = b = 0;
| ~~^~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |