| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 289441 | eohomegrownapps | 고대 책들 (IOI17_books) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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<int> px, int 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;
}