#include <bits/stdc++.h>
#include "books.h"
using namespace std;
typedef long long ll;
vector<ll> lnk;
vector<ll> mnUF, mxUF;
ll find(ll a) {
if (lnk[a] != a) lnk[a] = find(lnk[a]);
return lnk[a];
}
void unite(ll a, ll b) {
a = find(a); b = find(b);
if (a == b) return;
lnk[a] = b;
mnUF[b] = min(mnUF[b], mnUF[a]);
mxUF[b] = max(mxUF[b], mxUF[a]);
}
ll minimum_walk(vector<int> p, int s) {
ll n = p.size();
ll res = 0;
for (int i = 0; i < n; i++) res += abs(p[i] - i);
if (res == 0) return 0;
vector<bool> vst(n);
vector<vector<ll>> cyc;
vector<ll> mxCyc;
vector<ll> cycId(n);
for (int i = 0; i < n; i++) {
if (vst[i] || p[i] == i) continue;
cyc.push_back(vector<ll>());
mxCyc.push_back(i);
ll cur = i;
do {
cyc.back().push_back(cur);
mxCyc.back() = max(mxCyc.back(), cur);
cycId[cur] = cyc.size()-1;
cur = p[cur];
vst[cur] = true;
} while (cur != i);
}
ll m = cyc.size();
ll allMn = n, allMx = 0;
for (int i = 0; i < m; i++) {
allMn = min(allMn, cyc[i][0]);
allMx = max(allMx, mxCyc[i]);
}
lnk = vector<ll>(m);
mnUF = vector<ll>(m);
mxUF = vector<ll>(m);
for (int i = 0; i < m; i++) {
lnk[i] = i;
mnUF[i] = cyc[i][0];
mxUF[i] = mxCyc[i];
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++) {
if (cyc[i][0] < cyc[j][0] && mxCyc[i] > cyc[j][0] && mxCyc[i] < mxCyc[j]) {
unite(i, j);
}
}
}
vector<pair<ll, ll>> lut; // -size, id
for (int i = 0; i < m; i++) {
mnUF[i] = mnUF[find(i)];
mxUF[i] = mxUF[find(i)];
if (i == lnk[i]) lut.push_back({mnUF[i] - mxUF[i], i});
}
sort(lut.begin(), lut.end());
vector<ll> nxtDist(m, -1), nxtCyc(m);
for (auto &e : lut) {
ll i = e.second;
ll left = mnUF[i], right = mxUF[i];
ll dist = 0;
while (left > allMn || right < allMx) {
left = max(allMn, left-1);
right = min(allMx, right+1);
dist++;
if (p[left] != left) {
ll c = cycId[left];
if (mnUF[c] < mnUF[i] && mxUF[c] > mxUF[i]) {
nxtDist[i] = dist;
nxtCyc[i] = c;
break;
}
}
if (p[right] != right) {
ll c = cycId[right];
if (mnUF[c] < mnUF[i] && mxUF[c] > mxUF[i]) {
nxtDist[i] = dist;
nxtCyc[i] = c;
break;
}
}
}
}
ll val = res, val1 = res;
ll ptr = s;
if (p[s] != s) {
ptr = min(mnUF[cycId[s]], ptr);
}
while (ptr > allMn) {
ptr = max(allMn, ptr-1);
val += 2;
if (p[ptr] != ptr) {
ll c = cycId[ptr];
if (!(mnUF[c] < s && mxUF[c] > s)) continue;
while (nxtDist[c] != -1) {
val += 2*nxtDist[c];
c = nxtCyc[c];
}
ptr = allMn;
break;
}
}
res = max(res, val);
ptr = s;
if (p[s] != s) {
ptr = max(mxUF[cycId[s]], ptr);
}
while (ptr < allMx) {
ptr++;
val1 += 2;
if (p[ptr] != ptr) {
ll c = cycId[ptr];
if (!(mnUF[c] < s && mxUF[c] > s)) continue;
while (nxtDist[c] != -1) {
val1 += 2*nxtDist[c];
c = nxtCyc[c];
}
ptr = allMx;
break;
}
}
res = max(res, val1);
for (int i = 1; i < m; i++) {
if (lnk[i] != i) continue;
res += 2*max(0ll, mnUF[i] - mxUF[i-1]);
}
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '6', found: '10' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '6', found: '10' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '6', found: '10' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '5096' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '6', found: '10' |
| 2 |
Halted |
0 ms |
0 KB |
- |
