70pts 求调 WA#4 #8 #10
查看原帖
70pts 求调 WA#4 #8 #10
494736
funnyfruit楼主2024/10/29 21:19

讨论区hack与大样例均通过,但民间数据没过,求调

#include<bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
const int N = 2e5 + 10;
const double esp=1e-12;
int a[N],now=1,n,T,v[N],d[N],m,L,Vt,p[N];
double V,dx;int head,tail;
int ans,ans2,dx1,dx2;
void read(int &a){
    int f=1,t=0;
    char ch;
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        t=t*10+ch-48;
        ch=getchar();
    }
    a=t*f;
}
int Find(int x){
    int l=0,r=m,mid=(l+r+1)>>1;
    while(l<r){
        if(p[mid]>x){
            r=mid-1;
        }else{
            l=mid;
        }
        mid=(l+r+1)>>1;
    }
    return l;
}
struct car{
    int from,to;
    bool flag;
}c[N];
bool cmp(car a,car b){
    if(a.to==b.to)return a.from<b.from;
    return a.to<b.to;
}
bool check(int a,int b){
    return !(a%b);
}
signed main()
{
    //freopen("detect.in","r",stdin);
    //freopen("detect.out","w",stdout);
    read(T);
    while(T--){
        read(n);read(m);read(L);read(Vt);
        V=Vt;
        ans=ans2=now=0;
        memset(c,0,sizeof(c));
        for(int i=1;i<=n;i++){read(d[i]),read(v[i]),read(a[i]);}
        for(int i=1;i<=m;i++)read(p[i]);
        for(int i=1;i<=n;i++){
            if(v[i]<=V && a[i]<=0 ){
                head=tail=0;
            }else if(v[i]>V && a[i]>=0){
                head=d[i];tail=L;
            }else if(v[i]>V){
                head=d[i];
                dx=(V*V-v[i]*v[i])/2/a[i];
                dx1=(V*V-v[i]*v[i]);
                dx2=2*a[i];
                if(check(dx1,dx2))tail=d[i]+floor(dx)-1;
                else tail=d[i]+floor(dx);
            }else{
                tail=L;
                dx=(V*V-v[i]*v[i])/2/a[i];
                dx1=(V*V-v[i]*v[i]);
                dx2=2*a[i];
                if(check(dx1,dx2))head=d[i]+ceil(dx)+1;
                else head=d[i]+ceil(dx);
            }//计算超速区间的位置
            int f=lower_bound(p,p+m+1,head)-p;
            int e=Find(tail);//第一个和最后一个捕捉到摄像头
            if(f>e || e==0 && f==0)continue;
            c[i].from=f;c[i].to=e;c[i].flag=true;
            ans++;
        }
        sort(c+1,c+n+1,cmp);
        int i=1;
        while(i<=n){
            if(c[i].flag){
                ans2++;
                while(now+1<=c[i].to)now++;
                while(c[i].from<=now && i<=n )i++;
            }else{
                i++;
            }
        }
        printf("%lld %lld\n",ans,m-ans2);
    }
	return 0;
}
2024/10/29 21:19
加载中...