QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#67597#5170. 加速度skicean0 0ms0kbC++142.1kb2022-12-10 19:44:372022-12-10 19:44:38

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-10 19:44:38]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2022-12-10 19:44:37]
  • 提交

answer

#include <cstdio>
#include <iostream>
#include <cmath>
#define macro_expand(x) #x
#define print_macro(x) printf("%s\n",macro_expand(x))
#define FOR(i,l,r) for(int i=(l),i##ADJK=(r);i<=i##ADJK;++i)
#define ROF(i,r,l) for(int i=(r),i##ADJK=(l);i>=i##ADJK;--i)
using namespace std;
typedef long long LL;
typedef long double LD;
const int MN=5e3+5;
const LD eps=1e-9;
int N;
LD s[MN],l[MN],r[MN],a;
LD f[MN];
LD pf(LD x){return x*x;}
LD jfc(LD a,LD b,LD c){return (-b+sqrt(b*b-4.0*a*c))/2.0/a;}
int main(){
	freopen("b.in","r",stdin);
	freopen("b.out","w",stdout);
	scanf("%d%Lf",&N,&a);
	FOR(i,1,N+1)scanf("%Lf",&s[i]);
	FOR(i,1,N+1)scanf("%Lf %Lf",&l[i],&r[i]);
	FOR(i,2,N+1)l[i]=max(l[i-1],l[i]);
	ROF(i,N,1)r[i]=min(r[i+1],r[i]);
	FOR(i,1,N+1){
		if(l[i]>r[i]){
			printf("kaibai\n");
			return 0;
		}
	}
	r[1]=0;
	LD ans=1e18;
	FOR(i,1,N){
		LD nl=0,nr=f[i];
		FOR(j,i+1,N+1){
			if(j==N+1){
				LD t=jfc(0.5*a,nr,-s[N+1]+s[i]);
				if(r[i]+t>r[N+1])continue;
				ans=min(ans,max(l[N+1],r[i]+t));
			}else{
				LD vl=(l[j]>r[i]+eps)?((s[j]-s[i])/(r[j]-r[i])-0.5*a*(r[j]-r[i])):0,
				   vr=(l[j]>r[i]+eps)?((s[j]-s[i])/(l[j]-r[i])-0.5*a*(l[j]-r[i])):1e18;
				// if(i==4&&j==5){
				// 	cerr<<"vl:"<<vl<<" vr:"<<vr<<endl;
				// 	cerr<<"nl:"<<nl<<" nr:"<<nr<<endl;
				// }
				nl=max(nl,vl),nr=min(nr,vr);
				if(nl-nr>eps)break;
				if(fabs(s[i]+0.5*a*pf(r[j]-r[i])+nl*(r[j]-r[i])-s[j])<=eps)
					f[j]=max(f[j],nl+a*(r[j]-r[i]));
			}
		}
		LD ntl=0,ntr=1e18;
		FOR(j,i+1,N+1){
			if(j==N+1){
				LD nw=sqrt(2.0*(s[N+1]-s[i])/a);
				LD fu=r[i]+ntl+nw;
				// cerr<<"j:"<<j<<" fu:"<<fu<<endl;
				if(fu>r[N+1])continue;
				ans=min(ans,max(l[N+1],fu));
			}else{
				LD tl=l[j]-r[i]-sqrt(2*(s[j]-s[i])/a),
				   tr=r[j]-r[i]-sqrt(2*(s[j]-s[i])/a);
				ntl=max(ntl,tl),ntr=min(ntr,tr);
				if(ntl-ntr>eps)break;
				LD x=r[j]-r[i]-tr;
				if(fabs(s[i]+0.5*a*pf(x)-s[j])<=eps)
					f[j]=max(f[j],a*x);
			}
		}
	}
	// FOR(i,1,N)cerr<<f[i]<<" ";
	// cerr<<endl;
	if(ans>=1e18-1)printf("kaibai\n");
	else printf("%.10Lf\n",ans);
	fclose(stdin);
	fclose(stdout);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Dangerous Syscalls

Test #1:

score: 0
Dangerous Syscalls

input:

4 2
0 2 8 10 12
0 1000000000
2 2
4 4
6 7
6 1000000000


output:


result:


Subtask #2:

score: 0
Dangerous Syscalls

Test #7:

score: 0
Dangerous Syscalls

input:

3 20
0 4632 5697 8786
0 1000000000
1 1000000000
1 1000000000
1 1000000000

output:


result:


Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%