#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 1005
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define IDB pair <db,int>
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x)
using namespace std;
#include "books.h"
ll Right[N],Left[N],in[N],ma[N][N],mi[N][N],i,j,l,r,n_cycle,n,p[N],Begin,End,f[N][N],book_move;
II extend[N][N];
const ll oo=round(1e18);
void Init()
{
for(i=1;i<=n;i++)
if(in[i]==0)
{
n_cycle++;
l=oo;
r=-oo;
for(j=i;in[j]==0;j=p[j])
{
in[j]=n_cycle;
l=min(l,j);
r=max(r,j);
}
Left[n_cycle]=l;
Right[n_cycle]=r;
}
for(i=n;i>=1;i--)
{
ma[i][i-1]=-oo;
mi[i][i-1]=oo;
for(j=i;j<=n;j++)
{
ma[i][j]=max(ma[i][j-1],Right[in[j]]);
mi[i][j]=min(mi[i][j-1],Left[in[j]]);
}
}
}
II Fix(int l,int r)
{
if(extend[l][r].fst>-1) return extend[l][r];
if(ma[l][r]>r) return extend[l][r]=Fix(l,ma[l][r]);
if(mi[l][r]<l) return extend[l][r]=Fix(mi[l][r],r);
return extend[l][r]={ l,r };
}
ll cal(int l,int r)
{
II k=Fix(l,r);
l=k.fst; r=k.snd;
if(l==Begin && r==End) return 0;
if(f[l][r]>-1) return f[l][r];
f[l][r]=oo;
if(l>Begin) f[l][r]=cal(l-1,r)+2;
if(r<End) f[l][r]=min(f[l][r],cal(l,r+1)+2);
return f[l][r];
}
ll minimum_walk(vector <int> _p,int s)
{
s++;
for(int k:_p) p[++n]=k,p[n]++;
for(i=1;i<=n;i++)
{
book_move+=abs(i-p[i]);
if(i!=p[i])
{
if(Begin==0) Begin=i;
End=i;
}
}
if(Begin==0) return 0;
Begin=min(Begin,(ll)s);
End=max(End,(ll)s);
Init();
memset(f,-1,sizeof(f));
for(i=1;i<=n;i++)
for(j=1;j<=n;j++) extend[i][j]={ -1,-1 };
return book_move+cal(s,s);
}
/*
int main()
{
freopen("books.inp","r",stdin);
freopen("books.out","w",stdout);
vector <int> p;
int n,s,k;
cin>>n>>s;
for(int i=1;i<=n;i++) cin>>k,p.push_back(k);
cout<<minimum_walk(p,s);
}
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
10332 KB |
Output is correct |
2 |
Correct |
2 ms |
10332 KB |
Output is correct |
3 |
Correct |
2 ms |
10332 KB |
Output is correct |
4 |
Correct |
2 ms |
10332 KB |
Output is correct |
5 |
Correct |
2 ms |
10332 KB |
Output is correct |
6 |
Correct |
2 ms |
10332 KB |
Output is correct |
7 |
Correct |
2 ms |
10332 KB |
Output is correct |
8 |
Correct |
2 ms |
10332 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
2 ms |
10332 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
2 ms |
10332 KB |
Output is correct |
13 |
Correct |
2 ms |
10332 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
2 ms |
10332 KB |
Output is correct |
16 |
Correct |
2 ms |
10332 KB |
Output is correct |
17 |
Correct |
3 ms |
10332 KB |
Output is correct |
18 |
Correct |
2 ms |
10332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
10332 KB |
Output is correct |
2 |
Correct |
2 ms |
10332 KB |
Output is correct |
3 |
Correct |
2 ms |
10332 KB |
Output is correct |
4 |
Correct |
2 ms |
10332 KB |
Output is correct |
5 |
Correct |
2 ms |
10332 KB |
Output is correct |
6 |
Correct |
2 ms |
10332 KB |
Output is correct |
7 |
Correct |
2 ms |
10332 KB |
Output is correct |
8 |
Correct |
2 ms |
10332 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
2 ms |
10332 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
2 ms |
10332 KB |
Output is correct |
13 |
Correct |
2 ms |
10332 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
2 ms |
10332 KB |
Output is correct |
16 |
Correct |
2 ms |
10332 KB |
Output is correct |
17 |
Correct |
3 ms |
10332 KB |
Output is correct |
18 |
Correct |
2 ms |
10332 KB |
Output is correct |
19 |
Correct |
9 ms |
39516 KB |
Output is correct |
20 |
Correct |
7 ms |
39516 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
8 ms |
39772 KB |
Output is correct |
23 |
Correct |
7 ms |
39692 KB |
Output is correct |
24 |
Correct |
7 ms |
39620 KB |
Output is correct |
25 |
Correct |
8 ms |
39772 KB |
Output is correct |
26 |
Correct |
9 ms |
39512 KB |
Output is correct |
27 |
Correct |
7 ms |
39516 KB |
Output is correct |
28 |
Correct |
7 ms |
39516 KB |
Output is correct |
29 |
Correct |
8 ms |
39516 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
10332 KB |
Output is correct |
2 |
Correct |
2 ms |
10332 KB |
Output is correct |
3 |
Correct |
2 ms |
10332 KB |
Output is correct |
4 |
Correct |
2 ms |
10332 KB |
Output is correct |
5 |
Correct |
2 ms |
10332 KB |
Output is correct |
6 |
Correct |
2 ms |
10332 KB |
Output is correct |
7 |
Correct |
2 ms |
10332 KB |
Output is correct |
8 |
Correct |
2 ms |
10332 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
2 ms |
10332 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
2 ms |
10332 KB |
Output is correct |
13 |
Correct |
2 ms |
10332 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
2 ms |
10332 KB |
Output is correct |
16 |
Correct |
2 ms |
10332 KB |
Output is correct |
17 |
Correct |
3 ms |
10332 KB |
Output is correct |
18 |
Correct |
2 ms |
10332 KB |
Output is correct |
19 |
Correct |
9 ms |
39516 KB |
Output is correct |
20 |
Correct |
7 ms |
39516 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
8 ms |
39772 KB |
Output is correct |
23 |
Correct |
7 ms |
39692 KB |
Output is correct |
24 |
Correct |
7 ms |
39620 KB |
Output is correct |
25 |
Correct |
8 ms |
39772 KB |
Output is correct |
26 |
Correct |
9 ms |
39512 KB |
Output is correct |
27 |
Correct |
7 ms |
39516 KB |
Output is correct |
28 |
Correct |
7 ms |
39516 KB |
Output is correct |
29 |
Correct |
8 ms |
39516 KB |
Output is correct |
30 |
Runtime error |
96 ms |
42184 KB |
Execution killed with signal 11 |
31 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
39772 KB |
Output is correct |
2 |
Correct |
8 ms |
39516 KB |
Output is correct |
3 |
Correct |
8 ms |
39772 KB |
Output is correct |
4 |
Correct |
9 ms |
39796 KB |
Output is correct |
5 |
Correct |
9 ms |
39772 KB |
Output is correct |
6 |
Correct |
8 ms |
39656 KB |
Output is correct |
7 |
Correct |
9 ms |
39512 KB |
Output is correct |
8 |
Correct |
8 ms |
39512 KB |
Output is correct |
9 |
Correct |
8 ms |
39512 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
8 ms |
39772 KB |
Output is correct |
12 |
Correct |
8 ms |
39560 KB |
Output is correct |
13 |
Correct |
7 ms |
39512 KB |
Output is correct |
14 |
Correct |
7 ms |
39516 KB |
Output is correct |
15 |
Correct |
7 ms |
39516 KB |
Output is correct |
16 |
Correct |
7 ms |
39516 KB |
Output is correct |
17 |
Correct |
7 ms |
39772 KB |
Output is correct |
18 |
Correct |
8 ms |
39768 KB |
Output is correct |
19 |
Correct |
8 ms |
39516 KB |
Output is correct |
20 |
Correct |
8 ms |
39572 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
10332 KB |
Output is correct |
2 |
Correct |
2 ms |
10332 KB |
Output is correct |
3 |
Correct |
2 ms |
10332 KB |
Output is correct |
4 |
Correct |
2 ms |
10332 KB |
Output is correct |
5 |
Correct |
2 ms |
10332 KB |
Output is correct |
6 |
Correct |
2 ms |
10332 KB |
Output is correct |
7 |
Correct |
2 ms |
10332 KB |
Output is correct |
8 |
Correct |
2 ms |
10332 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
2 ms |
10332 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
2 ms |
10332 KB |
Output is correct |
13 |
Correct |
2 ms |
10332 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
2 ms |
10332 KB |
Output is correct |
16 |
Correct |
2 ms |
10332 KB |
Output is correct |
17 |
Correct |
3 ms |
10332 KB |
Output is correct |
18 |
Correct |
2 ms |
10332 KB |
Output is correct |
19 |
Correct |
9 ms |
39516 KB |
Output is correct |
20 |
Correct |
7 ms |
39516 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
8 ms |
39772 KB |
Output is correct |
23 |
Correct |
7 ms |
39692 KB |
Output is correct |
24 |
Correct |
7 ms |
39620 KB |
Output is correct |
25 |
Correct |
8 ms |
39772 KB |
Output is correct |
26 |
Correct |
9 ms |
39512 KB |
Output is correct |
27 |
Correct |
7 ms |
39516 KB |
Output is correct |
28 |
Correct |
7 ms |
39516 KB |
Output is correct |
29 |
Correct |
8 ms |
39516 KB |
Output is correct |
30 |
Runtime error |
96 ms |
42184 KB |
Execution killed with signal 11 |
31 |
Halted |
0 ms |
0 KB |
- |