#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
bool check(long long x, int n, long long pts[], vector<int> &d, int c){
long long up1,up2,do1,do2;
up1=2e18;
up2=2e18;
do1=-2e18;
do2=-2e18;
//d[i]+d[j]+|pts[i]-y|+|pts[j]-z| <= x
//1:
//y+z>=d[i]+d[j]+pts[i]+pts[j]-x+c
//y+z<=x-d[i]-d[j]+pts[i]+pts[j]-c
//2:
//y-z<=x-d[i]-d[j]+pts[i]-pts[j]-c
//y-z>=d[i]+d[j]-x+pts[i]-pts[j]+c
for(int i = 0;i<n;i++){
for(int j = i+1;j<n;j++){
long long dist1 = d[i]+d[j]+pts[j]-pts[i];
if(dist1<=x){
continue;
}
up1=min(up1,x-d[i]-d[j]+pts[i]+pts[j]-c);
do1=max(do1,d[i]+d[j]+pts[i]+pts[j]-x+c);
up2=min(up2,x-d[i]-d[j]+pts[i]-pts[j]-c);
do2=max(do2,d[i]+d[j]-x+pts[i]-pts[j]+c);
}
}
for(int i = 0;i<n;i++){
for(int j = 0;j<n;j++){
long long y = pts[i];
long long z = pts[j];
if(y+z>=do1&&y+z<=up1&&y-z>=do2&&y-z<=up2){
return 1;
}
}
}
return 0;
}
long long find_shortcut(int n, vector<int> lens, vector<int> d, int c){
long long lo=0;
long long hi=2e18;
long long pts[n];
pts[0]=0;
for(int i = 0;i<n-1;i++){
pts[i+1]=pts[i]+lens[i];
}
while(lo<hi){
long long mid = (lo+hi)/2;
if(check(mid,n,pts,d,c)){
hi=mid;
}
else{
lo=mid+1;
}
}
return lo;
}
Compilation message (stderr)
shortcut.h:1:9: warning: #pragma once in main file
1 | #pragma once
| ^~~~
shortcut_c.h:1:9: warning: #pragma once in main file
1 | #pragma once
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |