#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000000;
bool vis[N];
/*
bool tree[4 * N];
void push(int node)
{
if (tree[node])
{
tree[node * 2] = true;
tree[node * 2 +1] = true;
}
}
void ins(int from, int to, int a, int b, int node)
{
if (from <= a && b <= to)
{
tree[node] = true;
return;
}
push(node);
int mid = (a + b) / 2;
if (from <= mid) ins(from, to, a, mid, node * 2);
if (to > mid) ins(from, to, mid + 1, b, node * 2 + 1);
}
bool getIn(int i, int a, int b, int node)
{
if (a == b) return tree[node];
push(node);
int mid = (a + b) / 2;
if (i <= mid) return getIn(i, a, mid, node * 2);
return getIn(i, mid + 1, b, node * 2 + 1);
} */
long long minimum_walk(std::vector<int> p, int s) {
ll res = 0;
int n = p.size();
vector<array<int, 2>> ivals;
vector<array<int, 2>> landr(n);
vector<int> comp(n);
int compNum = 0;
for (int i = 0; i < n; i++)
{
if (p[i] == i || vis[i]) continue;
int cur = i;
int l = cur;
int r = cur;
do
{
vis[cur] = true;
l = min(l, cur);
r = max(r, cur);
res += abs(p[cur] - cur);
//ins(min(cur, p[cur]), max(cur, p[cur]), 0, n - 1, 1);
cur = p[cur];
} while (cur != i);
ivals.push_back({l, r});
do
{
comp[cur] = compNum;
//ins(min(cur, p[cur]), max(cur, p[cur]), 0, n - 1, 1);
cur = p[cur];
} while (cur != i);
landr[compNum][0] = l;
landr[compNum][1] = r;
compNum++;
}
if (res == 0) return 0;
sort(ivals.begin(), ivals.end());
vector<array<int, 2>> together;
int l = ivals[0][0];
int r = ivals[0][1];
for (int i = 1; i < ivals.size(); i++)
{
if (ivals[i][0] > r)
{
together.push_back({l, r});
l = ivals[i][0];
r = ivals[i][1];
} else
{
r = max(ivals[i][1], r);
}
}
together.push_back({l, r});
for (int i = 1; i < together.size(); i++)
{
res += (together[i][0] - together[i - 1][1]) * 2;
}
if (s < together[0][0])
{
res += (together[0][0] - s) * 2;
}
if (s > together[together.size() - 1][1])
{
res += (s - together[together.size() - 1][1]) * 2;
}
int in = -1;
for (int i = 0; i < together.size(); i++)
{
if (i >= together[i][0] && i <= together[i][1])
{
in = i;
break;
}
}
if (in != -1)
{
vector<int> dist(n, -1);
int cr = 0;
int cl = 0;
int cur = s;
deque<array<int, 2>> que;
que.push_back({comp[s], 0});
while (!que.empty())
{
auto cur = que.front();
if (dist[cur[0]] != -1) continue;
dist[cur[0]] = cur[1];
for (int i = landr[cur[0]][0]; i <= landr[cur[0]][1]; i++)
{
que.push_front({comp[i], cur[1]});
}
if (landr[cur[0]][0] - 1 >= together[in][0])
{
que.push_back({comp[landr[cur[0]][0] - 1], cur[1] + 1});
}
if (landr[cur[0]][1] + 1 <= together[in][1])
{
que.push_back({comp[landr[cur[0]][1] + 1], cur[1] + 1});
}
}
res += min(dist[comp[together[in][0]]], dist[comp[together[in][1]]]);
}
return res;
}
/*
4 0
0 2 3 1
*/
Compilation message
books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:94:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for (int i = 1; i < ivals.size(); i++)
| ~~^~~~~~~~~~~~~~
books.cpp:111:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for (int i = 1; i < together.size(); i++)
| ~~^~~~~~~~~~~~~~~~~
books.cpp:126:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
126 | for (int i = 0; i < together.size(); i++)
| ~~^~~~~~~~~~~~~~~~~
books.cpp:138:13: warning: unused variable 'cr' [-Wunused-variable]
138 | int cr = 0;
| ^~
books.cpp:139:13: warning: unused variable 'cl' [-Wunused-variable]
139 | int cl = 0;
| ^~
books.cpp:140:13: warning: unused variable 'cur' [-Wunused-variable]
140 | int cur = s;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Execution timed out |
2075 ms |
204 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Execution timed out |
2075 ms |
204 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Execution timed out |
2075 ms |
204 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2075 ms |
204 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Execution timed out |
2075 ms |
204 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
