#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
long long minimum_walk(vi p, int s) {
int N=p.size();
long long total_distance=0;
vi cmin; //cycle min and max positions
vi cmax;
vector<bool> cfound;
int C=0;//number of cycles
vector<bool> visited(N,false);
vi cycleof(N,0);
for(int i=0; i<N; i++) {
if(!visited[i]) {
//cout << "new cycle from " << i << endl;
visited[i]=true;
if(p[i]!=i) {
cmin.push_back(i); //create new cycle
cmax.push_back(i);
cfound.push_back(false);
total_distance+=abs(i-p[i]);
cycleof[i]=C;
for(int current=p[i]; current!=i; current=p[current]) { //add other points
cmin[C]=min(cmin[C],current);
cmax[C]=max(cmax[C],current);
total_distance+=abs(current-p[current]);
visited[current]=true;
cycleof[current]=C;
}
C++;
} else {
cycleof[i]=-1;
}
}
}
//cout << total_distance <<" for walking with books, cycles: " << C << endl;
int foundc=0;
int ml,mr,l,r; //maxl maxr currentl currentr
ml=mr=l=r=s;
while(foundc<C) { //not all cycles have been found
//cout << ml << ' ' << l << ' ' << r << ' ' << mr << ' ' << foundc << endl;
if(ml>l and mr<r) { //all directly reachable cycles visited
for(int d=1; d<N; d++) {
if(mr+d<N and cycleof[mr+d]!=-1 and !cfound[cycleof[mr+d]]) { //found one to the right
r=mr=mr+d;
total_distance+=2*d;
//cout << "walking an extra " << d << " meters (twice) to reach other cycle to the left\n";
break;
} else if(ml-d>=0 and cycleof[ml-d]!=-1 and !cfound[cycleof[ml-d]]) { //found one to the left
l=ml=ml-d;
total_distance+=2*d;
//cout << "walking an extra " << d << " meters (twice) to reach other cycle to the right\n";
break;
}
}
}
while(ml<=l) { //search for new cycles in reachable range
int i=l;
if(cycleof[i]!=-1 and !cfound[cycleof[i]]) {
cfound[cycleof[i]]=true;
ml=min(ml,cmin[cycleof[i]]);
mr=max(mr,cmax[cycleof[i]]);
foundc++;
//cout << "found cycle " << cycleof[i] << " at " << i << endl;
}
l--;
}
while(mr>=r) {
int i=r;
if(cycleof[i]!=-1 and !cfound[cycleof[i]]) {
cfound[cycleof[i]]=true;
ml=min(ml,cmin[cycleof[i]]);
mr=max(mr,cmax[cycleof[i]]);
foundc++;
//cout << "found cycle " << cycleof[i] << " at " << i << endl;
}
r++;
}
//clock_t start_time = clock();
// looping till required time is not achieved
//while (clock() < start_time + 1000000);
}
return total_distance;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Correct |
1 ms |
256 KB |
Output is correct |
| 3 |
Correct |
1 ms |
256 KB |
Output is correct |
| 4 |
Correct |
1 ms |
256 KB |
Output is correct |
| 5 |
Correct |
1 ms |
256 KB |
Output is correct |
| 6 |
Correct |
1 ms |
256 KB |
Output is correct |
| 7 |
Correct |
1 ms |
256 KB |
Output is correct |
| 8 |
Correct |
1 ms |
256 KB |
Output is correct |
| 9 |
Correct |
1 ms |
256 KB |
Output is correct |
| 10 |
Correct |
1 ms |
256 KB |
Output is correct |
| 11 |
Correct |
1 ms |
256 KB |
Output is correct |
| 12 |
Correct |
1 ms |
256 KB |
Output is correct |
| 13 |
Correct |
1 ms |
256 KB |
Output is correct |
| 14 |
Correct |
1 ms |
256 KB |
Output is correct |
| 15 |
Correct |
1 ms |
256 KB |
Output is correct |
| 16 |
Correct |
1 ms |
256 KB |
Output is correct |
| 17 |
Correct |
1 ms |
256 KB |
Output is correct |
| 18 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Correct |
1 ms |
256 KB |
Output is correct |
| 3 |
Correct |
1 ms |
256 KB |
Output is correct |
| 4 |
Correct |
1 ms |
256 KB |
Output is correct |
| 5 |
Correct |
1 ms |
256 KB |
Output is correct |
| 6 |
Correct |
1 ms |
256 KB |
Output is correct |
| 7 |
Correct |
1 ms |
256 KB |
Output is correct |
| 8 |
Correct |
1 ms |
256 KB |
Output is correct |
| 9 |
Correct |
1 ms |
256 KB |
Output is correct |
| 10 |
Correct |
1 ms |
256 KB |
Output is correct |
| 11 |
Correct |
1 ms |
256 KB |
Output is correct |
| 12 |
Correct |
1 ms |
256 KB |
Output is correct |
| 13 |
Correct |
1 ms |
256 KB |
Output is correct |
| 14 |
Correct |
1 ms |
256 KB |
Output is correct |
| 15 |
Correct |
1 ms |
256 KB |
Output is correct |
| 16 |
Correct |
1 ms |
256 KB |
Output is correct |
| 17 |
Correct |
1 ms |
256 KB |
Output is correct |
| 18 |
Correct |
1 ms |
384 KB |
Output is correct |
| 19 |
Correct |
1 ms |
256 KB |
Output is correct |
| 20 |
Correct |
1 ms |
384 KB |
Output is correct |
| 21 |
Correct |
1 ms |
256 KB |
Output is correct |
| 22 |
Correct |
1 ms |
384 KB |
Output is correct |
| 23 |
Correct |
1 ms |
384 KB |
Output is correct |
| 24 |
Correct |
1 ms |
384 KB |
Output is correct |
| 25 |
Correct |
1 ms |
384 KB |
Output is correct |
| 26 |
Correct |
1 ms |
256 KB |
Output is correct |
| 27 |
Correct |
1 ms |
384 KB |
Output is correct |
| 28 |
Correct |
1 ms |
384 KB |
Output is correct |
| 29 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Correct |
1 ms |
256 KB |
Output is correct |
| 3 |
Correct |
1 ms |
256 KB |
Output is correct |
| 4 |
Correct |
1 ms |
256 KB |
Output is correct |
| 5 |
Correct |
1 ms |
256 KB |
Output is correct |
| 6 |
Correct |
1 ms |
256 KB |
Output is correct |
| 7 |
Correct |
1 ms |
256 KB |
Output is correct |
| 8 |
Correct |
1 ms |
256 KB |
Output is correct |
| 9 |
Correct |
1 ms |
256 KB |
Output is correct |
| 10 |
Correct |
1 ms |
256 KB |
Output is correct |
| 11 |
Correct |
1 ms |
256 KB |
Output is correct |
| 12 |
Correct |
1 ms |
256 KB |
Output is correct |
| 13 |
Correct |
1 ms |
256 KB |
Output is correct |
| 14 |
Correct |
1 ms |
256 KB |
Output is correct |
| 15 |
Correct |
1 ms |
256 KB |
Output is correct |
| 16 |
Correct |
1 ms |
256 KB |
Output is correct |
| 17 |
Correct |
1 ms |
256 KB |
Output is correct |
| 18 |
Correct |
1 ms |
384 KB |
Output is correct |
| 19 |
Correct |
1 ms |
256 KB |
Output is correct |
| 20 |
Correct |
1 ms |
384 KB |
Output is correct |
| 21 |
Correct |
1 ms |
256 KB |
Output is correct |
| 22 |
Correct |
1 ms |
384 KB |
Output is correct |
| 23 |
Correct |
1 ms |
384 KB |
Output is correct |
| 24 |
Correct |
1 ms |
384 KB |
Output is correct |
| 25 |
Correct |
1 ms |
384 KB |
Output is correct |
| 26 |
Correct |
1 ms |
256 KB |
Output is correct |
| 27 |
Correct |
1 ms |
384 KB |
Output is correct |
| 28 |
Correct |
1 ms |
384 KB |
Output is correct |
| 29 |
Correct |
1 ms |
384 KB |
Output is correct |
| 30 |
Correct |
288 ms |
18936 KB |
Output is correct |
| 31 |
Correct |
269 ms |
18936 KB |
Output is correct |
| 32 |
Correct |
160 ms |
18936 KB |
Output is correct |
| 33 |
Correct |
177 ms |
20716 KB |
Output is correct |
| 34 |
Correct |
179 ms |
20716 KB |
Output is correct |
| 35 |
Correct |
178 ms |
20836 KB |
Output is correct |
| 36 |
Correct |
180 ms |
20716 KB |
Output is correct |
| 37 |
Correct |
170 ms |
19196 KB |
Output is correct |
| 38 |
Correct |
187 ms |
18992 KB |
Output is correct |
| 39 |
Correct |
172 ms |
18936 KB |
Output is correct |
| 40 |
Correct |
181 ms |
18936 KB |
Output is correct |
| 41 |
Correct |
198 ms |
18936 KB |
Output is correct |
| 42 |
Correct |
195 ms |
18952 KB |
Output is correct |
| 43 |
Correct |
185 ms |
21024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 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 |
1 ms |
256 KB |
Output is correct |
| 2 |
Correct |
1 ms |
256 KB |
Output is correct |
| 3 |
Correct |
1 ms |
256 KB |
Output is correct |
| 4 |
Correct |
1 ms |
256 KB |
Output is correct |
| 5 |
Correct |
1 ms |
256 KB |
Output is correct |
| 6 |
Correct |
1 ms |
256 KB |
Output is correct |
| 7 |
Correct |
1 ms |
256 KB |
Output is correct |
| 8 |
Correct |
1 ms |
256 KB |
Output is correct |
| 9 |
Correct |
1 ms |
256 KB |
Output is correct |
| 10 |
Correct |
1 ms |
256 KB |
Output is correct |
| 11 |
Correct |
1 ms |
256 KB |
Output is correct |
| 12 |
Correct |
1 ms |
256 KB |
Output is correct |
| 13 |
Correct |
1 ms |
256 KB |
Output is correct |
| 14 |
Correct |
1 ms |
256 KB |
Output is correct |
| 15 |
Correct |
1 ms |
256 KB |
Output is correct |
| 16 |
Correct |
1 ms |
256 KB |
Output is correct |
| 17 |
Correct |
1 ms |
256 KB |
Output is correct |
| 18 |
Correct |
1 ms |
384 KB |
Output is correct |
| 19 |
Correct |
1 ms |
256 KB |
Output is correct |
| 20 |
Correct |
1 ms |
384 KB |
Output is correct |
| 21 |
Correct |
1 ms |
256 KB |
Output is correct |
| 22 |
Correct |
1 ms |
384 KB |
Output is correct |
| 23 |
Correct |
1 ms |
384 KB |
Output is correct |
| 24 |
Correct |
1 ms |
384 KB |
Output is correct |
| 25 |
Correct |
1 ms |
384 KB |
Output is correct |
| 26 |
Correct |
1 ms |
256 KB |
Output is correct |
| 27 |
Correct |
1 ms |
384 KB |
Output is correct |
| 28 |
Correct |
1 ms |
384 KB |
Output is correct |
| 29 |
Correct |
1 ms |
384 KB |
Output is correct |
| 30 |
Correct |
288 ms |
18936 KB |
Output is correct |
| 31 |
Correct |
269 ms |
18936 KB |
Output is correct |
| 32 |
Correct |
160 ms |
18936 KB |
Output is correct |
| 33 |
Correct |
177 ms |
20716 KB |
Output is correct |
| 34 |
Correct |
179 ms |
20716 KB |
Output is correct |
| 35 |
Correct |
178 ms |
20836 KB |
Output is correct |
| 36 |
Correct |
180 ms |
20716 KB |
Output is correct |
| 37 |
Correct |
170 ms |
19196 KB |
Output is correct |
| 38 |
Correct |
187 ms |
18992 KB |
Output is correct |
| 39 |
Correct |
172 ms |
18936 KB |
Output is correct |
| 40 |
Correct |
181 ms |
18936 KB |
Output is correct |
| 41 |
Correct |
198 ms |
18936 KB |
Output is correct |
| 42 |
Correct |
195 ms |
18952 KB |
Output is correct |
| 43 |
Correct |
185 ms |
21024 KB |
Output is correct |
| 44 |
Incorrect |
1 ms |
384 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '3324' |
| 45 |
Halted |
0 ms |
0 KB |
- |
