QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#752898 | #3566. Cycling | gyydp123_LIM | 100 ✓ | 344ms | 3996kb | C++20 | 2.3kb | 2024-11-16 10:21:47 | 2024-11-16 10:21:48 |
Judging History
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*m);
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[x].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: 100
Accepted
time: 344ms
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 416.321 126.328 376....
result:
ok 120 lines