QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#25459#2431. Getting a Jump on CrimeJohnAlfnovAC ✓297ms4608kbC++204.0kb2022-04-03 18:56:282022-04-29 01:29:56

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-29 01:29:56]
  • 评测
  • 测评结果:AC
  • 用时:297ms
  • 内存:4608kb
  • [2022-04-03 18:56:28]
  • 提交

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