QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#752878#3566. Cyclinggyydp123_LIM0 257ms3996kbC++202.3kb2024-11-16 10:14:542024-11-16 10:14:55

Judging History

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

  • [2024-11-16 10:14:55]
  • 评测
  • 测评结果:0
  • 用时:257ms
  • 内存:3996kb
  • [2024-11-16 10:14:54]
  • 提交

answer

//Start: 2024-11-16 09:22:38
#include<bits/stdc++.h>
#define For(i,j,k) for(int i=(j);i<=(k);++i)
#define ForDown(i,j,k) for(int i=(j);i>=(k);--i)
#define Debug(fmt, args...) fprintf(stderr,"(func %s, line #%d): " fmt, __func__, __LINE__, ##args),fflush(stderr)
#define debug(fmt, args...) fprintf(stderr,fmt,##args),fflush(stderr)
#define within :
#define LJY main
using namespace std;
typedef long long ll;
const int N=605;
const double inf=1e18,A=0.5,eps=1e-8;
mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
inline int read(){
  char ch=getchar();int x=0,f=1;
  while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
  while(ch>='0'&&ch<='9')
    x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
  return x*f;
}
double X;int m;
struct Light{double x,r,g;}a[N];
double f[11][N];
double solve(double A,double B,double C){
  return (-B+sqrt(B*B-4*A*C))/(2*A);}
void ljy(){
  For(i,1,m) scanf("%lf%lf%lf",&a[i].x,&a[i].r,&a[i].g);
  sort(a+1,a+1+m,[](Light a,Light b){return a.x<b.x;});
  double all=sqrt(X*4);
  For(i,1,m) all+=a[i].r;
  int Lim=all/10;
  For(j,0,10) For(i,0,Lim) f[j][i]=-inf;f[0][0]=0;
  For(i,1,m) For(j,1,Lim) For(x,0,i-1) For(y,0,Lim) if(f[x][y]>=-eps){
    double x2=a[i].x,t2=j/2*(a[i].r+a[i].g)+(j&1)*a[i].r;
    double x1=a[x].x,t1=y/2*(a[x].r+a[x].g)+(y&1)*a[i].r,lim=f[x][y];
    double dt=t2-t1,dx=x2-x1;
    if(dt<0) continue;
    double v0=(dx-dt*dt/2*A)/dt;
    if(v0>lim) continue;
    if(v0<0) t1=t2-sqrt(dx*2/A),v0=0;
    bool flg=1;
    For(k,x+1,i-1){
      double dx=a[k].x-a[x].x;
      double nt=t1+solve(A/2,v0,-dx);
      double rst=nt-(int)(nt/(a[k].g+a[k].r))*(a[k].g+a[k].r);
      while(rst>=(a[k].g+a[k].r)-eps) rst-=((a[k].g+a[k].r));
      if(rst<a[k].r-eps){flg=0;break;}
    }if(flg) f[i][j]=max(f[i][j],sqrt(2*A*dx+v0*v0));
  }double ans=inf;
  For(i,0,m) For(j,0,Lim) if(f[i][j]>=-eps){
    double dx=a[i].x,v0=f[i][j],t1=j/2*(a[i].g+a[i].r)+(j&1)*a[i].r;bool flg=1;
    For(k,i+1,m){
      double dx=a[k].x-a[i].x;
      double nt=t1+solve(A/2,v0,-dx);
      double rst=nt-(int)(nt/(a[k].g+a[k].r))*(a[k].g+a[k].r);
      if(rst<a[k].r-eps){flg=0;break;}
    }if(flg) ans=min(ans,t1+solve(A/2,v0,-(X-a[i].x)));
  }printf("%.3lf\n",ans);
}
signed LJY(){while(scanf("%lf%d",&X,&m)==2) ljy();}

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

score: 0
Wrong Answer
time: 257ms
memory: 3996kb

input:

410.0 2
200.0 15.0 15.0
225.0 31.0 10.0
410.0 2
200.0 15.0 15.0
225.0 35.1 15.0
410.0 2
200.0 15.0 15.0
225.0 45.0 10.0
123.4 0
1234.5 0
1001.0 1
100.0 19.652502 10.581152
1002.0 1
800.0 20.98416 10.923976
1003.0 1
100.0 25.0 15.0
1005.0 1
500.0 60.0 15.0
1000.0 1
500.0 22.0 22.0
1103.0 10
101.234 1...

output:

41.497
52.623
57.213
22.217
70.271
63.277
63.309
68.340
78.682
84.524
66.423
428.492
315.578
162.419
91.789
97.892
99.779
148.498
2.000
1685.830
247.603
199.900
178.054
171.842
188.940
133.646
540.973
171.454
119.701
77.388
340.182
333.960
159.142
189.920
159.708
167.986
432.211
94.161
126.328
376.1...

result:

wrong answer 38th lines differ - expected: '416.321', found: '94.161'