#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;
int C=0;//number of cycles
vector<bool> visited(N,false);
for(int i=0; i<N; i++) {
if(!visited[i]) {
//cout << "new cycle from " << i << endl;
visited[i]=true;
cmin.push_back(i); //create new cycle
cmax.push_back(i);
total_distance+=abs(i-p[i]);
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;
}
C++;
}
}
//cout << total_distance <<" for walking with books, cycles: " << C << endl;
vector<pair<int,bool>> events={{s,0},{s,1}}; //0 for start, 1 for end
for(int c=0; c<C; c++) {
if(cmin[c]!=cmax[c]) {
events.push_back({cmin[c],0});
events.push_back({cmax[c],1});
}
}
sort(events.begin(),events.end());
int active_c=0;
for(int e=0; e<events.size(); e++) {
if(get<1>(events[e])==false) {//new
active_c++;
} else {//remove
active_c--;
if(active_c==0 and e<events.size()-1) {//there is a next event which needs to be walked to
total_distance+=2*(events[e+1].first-events[e].first);
}
}
}
return total_distance;
}
Compilation message
books.cpp: In function 'long long int minimum_walk(vi, int)':
books.cpp:59:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for(int e=0; e<events.size(); e++) {
| ~^~~~~~~~~~~~~~
books.cpp:64:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | if(active_c==0 and e<events.size()-1) {//there is a next event which needs to be walked to
| ~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 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 |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
256 KB |
Output is correct |
| 6 |
Correct |
0 ms |
256 KB |
Output is correct |
| 7 |
Correct |
1 ms |
256 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
256 KB |
Output is correct |
| 10 |
Correct |
1 ms |
288 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 |
256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 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 |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
256 KB |
Output is correct |
| 6 |
Correct |
0 ms |
256 KB |
Output is correct |
| 7 |
Correct |
1 ms |
256 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
256 KB |
Output is correct |
| 10 |
Correct |
1 ms |
288 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 |
256 KB |
Output is correct |
| 19 |
Correct |
1 ms |
288 KB |
Output is correct |
| 20 |
Correct |
1 ms |
288 KB |
Output is correct |
| 21 |
Correct |
1 ms |
384 KB |
Output is correct |
| 22 |
Correct |
1 ms |
384 KB |
Output is correct |
| 23 |
Correct |
1 ms |
288 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 |
416 KB |
Output is correct |
| 27 |
Correct |
1 ms |
512 KB |
Output is correct |
| 28 |
Correct |
1 ms |
372 KB |
Output is correct |
| 29 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 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 |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
256 KB |
Output is correct |
| 6 |
Correct |
0 ms |
256 KB |
Output is correct |
| 7 |
Correct |
1 ms |
256 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
256 KB |
Output is correct |
| 10 |
Correct |
1 ms |
288 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 |
256 KB |
Output is correct |
| 19 |
Correct |
1 ms |
288 KB |
Output is correct |
| 20 |
Correct |
1 ms |
288 KB |
Output is correct |
| 21 |
Correct |
1 ms |
384 KB |
Output is correct |
| 22 |
Correct |
1 ms |
384 KB |
Output is correct |
| 23 |
Correct |
1 ms |
288 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 |
416 KB |
Output is correct |
| 27 |
Correct |
1 ms |
512 KB |
Output is correct |
| 28 |
Correct |
1 ms |
372 KB |
Output is correct |
| 29 |
Correct |
1 ms |
384 KB |
Output is correct |
| 30 |
Correct |
250 ms |
13904 KB |
Output is correct |
| 31 |
Correct |
235 ms |
13892 KB |
Output is correct |
| 32 |
Correct |
174 ms |
21920 KB |
Output is correct |
| 33 |
Correct |
187 ms |
25404 KB |
Output is correct |
| 34 |
Correct |
209 ms |
25496 KB |
Output is correct |
| 35 |
Correct |
217 ms |
24272 KB |
Output is correct |
| 36 |
Correct |
180 ms |
20100 KB |
Output is correct |
| 37 |
Correct |
214 ms |
14836 KB |
Output is correct |
| 38 |
Correct |
168 ms |
14276 KB |
Output is correct |
| 39 |
Correct |
167 ms |
14076 KB |
Output is correct |
| 40 |
Correct |
179 ms |
13896 KB |
Output is correct |
| 41 |
Correct |
183 ms |
13896 KB |
Output is correct |
| 42 |
Correct |
184 ms |
13844 KB |
Output is correct |
| 43 |
Correct |
222 ms |
25936 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
360 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '2744' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 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 |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
256 KB |
Output is correct |
| 6 |
Correct |
0 ms |
256 KB |
Output is correct |
| 7 |
Correct |
1 ms |
256 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
256 KB |
Output is correct |
| 10 |
Correct |
1 ms |
288 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 |
256 KB |
Output is correct |
| 19 |
Correct |
1 ms |
288 KB |
Output is correct |
| 20 |
Correct |
1 ms |
288 KB |
Output is correct |
| 21 |
Correct |
1 ms |
384 KB |
Output is correct |
| 22 |
Correct |
1 ms |
384 KB |
Output is correct |
| 23 |
Correct |
1 ms |
288 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 |
416 KB |
Output is correct |
| 27 |
Correct |
1 ms |
512 KB |
Output is correct |
| 28 |
Correct |
1 ms |
372 KB |
Output is correct |
| 29 |
Correct |
1 ms |
384 KB |
Output is correct |
| 30 |
Correct |
250 ms |
13904 KB |
Output is correct |
| 31 |
Correct |
235 ms |
13892 KB |
Output is correct |
| 32 |
Correct |
174 ms |
21920 KB |
Output is correct |
| 33 |
Correct |
187 ms |
25404 KB |
Output is correct |
| 34 |
Correct |
209 ms |
25496 KB |
Output is correct |
| 35 |
Correct |
217 ms |
24272 KB |
Output is correct |
| 36 |
Correct |
180 ms |
20100 KB |
Output is correct |
| 37 |
Correct |
214 ms |
14836 KB |
Output is correct |
| 38 |
Correct |
168 ms |
14276 KB |
Output is correct |
| 39 |
Correct |
167 ms |
14076 KB |
Output is correct |
| 40 |
Correct |
179 ms |
13896 KB |
Output is correct |
| 41 |
Correct |
183 ms |
13896 KB |
Output is correct |
| 42 |
Correct |
184 ms |
13844 KB |
Output is correct |
| 43 |
Correct |
222 ms |
25936 KB |
Output is correct |
| 44 |
Incorrect |
1 ms |
360 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '2744' |
| 45 |
Halted |
0 ms |
0 KB |
- |
