/ Randle /

记录详情

Time Exceeded

/in/foo.cc: In function 'int main()':
/in/foo.cc:37:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   if(p[i].t>p[back].t)back=i;if(p[i].t<p[front].t)front=i;
   ^~
/in/foo.cc:37:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   if(p[i].t>p[back].t)back=i;if(p[i].t<p[front].t)front=i;
                              ^~
/in/foo.cc:38:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   if(p[i].v<p[slow].v)slow=i;if(p[i].v>p[fast].v)fast=i;
   ^~
/in/foo.cc:38:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   if(p[i].v<p[slow].v)slow=i;if(p[i].v>p[fast].v)fast=i;
                              ^~
/in/foo.cc:66:21: warning: use of 'll' length modifier with 'f' type character has either no effect or undefined behavior [-Wformat=]
  printf("%.2llf",ans);
                     ^
# 状态 耗时 内存占用
#1 Wrong Answer 3ms 312.0 KiB
#2 Time Exceeded ≥1007ms ≥308.0 KiB
#3 Wrong Answer 2ms 312.0 KiB
#4 Time Exceeded ≥1006ms ≥316.0 KiB
#5 Time Exceeded ≥1007ms ≥316.0 KiB
#6 Time Exceeded ≥1007ms ≥312.0 KiB
#7 Wrong Answer 4ms 440.0 KiB
#8 Time Exceeded ≥1007ms ≥300.0 KiB
#9 Time Exceeded ≥1007ms ≥1.801 MiB
#10 Time Exceeded ≥1005ms ≥1.82 MiB

代码

#include<bits/stdc++.h>
const int maxn=100001;
const double inf=100000000;
inline const void read(double&a)
{
	a=0;
	char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')
	{
		a=a*10+c-'0';
		c=getchar();
	}
}
struct puma
{
	double t,v;
}p[maxn];
int slow=0,fast=99999,back=0,front=99999;
double tt;
inline const double dis(int i,double t)
{
	return p[i].v*(t-p[i].t);
}
inline const double gettime(int a,int b)
{
	return (p[a].v*p[a].t-p[b].v*p[b].t)/(p[a].v-p[b].v);
}
int main()
{
	int n;
	std::cin>>n;
	p[back].t=0;p[front].t=inf;p[slow].v=inf;p[fast].v=0;
	for(int i=1;i<=n;i++)
	{
		read(p[i].t);read(p[i].v);
		if(p[i].t>p[back].t)back=i;if(p[i].t<p[front].t)front=i;
		if(p[i].v<p[slow].v)slow=i;if(p[i].v>p[fast].v)fast=i;
	}
	double ans=inf;
	tt=p[back].t;
	while(true)
	{
		if((fast==front)&&(slow==back))break;
		ans=std::min(ans,dis(front,tt)-dis(back,tt));
		double get=inf,take=inf;
		double over=back,caught=front,newtt;
		for(int i=1;i<=n;i++)
		{
			if(i!=back)
			{
				double t=gettime(back,i);
				if(t>tt&&p[i].v<p[back].v&&t<get){get=t;over=i;}
			}
			if(i!=front)
			{
				double t=gettime(front,i);
				if(t>tt&&p[i].v>p[front].v&&t<take){take=t;caught=i;}
			}
		}
		newtt=std::min(take,get);
		ans=std::min(ans,dis(front,newtt)-dis(back,newtt));
		if(get<take){back=over;tt=newtt;continue;}
		else{front=caught;tt=newtt;continue;}
	}
	printf("%.2llf",ans);
	return 0;
}

信息

递交者
类型
递交
题目
追逐 T3
题目数据
下载
语言
C++
递交时间
2017-10-04 13:41:30
评测时间
2017-10-04 13:41:30
评测机
分数
0
总耗时
≥7058ms
峰值内存
≥1.82 MiB