自动搬运

查看原文

来自洛谷，原作者为

	RainySoul 弱省弱校弱鸡CSP-J三等选手

搬运于2025-08-24 23:18:07，当前版本为作者最后更新于2025-08-13 08:16:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

好玩！好题要点赞。但是别人怎么都是两分钟秒了，好像难度虚高。

首先考虑我们询问的步骤应该是确定出每个单次的词义之后，先跳到与宝藏 $x$ 坐标相同的点上，然后跳到与宝藏 $y$ 坐标相同的点上。

问出词义这个东西不能再简单了，从 $(0,0)$ 开始询问，然后跳到 $(1,1)$，然后跳回 $(0,0)$，稍微分讨即可。只有宝藏在 $(1,0)$ 或者 $(0,1)$ 的时候你会问出两个 At the same distance，其他时候跳到 $(1,1)$ 问出的都是 Closer，跳回 $(0,0)$ 问出的都是 Further。

确定一维坐标的过程可以直接二分，现在范围是 $[l,r]$ 时你从 $l$ 跳到 $r$ 就可以知道宝藏是在 $[l,mid]$ 还是 $[mid+1,r]$，最劣情况下两次操作可以将询问范围减半，$2^{16}=65536<10^6$，还不太够用。

想到一个比较上流的做法，考虑能不能直接两维一起确定。发现只要跳当前范围矩阵的三个角就可以将两维都减少一半。

然后就是三次操作将二维都变为原来一半，这部分需要的操作次数是 $3\times \log(10^6)=3\times 19.931568569=60$，加上确定词义的 $3$ 次，共是 $63$ 次，卡得非常死。

/*落叶的位置 谱出一首诗
时间在消逝 我们的故事开始*/
#include<bits/stdc++.h>
using namespace std;
int main(){
    string notfound,closer,further;
    cout<<"0 0\n";
    getline(cin,notfound);
    if(notfound.back()=='!')return 0;
    cout<<"1 1\n";
    getline(cin,closer);
    if(closer.back()=='!')return 0;
    cout<<"0 0\n";
    getline(cin,further);
    if(closer==further){
        string temp;
        cout<<"0 1\n";
        getline(cin,temp);
        if(temp.back()=='!')return 0;
        cout<<"1 0\n";
        getline(cin,temp);
        if(temp.back()=='!')return 0;
    }
    int lx=0,rx=1000000,ly=0,ry=1000000;
    while(1){
        string temp1,temp2;
        int midx=(lx+rx)>>1,midy=(ly+ry)>>1;
        cout<<rx<<" "<<ly<<'\n';
        getline(cin,temp1);
        if(temp1.back()=='!')return 0;
        cout<<rx<<" "<<ry<<'\n';
        getline(cin,temp2);
        if(temp2.back()=='!')return 0;
        if(temp1==closer)lx=midx+1;
        else if(temp1==further)rx=midx;
        else lx=rx=midx;
        if(temp2==closer)ly=midy+1;
        else if(temp2==further)ry=midy;
        else ly=ry=midy;
        cout<<lx<<" "<<ly<<'\n';
        getline(cin,temp2);
        if(temp2.back()=='!')return 0;
    }
    return 0;
}

广告：强推林俊杰《愿与愁》《关键词》