QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#728463#5978. Runaway QuailJessica23330 129ms6292kbC++141.9kb2024-11-09 15:13:592024-11-09 15:13:59

Judging History

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

  • [2024-11-09 15:13:59]
  • 评测
  • 测评结果:0
  • 用时:129ms
  • 内存:6292kb
  • [2024-11-09 15:13:59]
  • 提交

answer

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const long double INF=1e17;
int T;
int N;
long double S;
struct NODE{
	long double p,b;
	long double pos_(long double t)
	{
		return p+(p<0?-1:1)*t*b;
	}
}A[508],C[508],D[508],E[508];
struct NODE2{
	int id;long double p,b;
}B[508];
long double f[508][508][2];
bool mcp(NODE2 x,NODE2 y)
{
	return x.p<y.p;
}
bool check(long double mid)
{
	for(int i=1;i<=N;i++)
	{
		B[i]={i,A[i].p+(A[i].p<=0?-1:1)*mid*A[i].b,A[i].b};
	}
	sort(B+1,B+N+1,mcp);
	int zo=N+1,totC=0;
	long double spd=-1;
	for(int i=1;i<=N;i++)
	{
		if(B[i].p>0)
		{
			zo=i;
			break;
		}
		if(spd<B[i].b) C[++totC]=A[B[i].id],spd=B[i].b;
	}
	spd=-1;
	int totD=0;
	for(int i=N;i>=zo;i--)
	{
		if(spd<B[i].b) D[++totD]=A[B[i].id],spd=B[i].b;
	}
	int M=0;
	for(int i=1;i<=totC;i++) E[++M]=C[i];
	for(int i=totD;i>=1;i--) E[++M]=D[i];
	for(int i=1;i<=M;i++) f[i][i][0]=f[i][i][1]=abs(E[i].p)/(S-E[i].b);
	for(int len=1;len<M;len++)
	{
		for(int l=1,r=l+len;r<=M;l++,r++)
		{
			f[l][r][0]=INF;
			long double t;
			f[l][r][0]=min(f[l][r][0],(t=f[l+1][r][0])+(E[l+1].pos_(t)-E[l].pos_(t))/(S-E[l].b));
			f[l][r][0]=min(f[l][r][0],(t=f[l+1][r][1])+(E[r].pos_(t)-E[l].pos_(t))/(S-E[l].b));
			
			f[l][r][1]=INF;
			f[l][r][1]=min(f[l][r][1],(t=f[l][r-1][1])+(E[r].pos_(t)-E[r-1].pos_(t))/(S-E[r].b));
			f[l][r][1]=min(f[l][r][1],(t=f[l][r-1][0])+(E[r].pos_(t)-E[l].pos_(t))/(S-E[r].b));
		}
	}
	return min(f[1][M][0],f[1][M][1])<=mid;
}
/*
2
4 3
3 6 9
3 2 1
2 2
1 -1
1 1
*/
void solve()
{
	cin>>S>>N;
	for(int i=1;i<=N;i++) cin>>A[i].p;
	for(int i=1;i<=N;i++) cin>>A[i].b;
	long double l=0,r=1e17,mid;
	while(r-l>1e-8)
	{
		mid=(l+r)/2.0;
		if(check(mid)) r=mid;
		else l=mid;
	}
	printf("%.6Lf\n",l);
}
signed main()
{
	cin>>T;
	while(T--)
	{
		solve();
//		init_();
	}
	return 0;
}
/*
1
1 1
1
0

2
4 3
3 6 9
3 2 1

2 2
1 -1
1 1
*/

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3936kb

input:

50
4 3
-3 -6 -9
3 2 1
2 2
1 -1
1 1
1000 25
769234 -5735820 -524288 -5403090 -6429140 1574982 1 -9733628 -1407481 4093041 4117720 -3193501 -9765195 -3069520 1122216 -5799108 131072 -8482066 -256 -8021159 -8958386 -7027036 5370579 -3602534 -6834567
425 102 744 155 339 19 999 19 159 198 51 304 369 601 ...

output:

3.000000
5.000000
0.000000
429262.396142
10570.035264
0.000000
15883.220077
314783.769009
5725896.876344
10556.739623
19603.022613
610881.705160
0.000000
10543.477387
10517.052632
45104.948854
47122.029851
8467.351502
10530.248432
451714.419608
23828.120184
53432.441529
25897.744048
16853.825243
318...

result:

wrong output format Expected 'Case' but found '3.000000' (test case 1)

Subtask #2:

score: 0
Wrong Answer

Test #2:

score: 0
Wrong Answer
time: 129ms
memory: 6292kb

input:

50
4 3
-3 -6 -9
3 2 1
2 2
1 -1
1 1
1000 500
-9650379 9806301 -6495789 -1283284 5022779 4725553 9364178 -8123302 -9609729 7847458 -142364 6983908 8147008 -3186924 7339254 -8737645 8757174 7887319 3609962 5780915 -1752801 -1657946 -9511339 5113995 -7887160 -6093170 260267 -3837106 -356098 6676924 6210...

output:

3.000000
5.000000
35346561.200000
0.000000
0.000000
13741948.500000
0.000000
0.000000
10530.248432
3694019.600000
10530.248432
0.000000
10517.052632
0.000000
0.000000
10543.477387
0.000000
7792241110.000000
1986500.666667
255372.714286
19603.022613
10517.052632
0.000000
94888.625000
0.000000
0.00000...

result:

wrong output format Expected 'Case' but found '3.000000' (test case 1)