QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#25459 | #2431. Getting a Jump on Crime | JohnAlfnov | AC ✓ | 297ms | 4608kb | C++20 | 4.0kb | 2022-04-03 18:56:28 | 2022-04-29 01:29:56 |
Judging History
answer
#include<bits/stdc++.h>
#define mk(i,j) (((i)-1)*m+(j))
#define double long double
using namespace std;
const double g=9.80665;
const double na=log(-1);
int he[25][25];
int f[405][405];
int n,m,w,v,x,y;
pair<double,double>calc(double d,double t){
double ll=1,rr=0;
if(t<0){
ll=sqrt(-g*d*d/2/t),rr=v;
}
double A=t*t+d*d,B=g*d*d*t-(double)1*v*v*d*d,C=g*g*d*d*d*d/4;
double del=B*B-4*A*C;
if(del<0)return make_pair(ll,rr);
del=sqrt(del);
double L=(-B-del)/A/2,R=(-B+del)/A/2;
if(L>R)swap(L,R);
L=max(L,(double)0),R=min(R,(double)1*v*v);
L=sqrt(L),R=sqrt(R);
if(!(R<ll||rr<L))L=min(L,ll),R=max(R,rr);
return make_pair(L,R);
}
pair<double,double>clac(double d,double t){
double A=t*t+d*d,B=g*d*d*t-(double)1*v*v*d*d,C=g*g*d*d*d*d/4;
double del=B*B-4*A*C;
if(del<0)return make_pair(na,na);
del=sqrt(del);
double L=(-B-del)/A/2,R=(-B+del)/A/2;
if(L>R)swap(L,R);
L=sqrt(L),R=sqrt(R);
double c1=sqrt(v*v-L*L)*d/L-g*d*d/2/L/L-t;
if(!(c1<0||c1==0||c1>0)||fabs(c1)>1e-5)L=na;
double c2=sqrt(v*v-R*R)*d/R-g*d*d/2/R/R-t;
if(!(c2<0||c2==0||c2>0)||fabs(c2)>1e-5)R=na;
return make_pair(L,R);
}
int main(){
cin>>n>>m>>w>>v>>x>>y;
for(int j=1;j<=m;++j)for(int i=1;i<=n;++i)
scanf("%d",&he[i][j]);
int N=n*m;
memset(f,63,sizeof(f));
for(int i=1;i<=N;++i)f[i][i]=0;
for(int Ax=1;Ax<=n;++Ax)for(int Ay=1;Ay<=m;++Ay)
for(int Bx=1;Bx<=n;++Bx)for(int By=1;By<=m;++By){
double ax=(Ax-0.5)*w,ay=(Ay-0.5)*w;
double bx=(Bx-0.5)*w,by=(By-0.5)*w;
double l=-1e18,r=1e18;
for(int i=0;i<=n;++i){
double cx=(double)i*w;
if(cx<min(ax,bx)||cx>max(ax,bx))continue;
if(cx==ax||cx==bx)assert(0);
double cy=(cx-ax)/(bx-ax)*by+(bx-cx)/(bx-ax)*ay;
if(cy<0||cy>(double)m*w)continue;
double dis=sqrt((ax-cx)*(ax-cx)+(ay-cy)*(ay-cy));
int Cy=(cy+1e-7)/w+1,ff=0;
if(fabs(cy-round(cy/w)*w)<1e-7)ff=1;
if(i>0&&Cy>0){
auto at=calc(dis,he[i][Cy]-he[Ax][Ay]);
l=max(l,at.first);
r=min(r,at.second);
if(l>r)break;
}
if(i<n&&Cy>0){
auto at=calc(dis,he[i+1][Cy]-he[Ax][Ay]);
l=max(l,at.first);
r=min(r,at.second);
if(l>r)break;
}
if(i>0&&Cy>1&&ff==1){
auto at=calc(dis,he[i][Cy-1]-he[Ax][Ay]);
l=max(l,at.first);
r=min(r,at.second);
if(l>r)break;
}
if(i<n&&Cy>1&&ff==1){
auto at=calc(dis,he[i+1][Cy-1]-he[Ax][Ay]);
l=max(l,at.first);
r=min(r,at.second);
if(l>r)break;
}
}
if(l>r)continue;
for(int i=0;i<=m;++i){
double cy=(double)i*w;
if(cy<min(ay,by)||cy>max(ay,by))continue;
if(cy==ay||cy==by)assert(0);
double cx=(cy-ay)/(by-ay)*bx+(by-cy)/(by-ay)*ax;
if(cx<0||cx>(double)n*w)continue;
double dis=sqrt((ax-cx)*(ax-cx)+(ay-cy)*(ay-cy));
int Cx=(cx+1e-7)/w+1,ff=0;
if(fabs(cx-round(cx/w)*w)<1e-7)ff=1;
if(i>0&&Cx>0){
auto at=calc(dis,he[Cx][i]-he[Ax][Ay]);
l=max(l,at.first);
r=min(r,at.second);
if(l>r)break;
}
if(i<m&&Cx>0){
auto at=calc(dis,he[Cx][i+1]-he[Ax][Ay]);
l=max(l,at.first);
r=min(r,at.second);
if(l>r)break;
}
if(i>0&&Cx>1&&ff==1){
auto at=calc(dis,he[Cx-1][i]-he[Ax][Ay]);
l=max(l,at.first);
r=min(r,at.second);
if(l>r)break;
}
if(i<m&&Cx>1&&ff==1){
auto at=calc(dis,he[Cx-1][i+1]-he[Ax][Ay]);
l=max(l,at.first);
r=min(r,at.second);
if(l>r)break;
}
}
if(l>r)continue;
double dd=sqrt((ax-bx)*(ax-bx)+(ay-by)*(ay-by));
auto tt=clac(dd,he[Bx][By]-he[Ax][Ay]);
if((tt.first>=l-1e-4&&tt.first<=r+1e-4)||(tt.second>=l-1e-4&&tt.second<=r+1e-4)){
int A=mk(Ax,Ay),B=mk(Bx,By);
f[A][B]=min(f[A][B],1);
}
}
for(int k=1;k<=N;++k)for(int i=1;i<=N;++i)
for(int j=1;j<=N;++j){
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
}
int km=mk(x,y);
for(int i=1;i<=m;++i){
for(int j=1;j<=n;++j){
int wz=mk(j,i);
if(f[km][wz]>1e9)printf("X ");
else printf("%d ",f[km][wz]);
}
putchar('\n');
}
return 0;
}
Details
Test #1:
score: 100
Accepted
time: 1ms
memory: 4444kb
Test #2:
score: 0
Accepted
time: 3ms
memory: 4492kb
Test #3:
score: 0
Accepted
time: 295ms
memory: 4488kb
Test #4:
score: 0
Accepted
time: 0ms
memory: 4396kb
Test #5:
score: 0
Accepted
time: 3ms
memory: 4552kb
Test #6:
score: 0
Accepted
time: 3ms
memory: 4396kb
Test #7:
score: 0
Accepted
time: 297ms
memory: 4464kb
Test #8:
score: 0
Accepted
time: 4ms
memory: 4508kb
Test #9:
score: 0
Accepted
time: 2ms
memory: 4496kb
Test #10:
score: 0
Accepted
time: 3ms
memory: 4492kb
Test #11:
score: 0
Accepted
time: 53ms
memory: 4340kb
Test #12:
score: 0
Accepted
time: 3ms
memory: 4472kb
Test #13:
score: 0
Accepted
time: 0ms
memory: 4396kb
Test #14:
score: 0
Accepted
time: 2ms
memory: 4508kb
Test #15:
score: 0
Accepted
time: 55ms
memory: 4468kb
Test #16:
score: 0
Accepted
time: 4ms
memory: 4504kb
Test #17:
score: 0
Accepted
time: 3ms
memory: 4488kb
Test #18:
score: 0
Accepted
time: 0ms
memory: 4460kb
Test #19:
score: 0
Accepted
time: 3ms
memory: 4496kb
Test #20:
score: 0
Accepted
time: 3ms
memory: 4464kb
Test #21:
score: 0
Accepted
time: 3ms
memory: 4468kb
Test #22:
score: 0
Accepted
time: 3ms
memory: 4536kb
Test #23:
score: 0
Accepted
time: 0ms
memory: 4492kb
Test #24:
score: 0
Accepted
time: 2ms
memory: 4472kb
Test #25:
score: 0
Accepted
time: 1ms
memory: 4548kb
Test #26:
score: 0
Accepted
time: 1ms
memory: 4392kb
Test #27:
score: 0
Accepted
time: 1ms
memory: 4396kb
Test #28:
score: 0
Accepted
time: 3ms
memory: 4552kb
Test #29:
score: 0
Accepted
time: 4ms
memory: 4440kb
Test #30:
score: 0
Accepted
time: 5ms
memory: 4392kb
Test #31:
score: 0
Accepted
time: 3ms
memory: 4336kb
Test #32:
score: 0
Accepted
time: 61ms
memory: 4464kb
Test #33:
score: 0
Accepted
time: 61ms
memory: 4396kb
Test #34:
score: 0
Accepted
time: 56ms
memory: 4392kb
Test #35:
score: 0
Accepted
time: 137ms
memory: 4608kb
Test #36:
score: 0
Accepted
time: 3ms
memory: 4496kb
Test #37:
score: 0
Accepted
time: 3ms
memory: 4532kb
Test #38:
score: 0
Accepted
time: 0ms
memory: 4552kb
Test #39:
score: 0
Accepted
time: 3ms
memory: 4536kb
Test #40:
score: 0
Accepted
time: 0ms
memory: 4336kb
Test #41:
score: 0
Accepted
time: 3ms
memory: 4440kb
Test #42:
score: 0
Accepted
time: 3ms
memory: 4492kb
Test #43:
score: 0
Accepted
time: 0ms
memory: 4468kb
Test #44:
score: 0
Accepted
time: 3ms
memory: 4548kb
Test #45:
score: 0
Accepted
time: 3ms
memory: 4452kb
Test #46:
score: 0
Accepted
time: 3ms
memory: 4340kb
Test #47:
score: 0
Accepted
time: 2ms
memory: 4496kb
Test #48:
score: 0
Accepted
time: 1ms
memory: 4496kb
Test #49:
score: 0
Accepted
time: 2ms
memory: 4604kb
Test #50:
score: 0
Accepted
time: 3ms
memory: 4396kb
Test #51:
score: 0
Accepted
time: 3ms
memory: 4452kb
Test #52:
score: 0
Accepted
time: 3ms
memory: 4464kb
Test #53:
score: 0
Accepted
time: 287ms
memory: 4488kb
Test #54:
score: 0
Accepted
time: 58ms
memory: 4544kb
Test #55:
score: 0
Accepted
time: 88ms
memory: 4340kb
Test #56:
score: 0
Accepted
time: 59ms
memory: 4468kb
Test #57:
score: 0
Accepted
time: 60ms
memory: 4468kb
Test #58:
score: 0
Accepted
time: 69ms
memory: 4552kb
Test #59:
score: 0
Accepted
time: 87ms
memory: 4536kb
Test #60:
score: 0
Accepted
time: 58ms
memory: 4464kb
Test #61:
score: 0
Accepted
time: 60ms
memory: 4604kb
Test #62:
score: 0
Accepted
time: 286ms
memory: 4464kb
Test #63:
score: 0
Accepted
time: 37ms
memory: 4472kb
Test #64:
score: 0
Accepted
time: 41ms
memory: 4396kb
Test #65:
score: 0
Accepted
time: 42ms
memory: 4504kb
Test #66:
score: 0
Accepted
time: 41ms
memory: 4452kb
Test #67:
score: 0
Accepted
time: 44ms
memory: 4492kb
Test #68:
score: 0
Accepted
time: 52ms
memory: 4388kb
Test #69:
score: 0
Accepted
time: 46ms
memory: 4396kb
Test #70:
score: 0
Accepted
time: 45ms
memory: 4452kb
Test #71:
score: 0
Accepted
time: 61ms
memory: 4340kb
Test #72:
score: 0
Accepted
time: 32ms
memory: 4448kb
Test #73:
score: 0
Accepted
time: 42ms
memory: 4468kb
Test #74:
score: 0
Accepted
time: 44ms
memory: 4496kb
Test #75:
score: 0
Accepted
time: 63ms
memory: 4444kb
Test #76:
score: 0
Accepted
time: 44ms
memory: 4448kb
Test #77:
score: 0
Accepted
time: 53ms
memory: 4396kb
Test #78:
score: 0
Accepted
time: 42ms
memory: 4468kb
Test #79:
score: 0
Accepted
time: 55ms
memory: 4532kb
Test #80:
score: 0
Accepted
time: 61ms
memory: 4392kb