QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#233125 | #2528. Mobile Robot | BUET_Twilight# | AC ✓ | 678ms | 19528kb | C++23 | 958b | 2023-10-31 13:43:56 | 2023-10-31 13:43:57 |
Judging History
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(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
long double l = 0;
long double r = 1e17;
cin>>n>>d;
for(int i=0;i<n;i++) {
cin>>ara[i];
rev[n-i-1] = ara[i];
}
for(int i=0;i<80;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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5944kb
input:
2 1 -1 1
output:
0.5
result:
ok single line: '0.5'
Test #2:
score: 0
Accepted
time: 0ms
memory: 5860kb
input:
2 1 0 1
output:
0.0
result:
ok single line: '0.0'
Test #3:
score: 0
Accepted
time: 0ms
memory: 5916kb
input:
2 1 0 0
output:
0.5
result:
ok single line: '0.5'
Test #4:
score: 0
Accepted
time: 0ms
memory: 5860kb
input:
2 1 -10000000000000000 10000000000000000
output:
9999999999999999.5
result:
ok single line: '9999999999999999.5'
Test #5:
score: 0
Accepted
time: 1ms
memory: 5948kb
input:
2 10000000000 0 0
output:
5000000000.0
result:
ok single line: '5000000000.0'
Test #6:
score: 0
Accepted
time: 1ms
memory: 5868kb
input:
2 10000000000 -10000000000000000 10000000000000000
output:
9999995000000000.0
result:
ok single line: '9999995000000000.0'
Test #7:
score: 0
Accepted
time: 1ms
memory: 5964kb
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: 1ms
memory: 5864kb
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: 1ms
memory: 5852kb
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: 1ms
memory: 5852kb
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: 5868kb
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: 5724kb
input:
3 1 1 3 2
output:
1.0
result:
ok single line: '1.0'
Test #13:
score: 0
Accepted
time: 0ms
memory: 5944kb
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: 5876kb
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: 5912kb
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: 0ms
memory: 5948kb
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: 1ms
memory: 5900kb
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: 5860kb
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: 5904kb
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: 480ms
memory: 19396kb
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: 5868kb
input:
5 1 -10 -1 0 1 2
output:
4.0
result:
ok single line: '4.0'
Test #22:
score: 0
Accepted
time: 557ms
memory: 19528kb
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:
4999994999999999.5
result:
ok single line: '4999994999999999.5'
Test #23:
score: 0
Accepted
time: 46ms
memory: 10176kb
input:
100000 1 -583 -8612 9722 -7985 6287 -671 9562 1102 8059 2711 -3166 3225 -8812 -3552 4408 2427 -5229 -9081 -6166 -39 8916 6657 8360 4473 3772 -2598 -1926 -9411 -4413 -5907 -3789 8189 -6980 -592 -3938 7243 -532 234 -5638 9313 4463 9685 -9131 -4109 7652 6911 1949 8427 2683 9987 1179 -8673 2855 -7231 -5...
output:
59762.5
result:
ok single line: '59762.5'
Test #24:
score: 0
Accepted
time: 44ms
memory: 8732kb
input:
100000 1 -99999198 -99999108 -99998834 -99996290 -99991027 -99989962 -99989632 -99988683 -99988479 -99985044 -99982846 -99980801 -99979883 -99977995 -99977143 -99976759 -99976173 -99974386 -99972813 -99972100 -99972092 -99970648 -99968555 -99965699 -99956729 -99955536 -99955208 -99954776 -99953136 -...
output:
99945970.0
result:
ok single line: '99945970.0'
Test #25:
score: 0
Accepted
time: 52ms
memory: 8620kb
input:
100000 1 99996546 99994746 99993446 99991809 99991807 99989710 99987260 99985166 99984943 99982711 99982670 99981566 99981536 99980278 99978158 99977455 99976140 99974738 99973887 99973549 99972752 99972441 99971965 99970660 99966851 99965071 99962198 99958006 99957716 99956710 99956550 99954040 999...
output:
99946766.5
result:
ok single line: '99946766.5'
Test #26:
score: 0
Accepted
time: 49ms
memory: 10368kb
input:
100000 1 -63599340 12134713 14751569 60639761 -90502770 75549834 -25390776 -61747336 18399163 96473627 -72006887 -51730439 -58472860 46064147 -21090910 93175920 35584787 -47336139 15585442 -27004203 28050022 -96893447 -95486116 49304408 72597016 51420075 45158032 48934563 80465443 -67840657 64977536...
output:
100030041.5
result:
ok single line: '100030041.5'
Test #27:
score: 0
Accepted
time: 36ms
memory: 6684kb
input:
100000 1000 -99998653 -99997283 -99997207 -99993344 -99993221 -99989301 -99988498 -99987235 -99985616 -99984333 -99984030 -99983971 -99983517 -99978650 -99978615 -99975625 -99972542 -99971852 -99970274 -99969420 -99968654 -99968616 -99965684 -99964794 -99963302 -99962056 -99960461 -99959474 -9995164...
output:
49998365.5
result:
ok single line: '49998365.5'
Test #28:
score: 0
Accepted
time: 36ms
memory: 8468kb
input:
100000 1000 99999570 99997740 99993133 99991390 99990818 99987647 99987194 99985627 99985192 99982035 99980198 99979859 99978140 99977104 99976435 99975789 99971892 99971515 99970655 99970146 99969234 99969014 99964893 99962544 99961272 99960786 99960433 99955264 99954950 99954902 99953919 99953852 ...
output:
50000439.5
result:
ok single line: '50000439.5'
Test #29:
score: 0
Accepted
time: 55ms
memory: 6704kb
input:
100000 1000 60856084 58148277 -4078235 62006072 -46939709 -98974060 -90491178 65748897 -57667627 36358869 -69476135 31710701 10175494 27319898 51657888 -3333605 -54246412 -91277680 -52546893 32456378 -47098095 18480664 1125344 13552648 -66061096 59906349 -57901943 29702663 -12300872 -67549268 -46802...
output:
149231358.0
result:
ok single line: '149231358.0'
Test #30:
score: 0
Accepted
time: 52ms
memory: 6648kb
input:
100000 10000000000 -9999913514792555 -9999128892345250 -9999006091972906 -9998876100702433 -9998738918995215 -9998497323420770 -9998320530856243 -9998038070684528 -9997971825613071 -9997877023005087 -9997870875964035 -9997562514859003 -9997552544847586 -9997531406772320 -9997449292594299 -9997387525...
output:
9499951420165972.5
result:
ok single line: '9499951420165972.5'
Test #31:
score: 0
Accepted
time: 63ms
memory: 6700kb
input:
100000 10000000000 9999957541295902 9999632341124299 9999392393744950 9999381693997579 9999338275167607 9999302055371418 9999235051177623 9999199187793994 9999183323685659 9999040344648342 9998536329432919 9998446773732239 9998380374074851 9998267316342805 9998215699538013 9998166995278016 999814080...
output:
9499976469102441.0
result:
ok single line: '9499976469102441.0'
Test #32:
score: 0
Accepted
time: 1ms
memory: 5824kb
input:
5 1 1 3 5 9 7
output:
2.5
result:
ok single line: '2.5'
Test #33:
score: 0
Accepted
time: 67ms
memory: 8528kb
input:
100000 10000000000 527679965270656 4910624838155323 3360731978533770 -116923838921508 8957268581890059 8780184453949832 555462578045670 -1514351557304302 -8008533364424397 1020835987517356 4682713484421501 -7503788766591770 7721715657910399 -8096545589847009 7319936981859888 -9938672293049364 873686...
output:
10480796877067284.5
result:
ok single line: '10480796877067284.5'
Test #34:
score: 0
Accepted
time: 51ms
memory: 6644kb
input:
100000 10000000000 -8459079513468224 4374521065795150 5263873516806124 -3824771801533216 9703621014180336 -4756270229411288 -8389013308864992 -3799247487813073 8253907285461284 2844946003788844 3736384833747798 5619288358174746 -7917373545902608 6413580173533839 -4624243785223537 7063534276004728 73...
output:
10465286562786960.5
result:
ok single line: '10465286562786960.5'
Test #35:
score: 0
Accepted
time: 678ms
memory: 19440kb
input:
1000000 10000000000 -4318654196863554 -275219619888671 5562193313500056 4178195030673104 4629750747293997 570434976128040 3653712382065689 -4732093332522913 -5688219122038859 9735702724899422 -1152617053491218 -5720356980411951 -986092999891608 -1552612161361996 -1519536678995098 -2581715135338536 4...
output:
14975895551334817.0
result:
ok single line: '14975895551334817.0'
Test #36:
score: 0
Accepted
time: 1ms
memory: 5948kb
input:
5 1 1 1 1 1 1
output:
2.0
result:
ok single line: '2.0'