#include "books.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using pi = pair<int, int>;
typedef long long ll;
struct state {
int hold, pos; string arr;
vi hist;
state(int hold, int pos, string arr) : hold(hold), pos(pos), arr(arr) {}
const bool operator<(const state &other) const {
if (arr != other.arr) return arr < other.arr;
if (hold != other.hold) return hold < other.hold;
return pos < other.pos;
}
};
ll brute(vi p, int s) {
int n = p.size();
string target = ""; for (int i = 0; i < n; i++) target += 'a' + i;
string start = ""; for (auto i : p) start += 'a' + i;
state begin(-1, s, start);
priority_queue<pair<int, state>, vector<pair<int, state>>, greater<pair<int, state>>> q; set<state> seen;
q.push({0, begin}); seen.insert(begin);
ll ans = -1;
while (!q.empty()) {
int moves = q.top().first; auto st = q.top().second;
q.pop();
// cout << "moves: " << moves << " arr: " << st.arr << " pos: " << st.pos << " hold: " << st.hold << "\n";
if (st.arr == target && st.pos == s && st.hold == -1) {
ans = moves;
vi hist = st.hist;
for (auto e : hist) {
if (e == 0) {
cout << "R";
} else if (e == 1) {
cout << "L";
} else if (e == 2) {
cout << "S";
}
}
break;
}
string ifswap = st.arr; int h2 = st.hold;
if (st.hold != -1) {
ifswap[st.pos] = 'a' + st.hold;
if (st.arr[st.pos] == '#') h2 = -1;
else h2 = st.arr[st.pos] - 'a';
} else {
ifswap[st.pos] = '#';
h2 = st.arr[st.pos] - 'a';
}
auto st2 = state(h2, st.pos, ifswap);
st2.hist = st.hist; st2.hist.push_back(2);
if (!seen.count(st2)) seen.insert(st2), q.push({moves, st2});
if (st.pos < n-1) {
auto st1 = state(st.hold, st.pos+1, st.arr);
st1.hist = st.hist; st1.hist.push_back(0);
if (!seen.count(st1)) seen.insert(st1), q.push({moves+1, st1});
}
if (st.pos > 0) {
auto st1 = state(st.hold, st.pos-1, st.arr);
st1.hist = st.hist; st1.hist.push_back(1);
if (!seen.count(st1)) seen.insert(st1), q.push({moves+1, st1});
}
}
cout << "\n";
return ans;
}
/*
(1) it is absolutely forced to pay at least Σ|p[i] - i| for all i, that is the cost of moving every element into the right spot
(2) note that every permutation cycle should just be followed. the `range` of a cycle = {coord of first el, coord of last el}
if we encounter another cycle that overlaps with our current one, we can follow it for free, because we would have to do it
anyways, AND following it puts us back in the exact same spot, so we don't even notice the interruption
(3) so this implies that every overlapping range can be merged (s=0 subtasks), and then the cost is only the cost of travelling between
disconnected cycles. cost for that = 2*[R[j]-L[i]], because have to walk backwards again (s=0). now. this directly solves the s=0 cases,
worth 50/100
(4) for arbitrary s, first note that the "active range" of the permutation is [x,y] where x is the first index where p[i] != i, and y is the last
clearly if s is outside of the active range, we need to walk into it and then back out of it. so ans += 2*min(|La - s|, |Ra - s|)
you want to determine the cost of merging all cycles within the active range. so. set your borders to [s, s]. while leftmost[L] < L
L--, and while (rightmost[R]) > R: R++. now try and expand outside of your range. you are looking for a cycle on the left that
extends past R, or one on the right that extends past L. if you find one on either side, pay 2*min(left dist, right dist). if you
only find one, pay 2*(dist). if you find none, pay 2*(left+right) and terminate
*/
struct SegTree {
int n;
vi minL, maxR;
SegTree(int n) : n(n), minL(4 * n), maxR(4 * n) {}
void build(int node, int start, int end, const vi& L, const vi& R) {
if (start == end) {
minL[node] = L[start];
maxR[node] = R[start];
return;
}
int mid = (start + end) / 2;
build(2 * node, start, mid, L, R);
build(2 * node + 1, mid + 1, end, L, R);
minL[node] = min(minL[2 * node], minL[2 * node + 1]);
maxR[node] = max(maxR[2 * node], maxR[2 * node + 1]);
}
pi query(int node, int start, int end, int l, int r) {
if (r < start || end < l) return {int(1e9), int(-1e9)};
if (l <= start && end <= r) return {minL[node], maxR[node]};
int mid = (start + end) / 2;
pi p1 = query(2 * node, start, mid, l, r);
pi p2 = query(2 * node + 1, mid + 1, end, l, r);
return {min(p1.first, p2.first), max(p1.second, p2.second)};
}
pi expand(int l, int r) {
while (true) {
pi res = query(1, 0, n - 1, l, r);
if (res.first == l && res.second == r) break;
l = res.first; r = res.second;
}
return {l, r};
}
};
ll test(vi p, int s) {
int n = p.size();
ll ans = 0; for (int i = 0; i < n; i++) ans += abs(i-p[i]);
int fl = 0, fr = n-1;
while (fl < n && p[fl] == fl) fl++;
while (fr >= 0 && p[fr] == fr) fr--;
if (fl >= n || fr < 0) return 0;
if (s <= fl) ans += 2*abs(fl-s), s = fl;
else if (fr <= s) ans += 2*abs(fr-s), s = fr;
vi checked(n, 0);
vi left(n), right(n);
for (int i = 0; i < n; i++) {
if (checked[i]) continue;
int L = i, R = i, x = i;
vi cycle;
while (!checked[x]) {
checked[x] = 1; cycle.push_back(x);
L = min(L, x); R = max(R, x);
x = p[x];
}
for (int node : cycle) { left[node] = L; right[node] = R; }
}
SegTree st(n);
st.build(1, 0, n - 1, left, right);
pi start_range = st.expand(s, s);
int L = start_range.first, R = start_range.second;
while (!(L <= fl && R >= fr)) {
int xl = L, xr = R, costl = 0; bool foundx = false;
while (xl > fl && xr <= R) {
xl--; costl += 2;
pi range = st.expand(xl, xr);
xl = range.first; xr = range.second;
foundx = xr > R;
}
int yl = L, yr = R, costr = 0; bool foundy = false;
while (yr < fr && yl >= L) {
yr++; costr += 2;
pi range = st.expand(yl, yr);
yl = range.first; yr = range.second;
foundy = yl < L;
}
if (foundx && foundy) {
ans += min(costl, costr);
L = min(xl, yl), R = max(xr, yr);
} else if (foundx) {
ans += costl, L = xl, R = xr;
} else if (foundy) {
ans += costr, L = yl, R = yr;
} else {
ans += costl, L = fl;
ans += costr, R = fr;
}
}
return ans;
}
ll minimum_walk(vi p, int s) {
return test(p, s);
// return brute(p, s);
// vector<int> perm(4); iota(perm.begin(), perm.end(), 0);
// do {
// int a = brute(perm, 2), b = test(perm, 2);
// if (a != b) {
// cout << "FAILED: on n = 4, s = 0, p = "; for (auto e : perm) cout << e << " "; cout << "\n";
// cout << "brute: " << a << " test: " << b << "\n";
// }
// } while (next_permutation(perm.begin(), perm.end()));
// return brute(p, s);
}
