QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#728463 | #5978. Runaway Quail | Jessica2333 | 0 | 129ms | 6292kb | C++14 | 1.9kb | 2024-11-09 15:13:59 | 2024-11-09 15:13:59 |
Judging History
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)