#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=-1;
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 l=s+1;int r=s;
while(l!=0 || r!=n-1){
mon++;
bool ok=(l==0);
int ll=l;
int rr=r;
if(l!=0){
l--;
ll--;
cur=p[l];
if(cur<s){
ll=min(ll,cur);
}else{
rr=max(rr,cur);
}
}else{
r++;
rr++;
cur=p[r];
if(cur<s){
ll=min(ll,cur);
}else{
rr=max(rr,cur);
}
}
while(ll!=l|| r!=rr){
ok=true;
sum+=mon*2;
mon=0;
while(r<rr){
r++;
cur=p[r];
if(cur<s){
ll=min(ll,cur);
}else{
rr=max(rr,cur);
}
}
while(l>ll){
l--;
cur=p[l];
if(cur<s){
ll=min(ll,cur);
}else{
rr=max(rr,cur);
}
}
}
if(l==0 && !ok){
mon=0;
}
}
return sum;
}
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){
~^~~~~~~~~~~
books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:82:7: warning: unused variable 'ok' [-Wunused-variable]
bool ok=false;
^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 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 |
252 KB |
Output is correct |
6 |
Correct |
2 ms |
256 KB |
Output is correct |
7 |
Correct |
2 ms |
256 KB |
Output is correct |
8 |
Correct |
2 ms |
256 KB |
Output is correct |
9 |
Correct |
2 ms |
348 KB |
Output is correct |
10 |
Correct |
2 ms |
348 KB |
Output is correct |
11 |
Correct |
2 ms |
256 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
256 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
256 KB |
Output is correct |
16 |
Correct |
2 ms |
256 KB |
Output is correct |
17 |
Correct |
2 ms |
376 KB |
Output is correct |
18 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 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 |
252 KB |
Output is correct |
6 |
Correct |
2 ms |
256 KB |
Output is correct |
7 |
Correct |
2 ms |
256 KB |
Output is correct |
8 |
Correct |
2 ms |
256 KB |
Output is correct |
9 |
Correct |
2 ms |
348 KB |
Output is correct |
10 |
Correct |
2 ms |
348 KB |
Output is correct |
11 |
Correct |
2 ms |
256 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
256 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
256 KB |
Output is correct |
16 |
Correct |
2 ms |
256 KB |
Output is correct |
17 |
Correct |
2 ms |
376 KB |
Output is correct |
18 |
Correct |
2 ms |
376 KB |
Output is correct |
19 |
Correct |
2 ms |
348 KB |
Output is correct |
20 |
Correct |
2 ms |
376 KB |
Output is correct |
21 |
Correct |
2 ms |
252 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 |
256 KB |
Output is correct |
25 |
Correct |
2 ms |
256 KB |
Output is correct |
26 |
Correct |
2 ms |
256 KB |
Output is correct |
27 |
Correct |
2 ms |
256 KB |
Output is correct |
28 |
Correct |
2 ms |
376 KB |
Output is correct |
29 |
Correct |
2 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 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 |
252 KB |
Output is correct |
6 |
Correct |
2 ms |
256 KB |
Output is correct |
7 |
Correct |
2 ms |
256 KB |
Output is correct |
8 |
Correct |
2 ms |
256 KB |
Output is correct |
9 |
Correct |
2 ms |
348 KB |
Output is correct |
10 |
Correct |
2 ms |
348 KB |
Output is correct |
11 |
Correct |
2 ms |
256 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
256 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
256 KB |
Output is correct |
16 |
Correct |
2 ms |
256 KB |
Output is correct |
17 |
Correct |
2 ms |
376 KB |
Output is correct |
18 |
Correct |
2 ms |
376 KB |
Output is correct |
19 |
Correct |
2 ms |
348 KB |
Output is correct |
20 |
Correct |
2 ms |
376 KB |
Output is correct |
21 |
Correct |
2 ms |
252 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 |
256 KB |
Output is correct |
25 |
Correct |
2 ms |
256 KB |
Output is correct |
26 |
Correct |
2 ms |
256 KB |
Output is correct |
27 |
Correct |
2 ms |
256 KB |
Output is correct |
28 |
Correct |
2 ms |
376 KB |
Output is correct |
29 |
Correct |
2 ms |
256 KB |
Output is correct |
30 |
Correct |
210 ms |
15916 KB |
Output is correct |
31 |
Correct |
208 ms |
15924 KB |
Output is correct |
32 |
Correct |
143 ms |
16016 KB |
Output is correct |
33 |
Correct |
155 ms |
15992 KB |
Output is correct |
34 |
Correct |
156 ms |
15916 KB |
Output is correct |
35 |
Correct |
158 ms |
15920 KB |
Output is correct |
36 |
Correct |
156 ms |
15932 KB |
Output is correct |
37 |
Correct |
169 ms |
15936 KB |
Output is correct |
38 |
Correct |
170 ms |
15928 KB |
Output is correct |
39 |
Correct |
163 ms |
15916 KB |
Output is correct |
40 |
Correct |
173 ms |
16016 KB |
Output is correct |
41 |
Correct |
193 ms |
15920 KB |
Output is correct |
42 |
Correct |
188 ms |
15916 KB |
Output is correct |
43 |
Correct |
154 ms |
15916 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
2 ms |
380 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
348 KB |
Output is correct |
6 |
Incorrect |
2 ms |
376 KB |
3rd lines differ - on the 1st token, expected: '22140', found: '22144' |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 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 |
252 KB |
Output is correct |
6 |
Correct |
2 ms |
256 KB |
Output is correct |
7 |
Correct |
2 ms |
256 KB |
Output is correct |
8 |
Correct |
2 ms |
256 KB |
Output is correct |
9 |
Correct |
2 ms |
348 KB |
Output is correct |
10 |
Correct |
2 ms |
348 KB |
Output is correct |
11 |
Correct |
2 ms |
256 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
256 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
256 KB |
Output is correct |
16 |
Correct |
2 ms |
256 KB |
Output is correct |
17 |
Correct |
2 ms |
376 KB |
Output is correct |
18 |
Correct |
2 ms |
376 KB |
Output is correct |
19 |
Correct |
2 ms |
348 KB |
Output is correct |
20 |
Correct |
2 ms |
376 KB |
Output is correct |
21 |
Correct |
2 ms |
252 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 |
256 KB |
Output is correct |
25 |
Correct |
2 ms |
256 KB |
Output is correct |
26 |
Correct |
2 ms |
256 KB |
Output is correct |
27 |
Correct |
2 ms |
256 KB |
Output is correct |
28 |
Correct |
2 ms |
376 KB |
Output is correct |
29 |
Correct |
2 ms |
256 KB |
Output is correct |
30 |
Correct |
210 ms |
15916 KB |
Output is correct |
31 |
Correct |
208 ms |
15924 KB |
Output is correct |
32 |
Correct |
143 ms |
16016 KB |
Output is correct |
33 |
Correct |
155 ms |
15992 KB |
Output is correct |
34 |
Correct |
156 ms |
15916 KB |
Output is correct |
35 |
Correct |
158 ms |
15920 KB |
Output is correct |
36 |
Correct |
156 ms |
15932 KB |
Output is correct |
37 |
Correct |
169 ms |
15936 KB |
Output is correct |
38 |
Correct |
170 ms |
15928 KB |
Output is correct |
39 |
Correct |
163 ms |
15916 KB |
Output is correct |
40 |
Correct |
173 ms |
16016 KB |
Output is correct |
41 |
Correct |
193 ms |
15920 KB |
Output is correct |
42 |
Correct |
188 ms |
15916 KB |
Output is correct |
43 |
Correct |
154 ms |
15916 KB |
Output is correct |
44 |
Correct |
2 ms |
376 KB |
Output is correct |
45 |
Correct |
2 ms |
256 KB |
Output is correct |
46 |
Correct |
2 ms |
380 KB |
Output is correct |
47 |
Correct |
2 ms |
256 KB |
Output is correct |
48 |
Correct |
2 ms |
348 KB |
Output is correct |
49 |
Incorrect |
2 ms |
376 KB |
3rd lines differ - on the 1st token, expected: '22140', found: '22144' |
50 |
Halted |
0 ms |
0 KB |
- |