Submission #1757387
Source Code Expand
#include <bits/stdc++.h> using namespace std;int a[1<<19],n,s,g,x,y,l,r,p,q,m,b,i;double t,c,f,d,e;int main(){cin>>n>>s>>g;for(;i<2*n;i++)cin>>a[i];a[2*n]=a[n*2+1]=g;p=s;for(;;){y=m=b=q+1;l=a[2*y];r=a[y*2+1];c=l-p;f=r-p;for(;y<=n;y++){l=a[y*2];r=a[y*2+1];d=l-p;d/=y-q;e=r-p;e/=y-q;if(f<d){x=a[b*2+1];t+=hypot(p-x,q-b);p=x;q=b;break;}if(c>e){x=a[m*2];t+=hypot(p-x,q-m);p=x;q=m;break;}if(c<d){c=d;m=y;}if(f>e){f=e;b=y;}}if(y>n){t+=hypot(p-g,q-n);break;}}printf("%.17f\n",t);}
Submission Info
Submission Time | |
---|---|
Task | D - レースゲーム |
User | omi |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 474 Byte |
Status | AC |
Exec Time | 657 ms |
Memory | 1920 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 100 / 100 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | 00_sample1.txt, 00_sample2.txt, 01_rnd_large_00.txt, 01_rnd_large_01.txt, 01_rnd_large_02.txt, 01_rnd_small_00.txt, 01_rnd_small_01.txt, 01_rnd_small_02.txt, 02_narrowrnd_large_00.txt, 02_narrowrnd_large_01.txt, 02_narrowrnd_small_00.txt, 02_narrowrnd_small_01.txt, 03_zigzag_large_00.txt, 03_zigzag_small_00.txt, 04_middle_large_00.txt, 04_middle_large_01.txt, 04_middle_large_02.txt, 04_middle_small_00.txt, 04_middle_small_01.txt, 04_middle_small_02.txt, 05_turnleft_large_00.txt, 05_turnleft_small_00.txt, 06_turnright_large_00.txt, 06_turnright_small_00.txt, 07_free_large_00.txt, 07_free_small_00.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample1.txt | AC | 1 ms | 256 KB |
00_sample2.txt | AC | 1 ms | 256 KB |
01_rnd_large_00.txt | AC | 130 ms | 1792 KB |
01_rnd_large_01.txt | AC | 129 ms | 1792 KB |
01_rnd_large_02.txt | AC | 128 ms | 1792 KB |
01_rnd_small_00.txt | AC | 2 ms | 256 KB |
01_rnd_small_01.txt | AC | 2 ms | 256 KB |
01_rnd_small_02.txt | AC | 2 ms | 256 KB |
02_narrowrnd_large_00.txt | AC | 128 ms | 1792 KB |
02_narrowrnd_large_01.txt | AC | 128 ms | 1792 KB |
02_narrowrnd_small_00.txt | AC | 2 ms | 256 KB |
02_narrowrnd_small_01.txt | AC | 2 ms | 256 KB |
03_zigzag_large_00.txt | AC | 103 ms | 1792 KB |
03_zigzag_small_00.txt | AC | 2 ms | 256 KB |
04_middle_large_00.txt | AC | 129 ms | 1792 KB |
04_middle_large_01.txt | AC | 131 ms | 1920 KB |
04_middle_large_02.txt | AC | 129 ms | 1792 KB |
04_middle_small_00.txt | AC | 2 ms | 256 KB |
04_middle_small_01.txt | AC | 2 ms | 256 KB |
04_middle_small_02.txt | AC | 2 ms | 256 KB |
05_turnleft_large_00.txt | AC | 129 ms | 1792 KB |
05_turnleft_small_00.txt | AC | 2 ms | 256 KB |
06_turnright_large_00.txt | AC | 657 ms | 1920 KB |
06_turnright_small_00.txt | AC | 2 ms | 256 KB |
07_free_large_00.txt | AC | 104 ms | 1792 KB |
07_free_small_00.txt | AC | 2 ms | 256 KB |