#include <cstdio>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <tuple>
#include <climits>
using namespace std;
bool isSubtask3(int s) {return s==0;}
bool isSubtask4(int n) {return n<=1000;}
long long subtask3(vector<int> p, int s = 0, int e = -1 , int dir = 1) {
int n = p.size(), last = s;
if (e==-1) e = n-1;
long long total = 0;
for(int i=s; dir==1 && i<=e || dir==-1 && i>=e; i += dir) {
if (i==p[i]) continue;
if (dir*(i-last) > 0) total += abs(i-last)*2;
total += abs(p[i]-i);
last = dir==1? max(last,p[i]):min(last,p[i]);
}
return total;
}
long long cal(vector<int> p, int l, int r, int lmost, int rmost, vector<vector<long long>>& dp) {
if (dp[l][r]!=LLONG_MAX) return dp[l][r];
int n = p.size();
long long temp1=LLONG_MAX, temp2=LLONG_MAX;
if (l>0) {
temp1 = abs(p[l-1]-(l-1)); if(l-1 < lmost) temp1 += 2;
int lmostN = min(lmost,min(l-1,p[l-1])), rmostN = max(rmost,p[l-1]);
temp1 += cal(p,l-1,r,lmostN,rmostN,dp);
}
if (r<n-1) {
temp2 = abs(p[r+1]-(r+1)); if(r+1 > rmost) temp2 += 2;
int lmostN = min(lmost,p[r+1]), rmostN = max(rmost,max(r+1,p[r+1]));
temp2 += cal(p,l,r+1,lmostN,rmostN,dp);
}
dp[l][r] = min(temp1,temp2);
return dp[l][r];
}
long long subtask4(vector<int> p, int s) {
int n = p.size();
// long long move = 0;
int start; for(start = 0; start < s; start++) if(start!=p[start]) break;
int end; for(end = n-1; end > s; end--) if(end!=p[end]) break;
for(int i = 0; i <= end-start; i++) p[i] = p[i+start]-start;
s -= start; n = end-start+1; p.resize(n);
vector<vector<long long>> dp(n,vector<long long>(n,LLONG_MAX));
dp[0][n-1]=0;
int l=s, r=s, lmost = min(s,p[s]), rmost = max(s,p[s]);
return cal(p,l,r,lmost,rmost,dp)+abs(p[s]-s);
}
pair<int,int> extend(int l, int r, vector<int>& lmost, vector<int>& rmost) {
while(l > min(lmost[l],lmost[r]) || r < max(rmost[l],rmost[r])) {
l=min(l,min(lmost[l],lmost[r]));
r=max(r,max(rmost[r],rmost[l]));
}
return make_pair(l,r);
}
long long fulltask(vector<int> p, int s) {
int n = p.size();
// curtail ignorable head and tail.
int start; for(start = 0; start < s; start++) if(start!=p[start]) break;
int end; for(end = n-1; end > s; end--) if(end!=p[end]) break;
for(int i = 0; i <= end-start; i++) p[i] = p[i+start]-start;
s -= start; n = end-start+1; p.resize(n);
// printf("s=%d, n=%d\n",s,n);
int l=s, lStart=s, r=s, rStart=s, moveL=0, moveR=0;
long long totalMove=0, totalJump=0;
for(int i=0; i<n; i++) totalJump += abs(p[i]-i);
// printf("totalJump=%d\n",totalJump);
vector<int> lmost(n), rmost(n);
l = lmost[s] = min(s,p[s]), r = rmost[s] = max(s,p[s]);
for(int i=s-1; i>=0; i--) {lmost[i] = min(lmost[i+1],p[i]); rmost[i] = max(rmost[i+1],p[i]);}
for(int i=s+1; i<n ; i++) {lmost[i] = min(lmost[i-1],p[i]); rmost[i] = max(rmost[i-1],p[i]);}
tie(l,r) = extend(l,r,lmost,rmost);
while(0<l || r<n-1) {
totalMove++; if(r<n-1) r++; if(l>0) l--;
tie(l,r) = extend(l,r,lmost,rmost);
}
return totalMove*2+totalJump;
}
long long minimum_walk(std::vector<int> p, int s) {
// if (isSubtask3(s)) return subtask3(p);
// if (isSubtask4(s)) return subtask4(p,s);
return fulltask(p,s);
}
Compilation message
books.cpp: In function 'long long int subtask3(std::vector<int>, int, int, int)':
books.cpp:18:25: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
18 | for(int i=s; dir==1 && i<=e || dir==-1 && i>=e; i += dir) {
| ~~~~~~~^~~~~~~
books.cpp: In function 'long long int fulltask(std::vector<int>, int)':
books.cpp:80:14: warning: unused variable 'lStart' [-Wunused-variable]
80 | int l=s, lStart=s, r=s, rStart=s, moveL=0, moveR=0;
| ^~~~~~
books.cpp:80:29: warning: unused variable 'rStart' [-Wunused-variable]
80 | int l=s, lStart=s, r=s, rStart=s, moveL=0, moveR=0;
| ^~~~~~
books.cpp:80:39: warning: unused variable 'moveL' [-Wunused-variable]
80 | int l=s, lStart=s, r=s, rStart=s, moveL=0, moveR=0;
| ^~~~~
books.cpp:80:48: warning: unused variable 'moveR' [-Wunused-variable]
80 | int l=s, lStart=s, r=s, rStart=s, moveL=0, moveR=0;
| ^~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
0 ms |
360 KB |
Output is correct |
26 |
Correct |
0 ms |
352 KB |
Output is correct |
27 |
Correct |
0 ms |
348 KB |
Output is correct |
28 |
Correct |
1 ms |
344 KB |
Output is correct |
29 |
Correct |
0 ms |
356 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
0 ms |
360 KB |
Output is correct |
26 |
Correct |
0 ms |
352 KB |
Output is correct |
27 |
Correct |
0 ms |
348 KB |
Output is correct |
28 |
Correct |
1 ms |
344 KB |
Output is correct |
29 |
Correct |
0 ms |
356 KB |
Output is correct |
30 |
Correct |
92 ms |
25216 KB |
Output is correct |
31 |
Correct |
83 ms |
25364 KB |
Output is correct |
32 |
Correct |
84 ms |
17752 KB |
Output is correct |
33 |
Correct |
109 ms |
25172 KB |
Output is correct |
34 |
Correct |
85 ms |
25172 KB |
Output is correct |
35 |
Correct |
89 ms |
25368 KB |
Output is correct |
36 |
Correct |
98 ms |
25176 KB |
Output is correct |
37 |
Correct |
86 ms |
25272 KB |
Output is correct |
38 |
Correct |
86 ms |
25480 KB |
Output is correct |
39 |
Correct |
82 ms |
25248 KB |
Output is correct |
40 |
Correct |
94 ms |
25172 KB |
Output is correct |
41 |
Correct |
82 ms |
25164 KB |
Output is correct |
42 |
Correct |
94 ms |
25172 KB |
Output is correct |
43 |
Correct |
83 ms |
25284 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Incorrect |
0 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '2094', found: '1592' |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
0 ms |
360 KB |
Output is correct |
26 |
Correct |
0 ms |
352 KB |
Output is correct |
27 |
Correct |
0 ms |
348 KB |
Output is correct |
28 |
Correct |
1 ms |
344 KB |
Output is correct |
29 |
Correct |
0 ms |
356 KB |
Output is correct |
30 |
Correct |
92 ms |
25216 KB |
Output is correct |
31 |
Correct |
83 ms |
25364 KB |
Output is correct |
32 |
Correct |
84 ms |
17752 KB |
Output is correct |
33 |
Correct |
109 ms |
25172 KB |
Output is correct |
34 |
Correct |
85 ms |
25172 KB |
Output is correct |
35 |
Correct |
89 ms |
25368 KB |
Output is correct |
36 |
Correct |
98 ms |
25176 KB |
Output is correct |
37 |
Correct |
86 ms |
25272 KB |
Output is correct |
38 |
Correct |
86 ms |
25480 KB |
Output is correct |
39 |
Correct |
82 ms |
25248 KB |
Output is correct |
40 |
Correct |
94 ms |
25172 KB |
Output is correct |
41 |
Correct |
82 ms |
25164 KB |
Output is correct |
42 |
Correct |
94 ms |
25172 KB |
Output is correct |
43 |
Correct |
83 ms |
25284 KB |
Output is correct |
44 |
Correct |
0 ms |
348 KB |
Output is correct |
45 |
Correct |
0 ms |
348 KB |
Output is correct |
46 |
Correct |
0 ms |
344 KB |
Output is correct |
47 |
Incorrect |
0 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '2094', found: '1592' |
48 |
Halted |
0 ms |
0 KB |
- |