#include "books.h"
#include <bits/stdc++.h>
#define MAXN 1000007
using namespace std;
bool vi[MAXN];
int a[MAXN],mik[MAXN],mak[MAXN],cnt;
long long d[1007][1007];
long long md[MAXN];
long long MST(int s)
{
for(int i=1;i<=cnt;i++) {vi[i]=false; md[i]=MAXN;}
md[s]=0;
long long t=0;
for(int x=0;x<cnt;x++)
{
pair<long long,int> mi=make_pair(MAXN,0);
for(int i=1;i<=cnt;i++) if(!vi[i]) mi=min(make_pair(md[i],i),mi);
int u=mi.second;
t+=mi.first;
vi[u]=true;
for(int i=1;i<=cnt;i++) if(!vi[i]) md[i]=min(md[i],d[u][i]);
}
return t;
}
long long minimum_walk(std::vector<int> p, int s)
{
if(s==0)
{
long long sk=0;
int mx=0;
for(int i=0;i<p.size();i++) if(!vi[i])
{
if(i>mx && p[i]!=i) sk+=2*((long long)i-mx);
int prev=i;
while(!vi[i])
{
if(p[i]!=i) mx=max(i,mx);
vi[i]=true;
i=p[i];
sk+=abs((long long)i-prev);
prev=i;
}
}
return sk;
}
long long sk=0;
for(int i=0;i<p.size();i++) if(!vi[i])
{
if(p[i]==i) continue;
int prev=i;
++cnt;
mik[cnt]=mak[cnt]=i;
while(!vi[i])
{
a[i]=cnt;
mik[cnt]=min(mik[cnt],i);
mak[cnt]=max(mak[cnt],i);
vi[i]=true;
i=p[i];
sk+=abs((long long)i-prev);
prev=i;
}
}
if(p[s]==s) {a[s]=++cnt; mak[cnt]=mik[cnt]=s;}
for(int i=1;i<=cnt;i++) for(int j=0;j<=cnt;j++) d[i][j]=MAXN;
for(int i=1;i<=cnt;i++) for(int j=0;j<p.size();j++)
{
if(j>=mik[i] && j<=mak[i]) d[i][a[j]]=0;
else d[i][a[j]]=min(d[i][a[j]],max((long long)mik[i]-j,(long long)j-mak[i]));
}
return sk+2LL*MST(a[s]);
}
Compilation message
books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:31:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<p.size();i++) if(!vi[i])
~^~~~~~~~~
books.cpp:47:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<p.size();i++) if(!vi[i])
~^~~~~~~~~
books.cpp:66:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1;i<=cnt;i++) for(int j=0;j<p.size();j++)
~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
484 KB |
Output is correct |
| 3 |
Correct |
2 ms |
544 KB |
Output is correct |
| 4 |
Correct |
3 ms |
544 KB |
Output is correct |
| 5 |
Correct |
2 ms |
544 KB |
Output is correct |
| 6 |
Correct |
2 ms |
544 KB |
Output is correct |
| 7 |
Correct |
2 ms |
544 KB |
Output is correct |
| 8 |
Correct |
3 ms |
544 KB |
Output is correct |
| 9 |
Correct |
3 ms |
544 KB |
Output is correct |
| 10 |
Correct |
4 ms |
544 KB |
Output is correct |
| 11 |
Correct |
2 ms |
544 KB |
Output is correct |
| 12 |
Correct |
3 ms |
544 KB |
Output is correct |
| 13 |
Correct |
3 ms |
544 KB |
Output is correct |
| 14 |
Correct |
2 ms |
544 KB |
Output is correct |
| 15 |
Correct |
3 ms |
600 KB |
Output is correct |
| 16 |
Correct |
3 ms |
612 KB |
Output is correct |
| 17 |
Correct |
2 ms |
612 KB |
Output is correct |
| 18 |
Correct |
3 ms |
612 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
484 KB |
Output is correct |
| 3 |
Correct |
2 ms |
544 KB |
Output is correct |
| 4 |
Correct |
3 ms |
544 KB |
Output is correct |
| 5 |
Correct |
2 ms |
544 KB |
Output is correct |
| 6 |
Correct |
2 ms |
544 KB |
Output is correct |
| 7 |
Correct |
2 ms |
544 KB |
Output is correct |
| 8 |
Correct |
3 ms |
544 KB |
Output is correct |
| 9 |
Correct |
3 ms |
544 KB |
Output is correct |
| 10 |
Correct |
4 ms |
544 KB |
Output is correct |
| 11 |
Correct |
2 ms |
544 KB |
Output is correct |
| 12 |
Correct |
3 ms |
544 KB |
Output is correct |
| 13 |
Correct |
3 ms |
544 KB |
Output is correct |
| 14 |
Correct |
2 ms |
544 KB |
Output is correct |
| 15 |
Correct |
3 ms |
600 KB |
Output is correct |
| 16 |
Correct |
3 ms |
612 KB |
Output is correct |
| 17 |
Correct |
2 ms |
612 KB |
Output is correct |
| 18 |
Correct |
3 ms |
612 KB |
Output is correct |
| 19 |
Correct |
2 ms |
612 KB |
Output is correct |
| 20 |
Correct |
3 ms |
612 KB |
Output is correct |
| 21 |
Correct |
2 ms |
612 KB |
Output is correct |
| 22 |
Correct |
2 ms |
620 KB |
Output is correct |
| 23 |
Correct |
2 ms |
620 KB |
Output is correct |
| 24 |
Correct |
3 ms |
620 KB |
Output is correct |
| 25 |
Correct |
3 ms |
620 KB |
Output is correct |
| 26 |
Correct |
4 ms |
620 KB |
Output is correct |
| 27 |
Correct |
4 ms |
620 KB |
Output is correct |
| 28 |
Correct |
2 ms |
620 KB |
Output is correct |
| 29 |
Correct |
2 ms |
620 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
484 KB |
Output is correct |
| 3 |
Correct |
2 ms |
544 KB |
Output is correct |
| 4 |
Correct |
3 ms |
544 KB |
Output is correct |
| 5 |
Correct |
2 ms |
544 KB |
Output is correct |
| 6 |
Correct |
2 ms |
544 KB |
Output is correct |
| 7 |
Correct |
2 ms |
544 KB |
Output is correct |
| 8 |
Correct |
3 ms |
544 KB |
Output is correct |
| 9 |
Correct |
3 ms |
544 KB |
Output is correct |
| 10 |
Correct |
4 ms |
544 KB |
Output is correct |
| 11 |
Correct |
2 ms |
544 KB |
Output is correct |
| 12 |
Correct |
3 ms |
544 KB |
Output is correct |
| 13 |
Correct |
3 ms |
544 KB |
Output is correct |
| 14 |
Correct |
2 ms |
544 KB |
Output is correct |
| 15 |
Correct |
3 ms |
600 KB |
Output is correct |
| 16 |
Correct |
3 ms |
612 KB |
Output is correct |
| 17 |
Correct |
2 ms |
612 KB |
Output is correct |
| 18 |
Correct |
3 ms |
612 KB |
Output is correct |
| 19 |
Correct |
2 ms |
612 KB |
Output is correct |
| 20 |
Correct |
3 ms |
612 KB |
Output is correct |
| 21 |
Correct |
2 ms |
612 KB |
Output is correct |
| 22 |
Correct |
2 ms |
620 KB |
Output is correct |
| 23 |
Correct |
2 ms |
620 KB |
Output is correct |
| 24 |
Correct |
3 ms |
620 KB |
Output is correct |
| 25 |
Correct |
3 ms |
620 KB |
Output is correct |
| 26 |
Correct |
4 ms |
620 KB |
Output is correct |
| 27 |
Correct |
4 ms |
620 KB |
Output is correct |
| 28 |
Correct |
2 ms |
620 KB |
Output is correct |
| 29 |
Correct |
2 ms |
620 KB |
Output is correct |
| 30 |
Correct |
277 ms |
9452 KB |
Output is correct |
| 31 |
Correct |
307 ms |
9452 KB |
Output is correct |
| 32 |
Correct |
182 ms |
9452 KB |
Output is correct |
| 33 |
Correct |
155 ms |
9452 KB |
Output is correct |
| 34 |
Correct |
146 ms |
9452 KB |
Output is correct |
| 35 |
Correct |
195 ms |
9452 KB |
Output is correct |
| 36 |
Correct |
182 ms |
9456 KB |
Output is correct |
| 37 |
Correct |
157 ms |
9456 KB |
Output is correct |
| 38 |
Correct |
186 ms |
9456 KB |
Output is correct |
| 39 |
Correct |
167 ms |
9456 KB |
Output is correct |
| 40 |
Correct |
184 ms |
9456 KB |
Output is correct |
| 41 |
Correct |
215 ms |
9488 KB |
Output is correct |
| 42 |
Correct |
199 ms |
9544 KB |
Output is correct |
| 43 |
Correct |
170 ms |
9544 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
9544 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '3324' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
484 KB |
Output is correct |
| 3 |
Correct |
2 ms |
544 KB |
Output is correct |
| 4 |
Correct |
3 ms |
544 KB |
Output is correct |
| 5 |
Correct |
2 ms |
544 KB |
Output is correct |
| 6 |
Correct |
2 ms |
544 KB |
Output is correct |
| 7 |
Correct |
2 ms |
544 KB |
Output is correct |
| 8 |
Correct |
3 ms |
544 KB |
Output is correct |
| 9 |
Correct |
3 ms |
544 KB |
Output is correct |
| 10 |
Correct |
4 ms |
544 KB |
Output is correct |
| 11 |
Correct |
2 ms |
544 KB |
Output is correct |
| 12 |
Correct |
3 ms |
544 KB |
Output is correct |
| 13 |
Correct |
3 ms |
544 KB |
Output is correct |
| 14 |
Correct |
2 ms |
544 KB |
Output is correct |
| 15 |
Correct |
3 ms |
600 KB |
Output is correct |
| 16 |
Correct |
3 ms |
612 KB |
Output is correct |
| 17 |
Correct |
2 ms |
612 KB |
Output is correct |
| 18 |
Correct |
3 ms |
612 KB |
Output is correct |
| 19 |
Correct |
2 ms |
612 KB |
Output is correct |
| 20 |
Correct |
3 ms |
612 KB |
Output is correct |
| 21 |
Correct |
2 ms |
612 KB |
Output is correct |
| 22 |
Correct |
2 ms |
620 KB |
Output is correct |
| 23 |
Correct |
2 ms |
620 KB |
Output is correct |
| 24 |
Correct |
3 ms |
620 KB |
Output is correct |
| 25 |
Correct |
3 ms |
620 KB |
Output is correct |
| 26 |
Correct |
4 ms |
620 KB |
Output is correct |
| 27 |
Correct |
4 ms |
620 KB |
Output is correct |
| 28 |
Correct |
2 ms |
620 KB |
Output is correct |
| 29 |
Correct |
2 ms |
620 KB |
Output is correct |
| 30 |
Correct |
277 ms |
9452 KB |
Output is correct |
| 31 |
Correct |
307 ms |
9452 KB |
Output is correct |
| 32 |
Correct |
182 ms |
9452 KB |
Output is correct |
| 33 |
Correct |
155 ms |
9452 KB |
Output is correct |
| 34 |
Correct |
146 ms |
9452 KB |
Output is correct |
| 35 |
Correct |
195 ms |
9452 KB |
Output is correct |
| 36 |
Correct |
182 ms |
9456 KB |
Output is correct |
| 37 |
Correct |
157 ms |
9456 KB |
Output is correct |
| 38 |
Correct |
186 ms |
9456 KB |
Output is correct |
| 39 |
Correct |
167 ms |
9456 KB |
Output is correct |
| 40 |
Correct |
184 ms |
9456 KB |
Output is correct |
| 41 |
Correct |
215 ms |
9488 KB |
Output is correct |
| 42 |
Correct |
199 ms |
9544 KB |
Output is correct |
| 43 |
Correct |
170 ms |
9544 KB |
Output is correct |
| 44 |
Incorrect |
4 ms |
9544 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '3324' |
| 45 |
Halted |
0 ms |
0 KB |
- |
