QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#233122#2528. Mobile RobotBUET_Twilight#TL 987ms19500kbC++23885b2023-10-31 13:41:292023-10-31 13:41:29

Judging History

你现在查看的是最新测评结果

  • [2023-10-31 13:41:29]
  • 评测
  • 测评结果:TL
  • 用时:987ms
  • 内存:19500kb
  • [2023-10-31 13:41:29]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
const long double eps = 1e-9;
const int N = 1000006;
int ara[N],rev[N];
int n,d;
bool pos(long double a,int ara[]){
    long double l0 = ara[0]-a;
    long double r0 = ara[0]+a;

    for(int i=1;i<n;i++){

        long double l2 = ara[i]-a;
        long double r2 = ara[i]+a;

        l2 = max(l2,l0+d);
        r2 = min(r2,r0+d);
        if( l2-r2>eps ) return false;
        l0 = l2;
        r0 = r2;
    }
    return true;
}

signed main(){
    long double l = 0;
    long double r = 1e18;
    cin>>n>>d;
    for(int i=0;i<n;i++) {
        cin>>ara[i];
        rev[n-i-1] = ara[i];
    }

    for(int i=0;i<200;i++){
        long double mid = (l+r)/2.;
        if(pos(mid,ara) or pos(mid,rev)) r = mid;
        else l = mid;
    }
    cout<<fixed<<setprecision(1)<<r<<endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5900kb

input:

2 1
-1 1

output:

0.5

result:

ok single line: '0.5'

Test #2:

score: 0
Accepted
time: 1ms
memory: 5928kb

input:

2 1
0 1

output:

0.0

result:

ok single line: '0.0'

Test #3:

score: 0
Accepted
time: 1ms
memory: 5860kb

input:

2 1
0 0

output:

0.5

result:

ok single line: '0.5'

Test #4:

score: 0
Accepted
time: 1ms
memory: 5884kb

input:

2 1
-10000000000000000 10000000000000000

output:

9999999999999999.5

result:

ok single line: '9999999999999999.5'

Test #5:

score: 0
Accepted
time: 1ms
memory: 5872kb

input:

2 10000000000
0 0

output:

5000000000.0

result:

ok single line: '5000000000.0'

Test #6:

score: 0
Accepted
time: 1ms
memory: 5884kb

input:

2 10000000000
-10000000000000000 10000000000000000

output:

9999995000000000.0

result:

ok single line: '9999995000000000.0'

Test #7:

score: 0
Accepted
time: 1ms
memory: 5972kb

input:

10 1
0 1 2 3 4 5 6 7 8 9

output:

0.0

result:

ok single line: '0.0'

Test #8:

score: 0
Accepted
time: 0ms
memory: 5872kb

input:

10 1
9 8 7 6 5 4 3 2 1 0

output:

0.0

result:

ok single line: '0.0'

Test #9:

score: 0
Accepted
time: 0ms
memory: 5872kb

input:

10 3
0 1 2 3 4 5 6 7 8 9

output:

9.0

result:

ok single line: '9.0'

Test #10:

score: 0
Accepted
time: 0ms
memory: 5924kb

input:

5 1
1 3 5 7 9

output:

2.0

result:

ok single line: '2.0'

Test #11:

score: 0
Accepted
time: 1ms
memory: 5876kb

input:

10 3
9 8 7 6 5 4 3 2 1 0

output:

9.0

result:

ok single line: '9.0'

Test #12:

score: 0
Accepted
time: 1ms
memory: 5940kb

input:

3 1
1 3 2

output:

1.0

result:

ok single line: '1.0'

Test #13:

score: 0
Accepted
time: 1ms
memory: 5736kb

input:

6 1
3 1 2 5 6 4

output:

2.0

result:

ok single line: '2.0'

Test #14:

score: 0
Accepted
time: 1ms
memory: 5888kb

input:

6 1
4 6 5 2 1 3

output:

2.0

result:

ok single line: '2.0'

Test #15:

score: 0
Accepted
time: 0ms
memory: 5876kb

input:

10 1
6 7 8 9 10 1 2 3 4 5

output:

4.0

result:

ok single line: '4.0'

Test #16:

score: 0
Accepted
time: 1ms
memory: 5928kb

input:

10 10
6 7 8 9 10 1 2 3 4 5

output:

44.5

result:

ok single line: '44.5'

Test #17:

score: 0
Accepted
time: 0ms
memory: 5876kb

input:

6 2
6 3 5 2 4 1

output:

3.5

result:

ok single line: '3.5'

Test #18:

score: 0
Accepted
time: 1ms
memory: 5920kb

input:

10 10000000000
60000000000 70000000000 80000000000 90000000000 100000000000 10000000000 20000000000 30000000000 40000000000 50000000000

output:

40000000000.0

result:

ok single line: '40000000000.0'

Test #19:

score: 0
Accepted
time: 1ms
memory: 5928kb

input:

10 10000000000
6000000000 7000000000 8000000000 9000000000 10000000000 1000000000 2000000000 3000000000 4000000000 5000000000

output:

44500000000.0

result:

ok single line: '44500000000.0'

Test #20:

score: 0
Accepted
time: 987ms
memory: 19500kb

input:

1000000 10000000000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

4999995000000000.0

result:

ok single line: '4999995000000000.0'

Test #21:

score: 0
Accepted
time: 1ms
memory: 5972kb

input:

5 1
-10 -1 0 1 2

output:

4.0

result:

ok single line: '4.0'

Test #22:

score: -100
Time Limit Exceeded

input:

1000000 10000000000
0 1 1 0 0 0 0 -1 -1 1 -1 1 1 0 0 1 -1 1 -1 0 -1 0 -1 1 0 -1 0 -1 -1 -1 1 -1 0 0 1 -1 -1 1 0 0 1 -1 0 1 -1 0 -1 -1 1 -1 1 1 1 -1 0 1 0 0 1 0 1 -1 -1 -1 1 -1 1 0 -1 0 -1 0 0 1 0 1 0 -1 1 -1 0 1 1 0 -1 -1 -1 -1 -1 0 0 0 -1 0 1 1 0 0 0 -1 0 0 -1 -1 0 0 0 0 0 1 -1 1 -1 -1 -1 0 1 1 -1 ...

output:


result: