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;
}