#include "books.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
long long minimum_walk(std::vector<int> p, int s) {
int n = p.size();
ll base_cost = 0;
for (int i=0; i<n; i++)
base_cost += abs(p[i]-i);
vector<pii> cycles;
vector<bool> used(n, 0);
for (int i=0; i<n; i++)
if (used[i]==0)
{
used[i]=1;
int mini = i;
int maxi = i;
int curr = p[i];
while (curr!=i)
{
used[curr] = 1;
maxi = max(curr, maxi);
curr = p[curr];
}
if (mini!=maxi)
cycles.push_back({mini, maxi});
}
int k = cycles.size();
ll penalty = 0;
int curr_max = -1;
for (int i=0; i<k; i++)
{
if (i==0)
penalty = cycles[0].first;
else if (cycles[i].first > curr_max)
penalty += cycles[i].first - curr_max;
curr_max = max(curr_max, cycles[i].second);
}
return base_cost + 2ll*penalty;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |