#include "books.h"
#include <vector>
#include <map>
typedef struct range range;
struct range
{
int e;
long long m;
};
// bool operator<(range a, range b)
// {
// return a.s < b.s;
// }
int vis[1000005];
int still[1000005];
int abs(int a)
{
return (a < 0)?-a:a;
}
int min(int a, int b)
{
return (a < b)?a:b;
}
int max(int a, int b)
{
return (a > b)?a:b;
}
long long minimum_walk(std::vector<int> p, int ss) {
std::map<int, range> R;
int i, n = p.size();
int s, e;
long long m;
for (i = 0; i < n; i++)
{
if (!vis[i])
{
s = i;
e = i;
m = 0;
while (!vis[i])
{
vis[i] = 1;
m += abs(p[i] - i);
i = p[i];
s = min(s, i);
e = max(e, i);
}
// printf("%d %d %lld\n", s, e, m);
if (m != 0)
R.insert(std::make_pair(s, range{e, m}));
else
still[i] = 1;
}
}
std::map<int, range>::iterator it, it2;
for (it = R.begin(); it != R.end();)
{
if (it != R.begin() && it->second.e < it2->second.e)
{
it2->second.m += it->second.m;
it = R.erase(it);
}
else if (it != R.begin() && it2->second.e > it->first)
{
it2->second.m += it->second.m;
it2->second.e = it->second.e;
it = R.erase(it);
}
else
{
it2 = it;
it++;
}
}
long long Ans = 0;
if (still[ss])
{
for (i = ss; i >= 0 && still[i]; i--)
if (i >= 0) Ans = 2LL*(ss - i);
for (i = ss; i < n; && still[i]; i++)
if (i < n) Ans = min(Ans, 2LL*(i - ss));
}
for (it = R.begin(); it != R.end(); it++)
{
// printf("%d %d %lld\n", it->first, it->second.e, it->second.m);
Ans += it->second.m;
if (it != R.begin())
Ans += 2LL*(it->first - it2->second.e);
it2 = it;
}
return Ans;
}
Compilation message
books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:80:23: warning: for increment expression has no effect [-Wunused-value]
for (i = ss; i < n; && still[i]; i++)
^
books.cpp:80:31: error: expected ')' before '[' token
for (i = ss; i < n; && still[i]; i++)
^
books.cpp: In lambda function:
books.cpp:80:34: error: expected '{' before ';' token
for (i = ss; i < n; && still[i]; i++)
^
books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:80:39: error: expected ';' before ')' token
for (i = ss; i < n; && still[i]; i++)
^
books.cpp:80:26: error: label 'still' used but not defined
for (i = ss; i < n; && still[i]; i++)
^
