#include <bits/stdc++.h> using namespace std; #define rep(i,a,b) for (int i = (a); i < (b); i++) #define pb push_back typedef long long ll; typedef pair<int, int> pii; #include "books.h" long long minimum_walk(std::vector<int> p, int s) { cerr << "hi " << s << "\n"; int cycles = 0; vector<int> cycle(p.size(), -1); vector<pii> lohi; ll base = 0; rep(i,0,p.size()) { if (p[i] == i) cycle[i] = -1; else if (cycle[i] == -1) { cycle[i] = cycles; base += abs(i - p[i]); int at = p[i], low = i, high = i; while (at != i) { if (at < low) low = at; if (at > high) high = at; base += abs(at - p[at]); cycle[at] = cycles; at = p[at]; } lohi.pb(make_pair(low, high)); cycles++; } } ll add = 0; if (s == 0) { int low = 0, high = 0; // inc //int ind = 0; rep(i,0,cycle.size()) { if (cycle[i] == -1) continue; if (i > high) add += (i - high) * 2; high = max(high, lohi[cycle[i]].second); } } else { cerr << "else\n"; vector<int> closest(cycle.size(), -1); if (cycle[0] == -1) closest[0] = -1; else closest[0] = 0; rep(i,1,s) { if (cycle[i] == -1) closest[i] = closest[i - 1]; else closest[i] = i; } if (cycle[cycle.size() - 1] == -1) closest[cycle.size() - 1] = -1; else closest[cycle.size() - 1] = cycle.size() - 1; for (int i = cycle.size() - 2; i > s; i--) // -2 !! { if (cycle[i] == -1) closest[i] = closest[i + 1]; else closest[i] = i; } cerr << "closest: "; rep(i,0,closest.size()) { cerr << closest[i] << " "; } cerr << "\n"; // edges int low = s, high = s; if (cycle[s] != -1) { low = lohi[cycle[s]].first; high = lohi[cycle[s]].second; } while (low > 0 || high < cycle.size() - 1) { int go; if (low > 0 && high < cycle.size() - 1) { if (closest[low - 1] == -1) { low = 0; continue; } if (closest[high + 1] == -1) { high = cycle.size() - 1; continue; } if (low - closest[low - 1] < closest[high + 1] - high) { go = closest[low - 1]; add += (low - closest[low - 1]) * 2; } else { go = closest[high + 1]; add += (closest[high + 1] - high) * 2; } } else if (high < cycle.size() - 1) { if (closest[high + 1] == -1) { high = cycle.size() - 1; continue; } go = closest[high + 1]; add += (closest[high + 1] - high) * 2; } else // low > 0 { if (closest[low - 1] == -1) { low = 0; continue; } go = closest[low - 1]; add += (low - closest[low - 1]) * 2; cerr << "add add " << low << " " << closest[low - 1] << " " << (low - closest[low - 1]) * 2 << "\n"; } low = min(low, lohi[cycle[go]].first); high = max(high, lohi[cycle[go]].second); } } ll ans = base + add; cerr << ans << "\n"; return ans; }

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:4:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(i,a,b) for (int i = (a); i < (b); i++)
      |                                        ^
books.cpp:22:2: note: in expansion of macro 'rep'
   22 |  rep(i,0,p.size())
      |  ^~~
books.cpp:4:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(i,a,b) for (int i = (a); i < (b); i++)
      |                                        ^
books.cpp:55:3: note: in expansion of macro 'rep'
   55 |   rep(i,0,cycle.size())
      |   ^~~
books.cpp:53:7: warning: unused variable 'low' [-Wunused-variable]
   53 |   int low = 0, high = 0; // inc
      |       ^~~
books.cpp:4:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(i,a,b) for (int i = (a); i < (b); i++)
      |                                        ^
books.cpp:89:3: note: in expansion of macro 'rep'
   89 |   rep(i,0,closest.size())
      |   ^~~
books.cpp:104:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |   while (low > 0 || high < cycle.size() - 1)
      |                     ~~~~~^~~~~~~~~~~~~~~~~~
books.cpp:108:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |    if (low > 0 && high < cycle.size() - 1)
      |                   ~~~~~^~~~~~~~~~~~~~~~~~
books.cpp:133:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |    else if (high < cycle.size() - 1)
      |             ~~~~~^~~~~~~~~~~~~~~~~~