坐标。

Description

交互题。

给定 $R$、$C$、$R_s$、$C_s$、$X$，交互库会隐藏一个 $R\times C$ 的正整数网格，保证其满足以下条件：

• 没有两个位置上的数相等。
• 值域为 $[1,10^9]$。
• $(R_s,C_s)$ 是网格中最大的数。
• 对于任意两个相邻网格，与 $(R_s,C_s)$ 曼哈顿距离较远的网格的数更小。

你可以进行询问：给出 $r$、$c$，然后得知网格上 $(r,c)$ 位置的值。

在 $1000$ 次询问内，找到值恰好为 $X$ 的那个位置。

$1\le R,C\le 200$，$1\le R_s\le R$，$1\le C_s\le C$，$1\le X\le 10^9$，$X$ 一定在网格中出现。

Solution

把网格上所有 $\ge X$ 的位置标记上，这个东西的边界在四个象限都是一条折线，围成了一个神秘图形。

不难发现 $X$ 一定位于这个神秘图形的边缘，所以我们二分出四个方向的边界，拿一个指针扫过去，一路询问边缘上的所有值，最后找 $X$ 在哪就行了。

Code

:::success[代码]

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3fll
using namespace std;

// -------- grader.h ------------
// #include "grader.h"
int Measure(int RM, int CM);
void Pinpoint(int RP, int CP);
// ------------------------------

int find_first(int l,int r,auto check){
    while(l<r){
        int mid=(l+r)>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    return l;
}

int find_last(int l,int r,auto check){
    while(l<r){
        int mid=(l+r+1)>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    return l;
}

int mp[210][210];
int query(int x,int y){
    if(mp[x][y]) return mp[x][y];
    return mp[x][y]=Measure(x,y);
}

void solve(int n,int m,int px,int py,int h){
    int lbound,rbound,tbound,bbound;

    lbound=find_first(1,py,[&](int pos){return query(px,pos)>=h;});
    rbound=find_last(py,m,[&](int pos){return query(px,pos)>=h;});
    tbound=find_first(1,px,[&](int pos){return query(pos,py)>=h;});
    bbound=find_last(px,n,[&](int pos){return query(pos,py)>=h;});

    // tbound -> lbound
    for(int nowx=tbound,nowy=py;nowy>=lbound;nowy--) while(nowx<=px&&query(nowx,nowy)<h) nowx++;

    // tbound -> rbound
    for(int nowx=tbound,nowy=py;nowy<=rbound;nowy++) while(nowx<=px&&query(nowx,nowy)<h) nowx++;

    // bbound -> lbound
    for(int nowx=bbound,nowy=py;nowy>=lbound;nowy--) while(nowx>=px&&query(nowx,nowy)<h) nowx--;

    // bbound -> rbound
    for(int nowx=bbound,nowy=py;nowy<=rbound;nowy++) while(nowx>=px&&query(nowx,nowy)<h) nowx--;

    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(mp[i][j]==h) Pinpoint(i,j);
    Pinpoint(0,0);
}

void Rescue(int R,int C,int RS,int CS,int X){solve(R,C,RS,CS,X);}

:::