| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 289440 | 2020-09-02T16:30:56 Z | eohomegrownapps | 고대 책들 (IOI17_books) | C++14 | 0 ms | 0 KB |
#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> cycle;
vector<ll> p;
ll n;
ll minc = 1e9;
ll maxc = -1e9;
ll findcycle(ll i, ll ptr){
cycle[i] = ptr;
minc=min(minc,i);
maxc=max(maxc,i);
if (cycle[p[i]]!=-1){
return abs(i-p[i]);
} else {
return abs(i-p[i]) + findcycle(p[i], ptr);
}
}
ll minimum_walk(std::vector<ll> px, ll s) {
p = px;
n = p.size();
cycle.resize(n,-1);
ll cycledist = 0;
ll ptr = 0;
vector<ll> cyclewidth(n);
for (ll i = 0; i<n; i++){
if (cycle[i]!=-1){continue;}
minc=1e9;maxc=-1e9;
ll dist = findcycle(i,ptr);
cyclewidth[minc]++;
cyclewidth[maxc]--;
cycledist+=dist;
ptr++;
}
ll prev = 0;
bool iszero = true;
ll ctr = 0;
for (ll i = 0; i<n; i++){
ctr+=cyclewidth[i];
if (iszero&&ctr>0){
cycledist+=2*(i-prev);
iszero = false;
} else if ((!iszero)&&ctr==0){
prev = i;
iszero = true;
}
}
return cycledist;
}