| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1012182 | 2024-07-01T19:16:30 Z | hyakup | 고대 책들 (IOI17_books) | C++17 | 0 ms | 0 KB |
#include "books.h"
#include <bits/stdc++.h>
using namespace std;
#define bug(x) cout << #x << " " << x << endl;
#define ll long long
const ll maxn = 1e6 + 10;
bool marc[maxn];
long long minimum_walk(vector<ll> p, ll s) {
if( is_sorted( p.begin(), p.end() ) ) return 0;
ll n = (ll)p.size();
ll resp = 0;
for( ll i = 0; i < (ll)p.size(); i++ ) resp += (ll)abs(p[i] - i);
ll maxi = -1;
bool contido = false;
for( ll i = 0; i < n; i++ ){
if( !marc[i] && p[i] != i ){
if( maxi != -1 && i > maxi ) resp += 2LL*(i - maxi);
ll cur = i;
while( !marc[cur] ){
maxi = max( maxi, cur );
marc[cur] = true;
cur = p[cur];
}
if( i <= s && s <= maxi ) contido = true;
}
}
ll l = s, r = s;
while( l >= 0 && !marc[l] ) l--;
while( r < n && !marc[r] ) r++;
if( contido ) resp += 2LL*min( s - l, r - s );
else{
if( l == -1 ) resp += 2LL*(r - s);
else if( r == n ) resp += 2LL*(s - l);
}
return resp;
}