#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;
bool done = false;
if (p[s] != s) {
ll c = cycId[s];
while (nxtDist[c] != -1) {
throw;
val += 2*nxtDist[c];
c = nxtCyc[c];
}
ptr = allMn;
done = true;
}
while (!done && ptr > allMn) {
ptr = max(allMn, ptr-1);
val += 2;
if (p[ptr] != ptr) {
ll c = cycId[ptr];
while (nxtDist[c] != -1) {
throw;
val += 2*nxtDist[c];
c = nxtCyc[c];
}
ptr = allMn;
done = true;
break;
}
}
if (done) res = val;
ptr = s;
bool done1 = false;
if (p[s] != s) {
ll c = cycId[s];
while (nxtDist[c] != -1) {
throw;
val1 += 2*nxtDist[c];
c = nxtCyc[c];
}
ptr = allMx;
done1 = true;
}
while (!done1 && ptr < allMx) {
ptr++;
val1 += 2;
if (p[ptr] != ptr) {
ll c = cycId[ptr];
while (nxtDist[c] != -1) {
throw;
val1 += 2*nxtDist[c];
c = nxtCyc[c];
}
ptr = allMx;
done1 = true;
break;
}
}
if (done1) {
if (done) res = min(res, val1);
else 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;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
344 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
344 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
432 KB |
Output is correct |
21 |
Correct |
1 ms |
344 KB |
Output is correct |
22 |
Incorrect |
2 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '2082', found: '2020' |
23 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
344 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
432 KB |
Output is correct |
21 |
Correct |
1 ms |
344 KB |
Output is correct |
22 |
Incorrect |
2 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '2082', found: '2020' |
23 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
344 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
432 KB |
Output is correct |
21 |
Correct |
1 ms |
344 KB |
Output is correct |
22 |
Incorrect |
2 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '2082', found: '2020' |
23 |
Halted |
0 ms |
0 KB |
- |