#include "books.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
#define ll long long
#define sz(x) (int)x.size()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
const int N = 1e6+5;
const int mod = 1e9+7;
int n, sz;
int par[N], ss, nearest, used[N], pp[N], l[N], r[N];
ll sum[N];
int f(int x){
if(par[x] == x) return x;
return par[x] = f(par[x]);
}
void merge(int a, int b){
a = f(a), b = f(b);
if(a == b) return;
l[a] = min(l[b], l[a]);
r[a] = max(r[a], r[b]);
par[b] = a;
sum[a] += sum[b];
}
void dfs(int u){
//cout<<u<<" ";
if(used[u]) return;
used[u] = 1;
l[f(u)] = min(l[f(u)], pp[u]);
r[f(u)] = max(r[f(u)], pp[u]);
par[pp[u]] = f(u);
//cout<<sum[f(u)]<<" ";
sum[f(u)] += abs(pp[u] - u);
//cout<<sum[f(u)]<<"\n";
dfs(pp[u]);
}
bool cmp(pair<pii, int> A, pair<pii, int> B){
pii a = A.ff, b = B.ff;
if(a.ff != b.ff) return a.ff < b.ff;
return a.ss > b.ss;
}
/*
8 5
0 1 7 3 4 5 6 2
4 0
0 2 3 1
4 0
0 3 2 1
4 0
3 2 0 1
3 0
2 0 1
*/
ll minimum_walk(vector<int> p, int s) {
n = sz(p);
nearest = -mod;
memset(used, 0, sizeof used);
for(int i=0;i<n;i++){
par[i] = i, sum[i] = 0, l[i] = i, r[i] = i;
}
for(int i=0;i<n;i++) pp[i] = p[i];
vector<pair<pii, int>> vv;
ss = s;
int ans;
for(int i=s;i<n;i++){
if(used[i]) continue;
dfs(i);
if(l[f(i)] != r[f(i)]){
vv.pb({{ l[ f(i) ], r[ f(i) ] }, f(i)});
int u = i, tt = i;
if(abs(nearest - s) > abs(u - s)) nearest = u;
u = pp[u];
while(tt != u){
if(abs(nearest - s) > abs(u - s)) nearest = u;
u = pp[u];
}
ans = i;
}
}
//cout<<nearest<<"\n";
sort(vv.begin(), vv.end(), cmp);
ll tmp = 0;
for(int i=1; i<sz(vv); i++){
int a = vv[i].ss, b = vv[i-1].ss;
tmp += max((vv[i].ff.ff - vv[i-1].ff.ss) * 2, 0);
vv[i].ff.ss = max(vv[i].ff.ss, vv[i-1].ff.ss);
merge(a, b);
ans = a;
}
//cout<<ans<<"\n"<<sum[f(ans)]<<" "<<tmp<<" "<<abs(nearest - s)*2<<"\n";
return sum[f(ans)] + tmp + abs(nearest - s)*2;
}
Compilation message
books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:24:10: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
24 | if(par[x] == x) return x;
| ~~~~~^
books.cpp:86:6: note: 'ans' was declared here
86 | int ans;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4204 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4204 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4204 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4204 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4204 KB |
Output is correct |
| 6 |
Correct |
3 ms |
4204 KB |
Output is correct |
| 7 |
Correct |
3 ms |
4204 KB |
Output is correct |
| 8 |
Correct |
3 ms |
4204 KB |
Output is correct |
| 9 |
Incorrect |
3 ms |
4204 KB |
3rd lines differ - on the 1st token, expected: '0', found: '2000000014' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4204 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4204 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4204 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4204 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4204 KB |
Output is correct |
| 6 |
Correct |
3 ms |
4204 KB |
Output is correct |
| 7 |
Correct |
3 ms |
4204 KB |
Output is correct |
| 8 |
Correct |
3 ms |
4204 KB |
Output is correct |
| 9 |
Incorrect |
3 ms |
4204 KB |
3rd lines differ - on the 1st token, expected: '0', found: '2000000014' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4204 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4204 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4204 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4204 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4204 KB |
Output is correct |
| 6 |
Correct |
3 ms |
4204 KB |
Output is correct |
| 7 |
Correct |
3 ms |
4204 KB |
Output is correct |
| 8 |
Correct |
3 ms |
4204 KB |
Output is correct |
| 9 |
Incorrect |
3 ms |
4204 KB |
3rd lines differ - on the 1st token, expected: '0', found: '2000000014' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4332 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '2438' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4204 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4204 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4204 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4204 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4204 KB |
Output is correct |
| 6 |
Correct |
3 ms |
4204 KB |
Output is correct |
| 7 |
Correct |
3 ms |
4204 KB |
Output is correct |
| 8 |
Correct |
3 ms |
4204 KB |
Output is correct |
| 9 |
Incorrect |
3 ms |
4204 KB |
3rd lines differ - on the 1st token, expected: '0', found: '2000000014' |
| 10 |
Halted |
0 ms |
0 KB |
- |
