#include <bits/stdc++.h>
#include "books.h"
#pragma GCC optimize("Ofast")
using namespace std;
#define pb push_back
#define pii pair<int,int>
#define sz(s) (int)s.size()
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define ll long long
const int MAX=1e6+10;
int n;
vector<int> g[MAX];
bool use[MAX];
vector<int> vec;
int pref[MAX];
struct dsu{
int f[MAX];
void init(int n){
for(int i=0;i<n;i++)f[i]=i;
}
int get(int v){
return (f[v]==v?v:f[v]=get(f[v]));
}
void unite(int a,int b){
a=get(a),b=get(b);
f[a]=b;
}
}d;
int num[MAX];
bool is(int l,int r,vector<int> x){
for(int pos:x){
if(l<=pos&&pos<=r)return 1;
}
return 0;
}
ll minimum_walk(vector<int> p,int s){
n=sz(p);
int Lneed=0,Rneed=n-1;
ll ans=0;
for(int i=0;i<n;i++){
ans+=abs(i-p[i]);
}
vector<vector<int>> x;
vector<pii> seg;
for(int i=0;i<n;i++){
if(!use[i]){
vec.clear();
int v=i;
while(!use[v]){
num[v]=sz(seg);
vec.pb(v);
use[v]=1;
v=p[v];
}
sort(all(vec));
seg.pb({vec[0],vec.back()});
x.pb(vec);
}
}
d.init(n);
for(int i=0;i<sz(seg);i++){
auto [l,r]=seg[i];
for(int j=i+1;j<sz(seg);j++){
assert(is(l,r,x[j])==is(seg[j].F,seg[j].S,x[i]));
for(int pos:x[j]){
if(l<=pos&&pos<=r){
d.unite(i,j);
}
}
}
}
for(int i=0;i<n-1;i++){
if(d.get(num[i])!=d.get(num[i+1])){
ans+=2;
d.unite(num[i],num[i+1]);
}
}
for(int i=0;i<s;i++){
if(p[i]==i)ans-=2;
else break;
}
for(int i=n-1;i>s;i--){
if(p[i]==i)ans-=2;
else break;
}
return ans;
}
Compilation message
books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:52:9: warning: unused variable 'Lneed' [-Wunused-variable]
52 | int Lneed=0,Rneed=n-1;
| ^~~~~
books.cpp:52:17: warning: unused variable 'Rneed' [-Wunused-variable]
52 | int Lneed=0,Rneed=n-1;
| ^~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
28248 KB |
Output is correct |
2 |
Runtime error |
20 ms |
56796 KB |
Execution killed with signal 6 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
28248 KB |
Output is correct |
2 |
Runtime error |
20 ms |
56796 KB |
Execution killed with signal 6 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
28248 KB |
Output is correct |
2 |
Runtime error |
20 ms |
56796 KB |
Execution killed with signal 6 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
19 ms |
57180 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
28248 KB |
Output is correct |
2 |
Runtime error |
20 ms |
56796 KB |
Execution killed with signal 6 |
3 |
Halted |
0 ms |
0 KB |
- |