#include "books.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e6 + 5, INF = 1e9;
int p[maxn];
int vis[maxn];
bool taken[maxn];
vector<pair<int,int>> vec = {{-1, -1}};
int l, r;
void expand(int L, int R) {
vector<int> add;
while (l > L) {
l--;
if (p[l]!=l) add.push_back(vis[l]);
}
while (r<R) {
r++;
if (p[r]!=r) add.push_back(vis[r]);
}
for (int i:add) expand(vec[i].first, vec[i].second);
}
int minimum_walk(vector<int32_t> P, int32_t s) {
int n = P.size();
for (int i=0;i<n;i++) p[i] = P[i];
for (int i=0;i<n;i++) vis[i] = false;
int ans = 0;
int cnt = 0;
for (int i=0;i<n;i++) if (!vis[i]) {
if (p[i]==i && i==s) {
cnt++;
vis[i] = cnt;
vec.push_back({s, s});
}
if (p[i]==i) continue;
int u = i;
pair<int,int> val = {u, u};
cnt++;
while (true) {
vis[u] = cnt;
val.first = min(u, val.first);
val.second = max(u, val.second);
int v = p[u];
ans += abs(v-u);
if (v==i) break;
u = v;
}
vec.push_back(val);
}
sort(vec.begin(), vec.end());
int lastl = 0, mx = 0;
int LL, RR;
for (int i=1;i<vec.size();i++) {
if (vec[i].first > mx) {
if (lastl<=s && s<=mx) {
LL = lastl, RR = mx;
break;
}
lastl = vec[i].first;
}
mx = max(vec[i].second, mx);
}
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
pq.push({vis[s], 0});
int dist[cnt+5];
for (int i=1;i<=cnt;i++) dist[i] = -1;
while (pq.size() > 0) {
int u = pq.top().first, d = pq.top().second;
pq.pop();
if (dist[u]!=-1) continue;
dist[u] = d;
for (int i=vec[u].first; i<=vec[u].second;i++) {
if (dist[vis[i]]==-1) pq.push({vis[i], d});
}
for (int i=vec[u].first-1;i>=0;i--) {
if (p[i]!=i) {
if (dist[vis[i]]!=-1) pq.push({vis[i], d + (vec[u].first - i)*2});
break;
}
}
for (int i=vec[u].second+1;i<n;i++) {
if (p[i]!=i) {
if (dist[vis[i]]!=-1) pq.push({vis[i], d + (i - vec[u].first)*2});
break;
}
}
}
int MX = 0;
for (int i=1;i<=cnt;i++) if (dist[i]!=-1) MX = max(dist[i], MX);
ans += MX;
vector<pair<int,int>> vec2;
for (auto [x, y]:vec) if (y<LL || x>RR) vec2.push_back({x, y});
vec2.push_back({LL, RR});
sort(vec2.begin(), vec2.end());
mx = vec2[0].second;
for (int i=1;i<vec2.size();i++) {
if (vec2[i].first > mx) ans += vec2[i].first - mx;
mx = max(vec2[i].second, mx);
}
return ans;
}
Compilation message
books.cpp: In function 'long long int minimum_walk(std::vector<int>, int32_t)':
books.cpp:56:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for (int i=1;i<vec.size();i++) {
| ~^~~~~~~~~~~
books.cpp:101:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | for (int i=1;i<vec2.size();i++) {
| ~^~~~~~~~~~~~
books.cpp:97:36: warning: 'RR' may be used uninitialized in this function [-Wmaybe-uninitialized]
97 | for (auto [x, y]:vec) if (y<LL || x>RR) vec2.push_back({x, y});
| ~~~~~^~~~~~~
books.cpp:97:27: warning: 'LL' may be used uninitialized in this function [-Wmaybe-uninitialized]
97 | for (auto [x, y]:vec) if (y<LL || x>RR) vec2.push_back({x, y});
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
4444 KB |
3rd lines differ - on the 1st token, expected: '8', found: '37099666' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
4444 KB |
3rd lines differ - on the 1st token, expected: '8', found: '37099666' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
4444 KB |
3rd lines differ - on the 1st token, expected: '8', found: '37099666' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '44973806' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
4444 KB |
3rd lines differ - on the 1st token, expected: '8', found: '37099666' |
| 4 |
Halted |
0 ms |
0 KB |
- |
