QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#151159 | #6124. King Of Zombies | Sommohito# | TL | 1765ms | 9016kb | C++20 | 2.7kb | 2023-08-26 15:38:45 | 2023-08-26 15:38:47 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#ifdef APURBA
#include "DEBUG_TEMPLATE.h"
#else
#define HERE
#define debug(args...)
#endif
#define ALL(x) x.begin(),x.end()
const int N=1e3+5;
int n,D;
int x[N],y[N],vx[N],vy[N];
bool done[N];
pair<ld,ld> getpos(int who, ld tm)
{
ld X=x[who]+vx[who]*tm;
ld Y=y[who]+vy[who]*tm;
return make_pair(X,Y);
}
ld getdist(pair<ld,ld> A, pair<ld,ld> B)
{
A.first-=B.first;
A.second-=B.second;
return sqrtl(A.first*A.first+A.second*A.second);
}
ld get(int a,int b,ld after)
{
ld low=after,high=1e18;
ld ans=1e18;
int cnt=200;
while(cnt--)
{
if(low+1e-18>=high) break;
ld mid1=low+(high-low)/3,mid2=high-(high-low)/3;
pair<ld,ld> posa=getpos(a,mid1);
pair<ld,ld> posb=getpos(b,mid1);
ld dist1=getdist(posa,posb);
posa=getpos(a,mid2);
posb=getpos(b,mid2);
ld dist2=getdist(posa,posb);
// debug(dist1,dist2,mid1,mid2);
ans=min({ans,dist1,dist2});
if(dist1<dist2)
{
high=mid2;
}
else
{
low=mid1;
}
}
// debug(ans,low,high);
low=after;
ans=1e18;
cnt=500;
while(cnt--)
{
if(low+1e-18>=high) break;
ld mid=(low+high)/2;
pair<ld,ld> posa=getpos(a,mid);
pair<ld,ld> posb=getpos(b,mid);
ld dist=getdist(posa,posb);
if(dist<=D)
{
ans=mid;
high=mid;
}
else
low=mid;
}
// debug(a,b,after,ans);
return ans;
}
ld ans[N];
void TEST_CASES()
{
cin>>n>>D;
for(int i=0;i<=n;i++)
cin>>x[i]>>y[i]>>vx[i]>>vy[i];
priority_queue<pair<ld,int>>pq;
pq.push({0.,0});
for(int i=1;i<=n;i++)
ans[i]=1e18;
while(!pq.empty())
{
int z=pq.top().second;
ld tm=-pq.top().first;
pq.pop();
if(done[z])
continue;
done[z]=true;
ans[z]=tm;
for(int i=0;i<=n;i++)
{
if(done[i]) continue;
ld when=get(z,i,tm);
if(when==1e18) continue;
pq.push({-when,i});
}
}
for(int i=1;i<=n;i++)
{
if(ans[i]==1e18) cout<<"-1\n";
else
cout<<fixed<<setprecision(13)<<ans[i]<<"\n";
}
}
/*
*/
int32_t main()
{
#ifndef APURBA
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#endif
//freopen("input.txt","r",stdin);
//freopen("out1.txt","w",stdout);
int t=1;
//cin>>t;
while(t--)
{
TEST_CASES();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3784kb
input:
5 3 0 0 3 0 10 10 0 -3 1 1 -1 -1 16 1 -1 0 100 100 100 100 -100 -3 10 0
output:
2.6262265521468 0.0000000000000 3.0000000000000 -1 14.2857142856202
result:
ok 5 numbers
Test #2:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
4 10 0 0 0 0 10 0 0 0 20 0 0 0 30 0 0 0 41 0 0 0
output:
0.0000000000000 0.0000000000000 0.0000000000000 -1
result:
ok 4 numbers
Test #3:
score: 0
Accepted
time: 1487ms
memory: 7832kb
input:
814 5261 8674 -10000 83 9959 -3135 4963 -5450 -980 -6718 -5021 -5412 1206 8906 -9471 -4357 5471 -3795 2180 -4645 -2664 9110 -5528 9221 -3130 -3916 1465 -6825 5446 1767 -3479 -6871 -7960 -3523 5303 -1141 7806 3362 -3357 7529 -6106 -7323 -8776 3458 3288 -4825 -5940 -4857 95 -3169 6767 -3056 -2340 3228...
output:
0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000...
result:
ok 814 numbers
Test #4:
score: 0
Accepted
time: 120ms
memory: 3796kb
input:
470 235 5883 -1751 1075 368 7790 2418 3758 -3846 -5164 -3433 -5837 -7492 -3987 -6763 6899 -9252 -7032 2446 -4829 6204 5952 -1391 -6466 -1366 1902 -976 -6563 3105 -726 2931 4726 5388 5891 -2901 -3071 906 1237 6576 -2018 1582 -4444 -974 -537 -7998 -5090 -3067 -6005 -6746 7139 -9713 -6108 5218 150 -569...
output:
-1 -1 -1 -1 -1 -1 -1 3.8776035415730 -1 -1 -1 -1 -1 1.8672340235670 9.4843862519506 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0.4692992262039 1.2760146654733 -1 -1 -1 -1 0.8519144711473 0.8400612857954 -1 -1 -1 2.0495981783141 -1 -1 -1 16.6338579748008 1.1308375470119 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -...
result:
ok 470 numbers
Test #5:
score: 0
Accepted
time: 594ms
memory: 5288kb
input:
513 6743 672 -7437 -673 -4800 2473 7996 -6326 3500 5785 -4490 8411 9527 -6418 -4031 -7778 -7792 9650 -8109 -6418 4041 -6638 9373 7042 1792 -2582 601 2410 8495 7222 1876 -8251 1827 -6668 3503 4439 -2064 1004 6600 4235 -5489 -995 77 4672 7871 -2757 -6231 3455 2819 -1903 -7115 -7370 -9396 -9766 -581 -7...
output:
0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000...
result:
ok 513 numbers
Test #6:
score: 0
Accepted
time: 622ms
memory: 3852kb
input:
532 1356 592 8158 1209 4121 8684 -404 6292 -1509 -5665 9852 -8564 -4450 -225 -791 -3099 -5575 -3121 8560 5045 6229 -5053 3552 -871 1805 3034 3522 -1398 7523 -6851 -6621 -5539 5163 561 4300 -7900 -6939 64 -7900 4459 -3273 -4009 -5022 -9559 2288 1829 -7181 -4184 3853 5126 4300 2628 1409 5769 -2768 548...
output:
0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000...
result:
ok 532 numbers
Test #7:
score: 0
Accepted
time: 632ms
memory: 3852kb
input:
643 343 -6247 451 4007 656 3579 -2469 720 -1888 -2485 4858 -9720 3473 -8864 9702 -2158 5692 -9764 6779 5532 9028 9723 -3172 7666 -3027 -4979 1933 2796 -3016 -6078 -4470 -211 4094 -5796 -7180 -8344 -4196 -1820 1461 8832 -3253 -848 3229 -678 5283 -5949 3456 3712 -4297 9845 7690 9994 -6191 -4871 -2949 ...
output:
1.6834008052057 -1 -1 -1 -1 0.7878161749030 0.5525516670074 -1 -1 -1 0.3979023561664 -1 2.4381826347146 1.4890329428490 7.6708666801126 3.0161985433470 -1 -1 -1 7.5952025662373 -1 3.4768956437681 -1 1.1149233424483 1.2285466413418 -1 0.7457215031538 -1 -1 -1 -1 -1 4.0849610680290 1.3055001709401 -1 ...
result:
ok 643 numbers
Test #8:
score: 0
Accepted
time: 934ms
memory: 4224kb
input:
649 3052 1634 -9666 -5898 2948 -3830 8114 -1787 -3584 -4100 -5438 8239 -9293 9908 -3521 -633 -3613 -7653 -5639 -7483 6603 1242 2634 2971 598 9456 6152 -1814 6843 -4929 8914 1158 5029 -3091 4248 140 -895 9284 -6769 -9699 -9594 -2824 6832 4073 -8505 4594 3404 -1270 -5966 9563 -1447 -4108 4073 -3025 -2...
output:
0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000...
result:
ok 649 numbers
Test #9:
score: 0
Accepted
time: 1696ms
memory: 7476kb
input:
870 5514 -1985 -9924 -5613 -9347 3241 -128 -5784 33 -4825 -572 -1340 2283 4080 -3302 5218 4158 -1317 -3620 7471 1536 -1154 6167 3855 8688 -3304 -1866 4963 3167 -8053 3553 3507 7352 5065 3337 319 -5145 7448 -8719 9929 7044 -6110 -612 7888 882 -3818 3492 7954 -6249 -3942 -5128 -8938 5992 3112 -122 79 ...
output:
0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000...
result:
ok 870 numbers
Test #10:
score: 0
Accepted
time: 1765ms
memory: 8888kb
input:
886 5788 4869 805 -1826 8306 2185 3157 -4632 7777 5595 -5345 6978 -9690 2367 3972 -9402 726 5510 -8129 -1422 -4013 4131 7664 -8198 -2791 9043 -2491 8462 -1914 -6524 4703 4495 -8856 5351 -7212 2052 -3286 -2623 6477 8934 -1888 9084 1877 -625 -9152 7860 -5086 -4514 7105 -4796 -7466 -8809 -52 7692 6702 ...
output:
0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000...
result:
ok 886 numbers
Test #11:
score: 0
Accepted
time: 222ms
memory: 3752kb
input:
314 5962 2258 -8497 -2386 5236 -428 6368 5126 9422 -3688 -8063 -4141 -4815 -853 199 -2565 -3687 534 -5684 2036 -1824 7442 -4207 8410 4896 2641 3361 -8534 9797 -9026 7734 -6819 7914 460 3684 6187 6603 7444 -4285 -3281 1650 7287 -1985 2698 3794 -6447 2709 9001 3869 -6024 2374 8468 -2719 -6641 6761 763...
output:
0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000...
result:
ok 314 numbers
Test #12:
score: 0
Accepted
time: 1514ms
memory: 9016kb
input:
821 5983 -8357 -5982 567 -3431 27 3101 -1648 1733 -3386 2420 -9294 -3877 -8981 -7706 -1073 5824 -6539 -53 3538 -5322 -9740 6341 9302 -4074 7003 8101 7115 7103 -2801 1876 5693 -6039 6032 -9161 693 -2299 8895 -3560 -7514 1319 -8687 -4261 -906 7503 -9920 -3828 1091 4014 -4722 -723 3200 5898 -917 7491 -...
output:
0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000000 0.0000000000...
result:
ok 821 numbers
Test #13:
score: -100
Time Limit Exceeded
input:
1000 4747 4970 8674 -10000 83 9959 -3135 4963 -5450 -980 -6718 -5021 -5412 1206 8906 -9471 -4357 5471 -3795 2180 -4645 -2664 9110 -5528 9221 -3130 -3916 1465 -6825 5446 1767 -3479 -6871 -7960 -3523 5303 -1141 7806 3362 -3357 7529 -6106 -7323 -8776 3458 3288 -4825 -5940 -4857 95 -3169 6767 -3056 -234...