| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1185024 | hamzabc | Simurgh (IOI17_simurgh) | C++20 | 0 ms | 0 KiB |
#include "books.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> dsu;
vector<int> l;
vector<int> r;
vector<int> used;
vector<pair<int, int>> araliklar;
int goDSU(int a){
if (dsu[a] == a)
return a;
dsu[a] = goDSU(dsu[a]);
return dsu[a];
}
long long minimum_walk(std::vector<int> p, int s) {
int n = p.size();
dsu.resize(n);
l.resize(n);
r.resize(n);
used.resize(n);
for (int i = 0; i < n; i++){
p[i];
dsu[i] = i;
l[i] = i;
r[i] = i;
}
int L = 0;
for (; n > 0; n--){
if (p[n - 1] != n - 1)
break;
}
if (n == 0)
return 0;
for (; L < n; L++){
if (p[L] != L)
break;
}
long long int ret = 0;
for (int i = L; i < n; i++){
ret += abs(p[i] - i);
if (goDSU(i) != goDSU(p[i])){
r[goDSU(p[i])] = max(r[goDSU(p[i])], r[goDSU(i)]);
l[goDSU(p[i])] = min(l[goDSU(p[i])], l[goDSU(i)]);
dsu[goDSU(i)] = goDSU(p[i]);
}
}
for (int i = L; i < n; i++){
if (!used[goDSU(i)]){
used[goDSU(i)] = true;
araliklar.push_back({ l[goDSU(i)], r[goDSU(i)] });
}
}
sort(araliklar.begin(), araliklar.end());
int mxr = araliklar[0].second;
for (int i = 1; i < araliklar.size(); i++){
if (mxr > araliklar[i].first){
mxr = max(mxr, araliklar[i].second);
}else{
mxr = max(mxr, araliklar[i].second);
ret += 2;
}
}
int add = 0;
for (int i = s; i < n; i++){
if (p[i] != i){
add = i - s;
break;
}
}
for (int i = s; i > L; i--){
if (p[i] != i){
add = min(add, i - s);
break;
}
}
return ret + max(0, L - s) * 2 + max(0, s - n + 1) * 2 + add * 2;
}