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>
#define fi first
#define se second
#define ryan bear
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef vector<int> vim;
int n; vim P;
int fr, re;
ll ret;
vector<pii> im, ar, fin;
ll minimum_walk(vim p, int s) {
n=p.size();
for (fr=0; fr<n&&p[fr]==fr; fr++) {}
for (re=n-1; re>=0&&p[re]==re; re--) {}
for (int i=0; i<n; i++) ret+=abs(p[i]-i);
if (!ret) return 0;
vim chk(1000010);
int mx;
for (int i=fr; i<=re; i++) {
if (chk[i]) continue;
mx=0;
for (int j=i; !chk[j]; j=p[j]) {
chk[j]=1;
mx=max(mx, j);
}
im.push_back({i, mx});
}
sort(im.begin(), im.end());
mx=0;
for (pii pi:im) {
if (pi.se<mx) continue;
mx=pi.se;
ar.push_back(pi);
}
for (int i=0; i<ar.size(); i++) {
fin.push_back({ar[i].fi, i});
fin.push_back({ar[i].se, i});
}
sort(fin.begin(), fin.end());
int l;
ll an1=0, an2=0;
for (l=0; l<fin.size(); l++) if (fin[l].fi>=s) break;
int lst=s;
fill(chk.begin(), chk.end(), 0);
for (int i=l; i<fin.size(); i++) {
if (chk[fin[i].se]) continue;
chk[fin[i].se]=1;
an1+=abs(fin[i].fi-lst);
lst=fin[i].fi;
}
for (int i=l-1; i>=0; i--) {
if (chk[fin[i].se]) continue;
chk[fin[i].se]=1;
an1+=abs(fin[i].fi-lst);
lst=fin[i].fi;
}
an1+=abs(lst-s);
lst=s;
fill(chk.begin(), chk.end(), 0);
for (int i=l-1; i>=0; i--) {
if (chk[fin[i].se]) continue;
chk[fin[i].se]=1;
an2+=abs(fin[i].fi-lst);
lst=fin[i].fi;
}
for (int i=l; i<fin.size(); i++) {
if (chk[fin[i].se]) continue;
chk[fin[i].se]=1;
an2+=abs(fin[i].fi-lst);
lst=fin[i].fi;
}
an2+=abs(lst-s);
return min(an1, an2)+ret;
}
Compilation message (stderr)
books.cpp: In function 'll minimum_walk(vim, int)':
books.cpp:46:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<ar.size(); i++) {
~^~~~~~~~~~
books.cpp:53:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (l=0; l<fin.size(); l++) if (fin[l].fi>=s) break;
~^~~~~~~~~~~
books.cpp:57:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=l; i<fin.size(); i++) {
~^~~~~~~~~~~
books.cpp:79:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=l; i<fin.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... |