悬关求调
查看原帖
悬关求调
686281
sherry_lover楼主2024/10/30 20:48
#include<bits/stdc++.h>
using namespace std;
struct car{
	int d,v,a;
}a[100005];
int T,n,m,l,v,p[100005],ans,aans,Case;
long double V,eps = 1e-9;
bool vis[100005];
pair<int,int> b[100005];
bool f = 1,f1 = 1;
int G(long double x)
{
	if(p[m] < x) return m+2;
	int L = 0,R = m+2;
	while(L < R)
	{
		int mid = (L+R) >> 1;
//		if(p[mid]*1.0 > x) R = mid;
		if(p[mid]*1.0-x > eps) R = mid;
		else L = mid+1;
	}
	return L;
}
int G2(int x)
{
	int L = 1,R = m;
	while(L < R)
	{
		int mid = (L+R) >> 1;
		if(p[mid] >= x) R = mid;
		else L = mid+1;
	}
	return L;
} 

int main()
{
 	freopen("detect5.in","r",stdin);
 	freopen("detect.out","w",stdout);
//	srand(time(NULL));
	scanf("%d",&T);
	while(T--)
	{
		Case++;
		memset(vis,1,sizeof(vis));
		ans = 0;
		scanf("%d%d%d%d",&n,&m,&l,&v);
		for(int i = 1;i <= n;i++)
		{
			scanf("%d%d%d",&a[i].d,&a[i].v,&a[i].a);
			f &= (a[i].a == 0);
			f1 &= (a[i].a > 0);
		}
		for(int i = 1;i <= m;i++) scanf("%d",&p[i]);
		for(int i = 1;i <= n;i++)
		{
			V = a[i].d*1.0;
			int x = v*v-a[i].v*a[i].v,y = 2*a[i].a,l,r;
			if(y == 0)
			{
				if(a[i].v > v && p[m] >= a[i].d)
				{
					l = G(V);
					ans++;
					b[i] = make_pair(l,m);
				}
			}
			else
			{
				V += (1.0*x*1ll)/(1.0*y);
				if(a[i].a > 0)
				{
					if(p[m] > V && p[m] >= a[i].d) ans++;
				}
				else
				{
					l = lower_bound(p+1,p+m+1,a[i].d)-p;
					r = G(V)-1;
					if(r >= l && r <= m) //
					{
						ans++;
						b[i] = make_pair(l,r);
					}
				}
			}
		}
		printf("%d %d\n",ans,m-1);
//		printf("%d ",ans);
//		if(f || f1)
//		{
//			if(ans != 0) printf("%d\n",m-1);
//			else printf("%d\n",m);
//		}
	}
	return 0;
}


在调第一问,发现大样例5(ai<0a_i < 0)都会多检测出几辆车,怀疑是第78、79行出了问题,大佬求调……

2024/10/30 20:48
加载中...