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 <bits/stdc++.h>
using namespace std;
#define MAX 1010101
typedef pair<int, int> pii;
typedef long long ll;
int p[MAX];
ll ans = 0;
int N;
vector<vector<int>> cyc;
int cycnt;
int vis[MAX];
int chk[MAX];
int prt[MAX];
int lv[MAX];
int rv[MAX];
vector<int> adj[MAX];
vector<int> lst;
int s;
void dfs(int x) {
lst.push_back(x);
for (auto v : adj[x]) if (lv[v] <= s && s <= rv[v]) dfs(v);
}
long long minimum_walk(std::vector<int> p, int _s) {
s = _s;
N = p.size();
int i;
for (i = 0; i < N; i++) if (i != p[i]) break;
int er = i;
if (i == N) return 0;
int fcnt = 0;
for (; i < N; i++) p[fcnt++] = p[i] - er;
s -= er;
if (s < 0) ans += 2ll * (-s), s = 0;
N = fcnt;
p.resize(N);
while ((p.back() + 1) == (int)p.size()) p.pop_back();
N = p.size();
if (s >= N) ans += 2ll * (s - N + 1), s = N - 1;
for (i = 0; i < N; i++) ans += abs(p[i] - i);
for (i = 0; i < N; i++) {
if (vis[i]) continue;
vector<int> vlist;
int v = i;
while (!vis[v]) {
vis[v] = 1;
vlist.push_back(v);
v = p[v];
}
cycnt++;
cyc.push_back(vlist);
}
vector<pair<pii, int>> vpi;
int X = cyc.size();
for (auto& v : cyc) {
sort(v.begin(), v.end());
vpi.emplace_back(pii(v[0], v.back()), 0);
}
i = 0;
for (auto& [_, x] : vpi) x = i++;
sort(vpi.begin(), vpi.end());
vector<pair<pii, int>> stk;
for (i = 0; i < vpi.size(); i++) {
while (stk.size() && stk.back().first.second < vpi[i].first.first) stk.pop_back();
vector<int> er;
int t = -1;
while (stk.size() && vpi[i].first.first <= stk.back().first.second && stk.back().first.second <= vpi[i].first.second) {
er.push_back(stk.back().second);
stk.pop_back();
}
if (er.size()) {
t = er.back();
er.pop_back();
er.push_back(i);
for (auto x : er) {
chk[x] = 1;
if (cyc[t].size() < cyc[x].size()) swap(cyc[t], cyc[x]);
for (auto v : cyc[x]) cyc[t].push_back(v);
}
stk.emplace_back(pii(cyc[t][0], vpi[i].first.second), t);
}
else {
if (stk.empty()) prt[i] = -1;
else prt[i] = stk.back().second;
stk.push_back(vpi[i]);
}
}
vector<int> all;
for (i = 0; i < X; i++) {
if (!chk[i]) {
sort(cyc[i].begin(), cyc[i].end());
lv[i] = cyc[i][0];
rv[i] = cyc[i].back();
if (~prt[i]) adj[prt[i]].push_back(i);
}
}
for (i = 0; i < cyc.size(); i++) if (!~prt[i]) all.push_back(i);
for (i = 1; i < all.size(); i++) ans += 2ll * (lv[all[i]] - rv[all[i - 1]]);
int rt = -1;
for (auto v : all) {
if (lv[v] <= s && s <= rv[v]) {
rt = v;
break;
}
}
dfs(rt);
set<int> st;
for (auto v : cyc[lst[0]]) st.insert(v);
for (i = 1; i < lst.size(); i++) {
auto ind = st.lower_bound(lv[lst[i]]);
int c;
if (ind == st.end()) c = 0;
else if (*ind <= rv[lst[i]]) c = 1;
else c = 0;
if (!c) {
ind = st.lower_bound(lv[lst[i]]);
int mn = 2e9;
if (ind != st.begin()) {
ind--;
mn = min(mn, abs(*ind - lv[lst[i]]));
}
ind = st.upper_bound(rv[lst[i]]);
if (ind != st.end()) mn = min(mn, abs(*ind - rv[lst[i]]));
ans += 2ll * mn;
}
for (auto v : cyc[lst[i]]) st.insert(v);
}
return ans;
}
Compilation message (stderr)
books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:64:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for (i = 0; i < vpi.size(); i++) {
| ~~^~~~~~~~~~~~
books.cpp:98:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for (i = 0; i < cyc.size(); i++) if (!~prt[i]) all.push_back(i);
| ~~^~~~~~~~~~~~
books.cpp:99:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for (i = 1; i < all.size(); i++) ans += 2ll * (lv[all[i]] - rv[all[i - 1]]);
| ~~^~~~~~~~~~~~
books.cpp:110:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | for (i = 1; i < lst.size(); i++) {
| ~~^~~~~~~~~~~~
# | 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... |