#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);
vi incycle(N,0);
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]);
incycle[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;
incycle[current]=C;
}
C++;
}
}
//cout << total_distance <<" for walking with books, cycles: " << C << endl;
//edge case: s on correct table
if(cmin[incycle[s]]==cmax[incycle[s]]) {
//cout << "initial move needed\n";
for(int d=1; d<N; d++) {
if(s-d >=0 and cmin[incycle[s-d]]!=cmax[incycle[s-d]]) {
total_distance+=2*d;
break;
}
if(s+d < N and cmin[incycle[s+d]]!=cmax[incycle[s+d]]) {
total_distance+=2*d;
break;
}
}
}
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:78: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]
78 | for(int e=0; e<events.size(); e++) {
| ~^~~~~~~~~~~~~~
books.cpp:83: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]
83 | 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 |
1 ms |
256 KB |
Output is correct |
| 2 |
Correct |
0 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 |
384 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 |
360 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 |
400 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 |
1 ms |
256 KB |
Output is correct |
| 2 |
Correct |
0 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 |
384 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 |
360 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 |
400 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 |
384 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 |
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 |
384 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 |
0 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 |
384 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 |
360 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 |
400 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 |
384 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 |
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 |
384 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 |
243 ms |
12408 KB |
Output is correct |
| 31 |
Correct |
243 ms |
12536 KB |
Output is correct |
| 32 |
Correct |
167 ms |
20440 KB |
Output is correct |
| 33 |
Correct |
183 ms |
24020 KB |
Output is correct |
| 34 |
Correct |
187 ms |
24020 KB |
Output is correct |
| 35 |
Correct |
191 ms |
22868 KB |
Output is correct |
| 36 |
Correct |
185 ms |
18784 KB |
Output is correct |
| 37 |
Correct |
162 ms |
13556 KB |
Output is correct |
| 38 |
Correct |
166 ms |
12664 KB |
Output is correct |
| 39 |
Correct |
163 ms |
12664 KB |
Output is correct |
| 40 |
Correct |
171 ms |
12408 KB |
Output is correct |
| 41 |
Correct |
202 ms |
12408 KB |
Output is correct |
| 42 |
Correct |
184 ms |
12408 KB |
Output is correct |
| 43 |
Correct |
202 ms |
24276 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
512 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 |
1 ms |
256 KB |
Output is correct |
| 2 |
Correct |
0 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 |
384 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 |
360 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 |
400 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 |
384 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 |
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 |
384 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 |
243 ms |
12408 KB |
Output is correct |
| 31 |
Correct |
243 ms |
12536 KB |
Output is correct |
| 32 |
Correct |
167 ms |
20440 KB |
Output is correct |
| 33 |
Correct |
183 ms |
24020 KB |
Output is correct |
| 34 |
Correct |
187 ms |
24020 KB |
Output is correct |
| 35 |
Correct |
191 ms |
22868 KB |
Output is correct |
| 36 |
Correct |
185 ms |
18784 KB |
Output is correct |
| 37 |
Correct |
162 ms |
13556 KB |
Output is correct |
| 38 |
Correct |
166 ms |
12664 KB |
Output is correct |
| 39 |
Correct |
163 ms |
12664 KB |
Output is correct |
| 40 |
Correct |
171 ms |
12408 KB |
Output is correct |
| 41 |
Correct |
202 ms |
12408 KB |
Output is correct |
| 42 |
Correct |
184 ms |
12408 KB |
Output is correct |
| 43 |
Correct |
202 ms |
24276 KB |
Output is correct |
| 44 |
Incorrect |
1 ms |
512 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '2744' |
| 45 |
Halted |
0 ms |
0 KB |
- |
