#include <utility>
#include <algorithm>
#include <math.h>
#include <vector>
#include "books.h"
#define fori(i,n) for(int i=0;i<n;i++)
#define forib(i,n) for(int i=n-1;i>=0;i--)
#define maxl 10000000000
typedef long long lol;
using namespace std;
typedef vector<int> veci;
lol sum=0;
veci merge(veci a ,veci b){
int i=0,j=0;
veci ans;
while(i<a.size()&&j<b.size()){
if(a[i]<b[j]){
ans.push_back(a[i++]);
sum+=j;
}else{
ans.push_back(b[j++]);
}
}
while(i<a.size()){
ans.push_back(a[i++]);
sum+=j;
}
while(j<b.size()){
ans.push_back(b[j++]);
}
return ans;
}
veci mergesort(veci a){
if(a.size()==1){
return a;
}
veci b,c;
fori(i,a.size()){
if(i<a.size()/2){
b.push_back(a[i]);
}else{
c.push_back(a[i]);
}
}
b=mergesort(b);
c=mergesort(c);
return merge(b,c);
}
long long minimum_walk(vector<int> p, int s) {
int n=p.size();
vector<int> a(n,-1);
int cur=s;
do{
sum+=abs(p[cur]-cur);
cur= p[cur];
a[cur]=0;
}while(cur !=s);
int num=1;
vector<int> b(n+1,s);
int mon=0;
fori(i,n){
if(p[i]==i||a[i]!=-1){
continue;
}
int l=-10000000;
int r=n;
int cur=i;
do{
if(cur<s){
l=max(l,cur);
}else{
r=min(r,cur);
}
sum+=abs(p[cur]-cur);
cur= p[cur];
a[cur]=num;
}while(cur !=i);
num++;
b[r-1]=l;
}
bool ok=false;
int minn=n;
forib(i,n){
if(i==s){
break;
}
if(p[i]!=i){
ok=true;
}
minn=min(minn,p[i]);
if(ok&&minn==i){
mon++;
}
}
ok=false;
minn=0;
fori(i,n){
if(i==s){
break;
}
if(p[i]!=i){
ok=true;
}
minn=max(minn,p[i]);
if(ok&&minn==i){
mon++;
}
}
return sum+mon*2;
}
Compilation message
books.cpp: In function 'veci merge(veci, veci)':
books.cpp:17:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(i<a.size()&&j<b.size()){
~^~~~~~~~~
books.cpp:17:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(i<a.size()&&j<b.size()){
~^~~~~~~~~
books.cpp:25:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(i<a.size()){
~^~~~~~~~~
books.cpp:29:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(j<b.size()){
~^~~~~~~~~
books.cpp: In function 'veci mergesort(veci)':
books.cpp:6:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define fori(i,n) for(int i=0;i<n;i++)
books.cpp:39:7:
fori(i,a.size()){
~~~~~~~~~~
books.cpp:39:2: note: in expansion of macro 'fori'
fori(i,a.size()){
^~~~
books.cpp:40:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i<a.size()/2){
~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
348 KB |
Output is correct |
6 |
Correct |
2 ms |
256 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
256 KB |
Output is correct |
10 |
Correct |
2 ms |
428 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
348 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
380 KB |
Output is correct |
15 |
Correct |
2 ms |
256 KB |
Output is correct |
16 |
Correct |
2 ms |
252 KB |
Output is correct |
17 |
Correct |
2 ms |
256 KB |
Output is correct |
18 |
Correct |
2 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
348 KB |
Output is correct |
6 |
Correct |
2 ms |
256 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
256 KB |
Output is correct |
10 |
Correct |
2 ms |
428 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
348 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
380 KB |
Output is correct |
15 |
Correct |
2 ms |
256 KB |
Output is correct |
16 |
Correct |
2 ms |
252 KB |
Output is correct |
17 |
Correct |
2 ms |
256 KB |
Output is correct |
18 |
Correct |
2 ms |
256 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
2 ms |
256 KB |
Output is correct |
21 |
Correct |
2 ms |
452 KB |
Output is correct |
22 |
Correct |
2 ms |
256 KB |
Output is correct |
23 |
Correct |
2 ms |
376 KB |
Output is correct |
24 |
Correct |
2 ms |
380 KB |
Output is correct |
25 |
Correct |
2 ms |
376 KB |
Output is correct |
26 |
Correct |
2 ms |
256 KB |
Output is correct |
27 |
Correct |
2 ms |
376 KB |
Output is correct |
28 |
Correct |
2 ms |
256 KB |
Output is correct |
29 |
Correct |
2 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
348 KB |
Output is correct |
6 |
Correct |
2 ms |
256 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
256 KB |
Output is correct |
10 |
Correct |
2 ms |
428 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
348 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
380 KB |
Output is correct |
15 |
Correct |
2 ms |
256 KB |
Output is correct |
16 |
Correct |
2 ms |
252 KB |
Output is correct |
17 |
Correct |
2 ms |
256 KB |
Output is correct |
18 |
Correct |
2 ms |
256 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
2 ms |
256 KB |
Output is correct |
21 |
Correct |
2 ms |
452 KB |
Output is correct |
22 |
Correct |
2 ms |
256 KB |
Output is correct |
23 |
Correct |
2 ms |
376 KB |
Output is correct |
24 |
Correct |
2 ms |
380 KB |
Output is correct |
25 |
Correct |
2 ms |
376 KB |
Output is correct |
26 |
Correct |
2 ms |
256 KB |
Output is correct |
27 |
Correct |
2 ms |
376 KB |
Output is correct |
28 |
Correct |
2 ms |
256 KB |
Output is correct |
29 |
Correct |
2 ms |
256 KB |
Output is correct |
30 |
Correct |
239 ms |
22648 KB |
Output is correct |
31 |
Correct |
240 ms |
22668 KB |
Output is correct |
32 |
Correct |
140 ms |
22652 KB |
Output is correct |
33 |
Correct |
156 ms |
22740 KB |
Output is correct |
34 |
Correct |
154 ms |
22648 KB |
Output is correct |
35 |
Correct |
159 ms |
22688 KB |
Output is correct |
36 |
Correct |
173 ms |
22648 KB |
Output is correct |
37 |
Correct |
159 ms |
22648 KB |
Output is correct |
38 |
Correct |
165 ms |
22692 KB |
Output is correct |
39 |
Correct |
164 ms |
22652 KB |
Output is correct |
40 |
Correct |
172 ms |
22696 KB |
Output is correct |
41 |
Correct |
194 ms |
22776 KB |
Output is correct |
42 |
Correct |
190 ms |
22784 KB |
Output is correct |
43 |
Correct |
159 ms |
22696 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
256 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 |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
348 KB |
Output is correct |
6 |
Correct |
2 ms |
256 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
256 KB |
Output is correct |
10 |
Correct |
2 ms |
428 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
348 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
380 KB |
Output is correct |
15 |
Correct |
2 ms |
256 KB |
Output is correct |
16 |
Correct |
2 ms |
252 KB |
Output is correct |
17 |
Correct |
2 ms |
256 KB |
Output is correct |
18 |
Correct |
2 ms |
256 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
2 ms |
256 KB |
Output is correct |
21 |
Correct |
2 ms |
452 KB |
Output is correct |
22 |
Correct |
2 ms |
256 KB |
Output is correct |
23 |
Correct |
2 ms |
376 KB |
Output is correct |
24 |
Correct |
2 ms |
380 KB |
Output is correct |
25 |
Correct |
2 ms |
376 KB |
Output is correct |
26 |
Correct |
2 ms |
256 KB |
Output is correct |
27 |
Correct |
2 ms |
376 KB |
Output is correct |
28 |
Correct |
2 ms |
256 KB |
Output is correct |
29 |
Correct |
2 ms |
256 KB |
Output is correct |
30 |
Correct |
239 ms |
22648 KB |
Output is correct |
31 |
Correct |
240 ms |
22668 KB |
Output is correct |
32 |
Correct |
140 ms |
22652 KB |
Output is correct |
33 |
Correct |
156 ms |
22740 KB |
Output is correct |
34 |
Correct |
154 ms |
22648 KB |
Output is correct |
35 |
Correct |
159 ms |
22688 KB |
Output is correct |
36 |
Correct |
173 ms |
22648 KB |
Output is correct |
37 |
Correct |
159 ms |
22648 KB |
Output is correct |
38 |
Correct |
165 ms |
22692 KB |
Output is correct |
39 |
Correct |
164 ms |
22652 KB |
Output is correct |
40 |
Correct |
172 ms |
22696 KB |
Output is correct |
41 |
Correct |
194 ms |
22776 KB |
Output is correct |
42 |
Correct |
190 ms |
22784 KB |
Output is correct |
43 |
Correct |
159 ms |
22696 KB |
Output is correct |
44 |
Incorrect |
2 ms |
256 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '2744' |
45 |
Halted |
0 ms |
0 KB |
- |