QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#151193 | #6124. King Of Zombies | Sommohito# | WA | 1041ms | 5264kb | C++20 | 2.8kb | 2023-08-26 15:50:45 | 2023-08-26 15:50:48 |
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=1e6;
ld ans=1e6;
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);
// if(ans-1e-18>D)
// return 1e6;
low=after;
ans=1e6;
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);
// debug(dist);
if(dist<=D+1e-18)
{
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]=1e6;
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==1e6) continue;
pq.push({-when,i});
}
}
for(int i=1;i<=n;i++)
{
if(ans[i]==1e6) cout<<"-1\n";
else
cout<<fixed<<setprecision(15)<<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: 1ms
memory: 3848kb
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.626226552146786 0.000000000000000 3.000000000000000 -1 14.285714285620208
result:
ok 5 numbers
Test #2:
score: 0
Accepted
time: 1ms
memory: 3900kb
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.000000000000000 0.000000000000000 0.000000000000000 -1
result:
ok 4 numbers
Test #3:
score: 0
Accepted
time: 1041ms
memory: 5264kb
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.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000 0.0000000000...
result:
ok 814 numbers
Test #4:
score: -100
Wrong Answer
time: 79ms
memory: 3848kb
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.877603541572985 -1 -1 -1 -1 -1 1.867234023566958 9.484386251950605 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0.469299226203908 1.276014665473257 -1 -1 -1 -1 0.851914471147283 0.840061285795425 -1 -1 -1 2.049598178314072 -1 -1 -1 16.633857974800816 1.130837547011939 -1 -1 -1 -1 -1 -1...
result:
wrong answer 199th numbers differ - expected: '0.7657190', found: '1.1056613', error = '0.3399423'