#include <iostream>
#include <vector>
#include "books.h"
using namespace std;
typedef vector<int> vi;
void extend(int &l, int &r, vi C, vi L, vi R){
int ll = l, rr = r;
ll = min(ll, min(L[C[l]], L[C[r]]));
rr = max(rr, max(R[C[l]], R[C[r]]));
while(ll < l || r < rr){
if (ll < l){ // sve dok ll "bjezi" tj dok se nalazi min smanjivat ce se i l
l--; // l == ll kad ne mogne dalje tj kad L[C[l]] dodje do najljevljeg moguceg
ll = min(ll, L[C[l]]);
rr = max(rr, R[C[l]]);
}
else{
r++;
ll = min(ll, L[C[r]]);
rr = max(rr, R[C[r]]);
}
}
}
int connect(int l, int r, int target_l, int target_r, vi &C, vi &L, vi &R){
int cost = 0;
do{
extend(l, r, C, L, R);
bool next_l = false;
int cost_l = 0;
int l_l = l, r_l = r;
while(true){
if (l_l <= target_l)
break;
l_l--;
cost_l += 2;
extend(l_l, r_l, C, L, R);
if (r_l > r){
next_l = true;
break;
}
}
bool next_r = false;
int cost_r = 0;
int l_r = l, r_r = r;
while(true){
if (r_r >= target_r)
break;
r_r++;
cost_r += 2;
extend(l_r, r_r, C, L, R);
if (l_r < l){
next_r = true;
break;
}
}
assert(!(next_l xor next_r));
if (next_l && next_r)
cost += min(cost_l, cost_r);
else
cost += cost_l + cost_r;
l = min(l_l, l_r);
r = max(r_l, r_r);
}while(l > target_l || r < target_r);
return cost;
}
long long booksort(int n, int s, vector<int> order){
long long res = 0;
vector<int> C(n, -1), L(n), R(n);
int l = s, r = s;
int c = 0;
for (int i = 0; i < n; i++){
res += abs(i - order[i]);
if (C[i] == -1){
L[c] = i; R[c] = i;
int j = i;
do{
C[j] = c;
R[c] = max(R[c], j);
j = order[j];
}while(i != j);
if (i != order[i]){
l = min(l, L[c]);
r = max(r, R[c]);
}
c++;
}
}
return res + connect(s, s, l, r, C, L, R);
}
long long minimum_walk(vi order, int s){
int n = order.size();
return booksort(n, s, order);
}
Compilation message
books.cpp: In function 'int connect(int, int, int, int, vi&, vi&, vi&)':
books.cpp:61:9: error: 'assert' was not declared in this scope
61 | assert(!(next_l xor next_r));
| ^~~~~~
books.cpp:4:1: note: 'assert' is defined in header '<cassert>'; did you forget to '#include <cassert>'?
3 | #include "books.h"
+++ |+#include <cassert>
4 |
