题解 CF788D【Finding lines】

· · 题解

CF788D Finding lines解题报告：

更好的阅读体验

题意

有n条平行于y轴的直线m条平行于x轴的直线，你每次询问可以得到一个点距离其最近的直线距离，在不多于3\times 10^5次询问中你需要确定这些直线。

1\leqslant n,m\leqslant 10^4

分析

普通的交互题。

考虑这些直线都会与一三象限平分线y=x产生交点，我们可以在这条直线上分治确定这些交点。

具体地，我们每次处理区间[l,r]的时候询问(mid,mid)（mid为区间中点），如果返回值res为0那么就确定了一个交点，且继续递归[l,mid-1]与[mid+1,r]，否则递归到区间[l,mid-res]与[mid+res,r]。

这一部分的询问次数有点难分析（下面纯口胡）：考虑solve一个有线段的区间会在两次询问中找到某条线段，并产生3个区间的无用递归（原区间没有这条线段的另一个区间，以及找到这条线段后递归的两个区间），而如果某个区间没有线段，只需要一次询问就可以排除（因为会递归到两个空区间），所以询问次数有一个很松的上界为5(n+m)，但是实际表现甚至跑不满3(n+m)。

找到这些直线与y=x交点后，我们任取一个之前询问不在线段上的点(no,no)，枚举每个交点(k,k)，如果(k,no)在线段上的话就有一条x=ans，如果(no,k)在线段上的话就有一条y=k（注意有可能同时存在）。

这一部分的询问次数上界为2(n+m)。

那么总询问次数最多7(n+m)，似乎在CF上最多只跑到5(n+m)（还是小数据）。

代码

#include<stdio.h>
#include<vector>
using namespace std;
int no;
vector<int>ans,X,Y;
int ask(int x,int y){
    printf("0 %d %d\n",x,y);
    fflush(stdout);
    int res;
    scanf("%d",&res);
    return res;
}
void solve(int l,int r){
    if(l>r)
        return ;
    int mid=(l+r)>>1,res=ask(mid,mid);
    if(res==0)
        ans.push_back(mid),res=1;
    else no=mid;
    solve(l,mid-res),solve(mid+res,r);
}
int main(){
    solve(-100000000,100000000);
    for(int i=0;i<ans.size();i++){
        if(ask(ans[i],no)==0)
            X.push_back(ans[i]);
        if(ask(no,ans[i])==0)
            Y.push_back(ans[i]);
    }
    printf("1 %d %d\n",X.size(),Y.size());
    for(int i=0;i<X.size();i++)
        printf("%d%c",X[i],i==X.size()-1? '\n':' ');
    for(int i=0;i<Y.size();i++)
        printf("%d%c",Y[i],i==Y.size()-1? '\n':' ');
    return 0;
}