U401797 [THUWC2024]小C的矩阵

小 C 有一个 $n×m$ 的 $01$ 矩阵，保证其中至少有一个位置的数 $1$ ，你要寻找其中最靠近 $(n,m)$ 的那个，即你需要找到位置 $(x,y)$ ，满足 $a_{x,y}=1$ 的同时 $x+y$ 最大 这是一道交互题，这道题目的矩阵是在调用你的程序前就被交互库生成并不再改变的，即交互库不会根据你的询问动态构造矩阵。 如果你的询问均合法且次数不超过次数上限，保证此时交互库的耗时的总时间不超过 $0.1s$ ，消耗的总内存不超过 $100MiB$ 。 请不要使用 `#program` 命令等攻击交互库或探测搜索交互库内部变量，否则后果自负。

你可以使用 `Ask` 函数询问某个子矩形中是否含有 $1$ 。 ```cpp Ask(int l ,int r ,int u ,int v) ``` 你需要保证 $1\le l \le r \le n,1\le u \le v \le m$ ，表示你要询问第 $l$ 行到第 $r$ 行，第 $u$ 列到第 $v$ 列的子矩阵中是否有 $1$ ，若有返回 $1$ ,若无返回 $0$ 。 其计算方法为： $$\left[\sum_{l\le x \le r,u\le y \le v}a_{x,y}>0\right]$$ 当然你的询问是有一些限制的，比如询问次数 $s_1$ 和询问规模 $s_2$ 。如果你的询问次数超过 $10^6$ ，小C会直接拒绝回答你的询问并判定答案错误。 其中 $s_2=\sum max(r-l+1,v-u+1)$ 。 你不需要也不应修改交互器，只需要在下发文件中修改 Solve 函数的文件即可。你不需要也不应实现主函数，也不应有任何输出。 交互库会调用恰好一次 `Solve` 函数 ```cpp Solve(int n ,int m ,int id) ``` 其中 $id$ 代表子任务编号，若是样例则为 $0$ 。

第一行 $3$ 个整数， $n,m$ 和 $id$ 接下来是一个 $n$ 行 $m$ 列的 $01$ 矩阵

返回最大的 $x+y$

| 子任务编号 | 分值 | $n=$ | $m=$ | | :----------: | :----------: | :----------: | :----------: | | $1$ | $4$ | $2$ | $2$ | | $2$ | $20$ | $1$ | $4096$ | | $3$ | $76$ | $4096$ | $4096$ | 每个子任务的评分标准如下： 如果你的 `Solve` 函数调用的 `Ask` 均合法且不超过 $10^6$ 次，而且返回了正确的答案，则该子任务得分为 $s_1$ 对应的分值与 $s_2$ 对应的分值之和，否则该子任务得分为 $0$ 。 对于子任务 $1$ ： | $s_1\in$ | 分值 | $s_2\in$ | 分值 | | :----------: | :----------: | :----------: | :----------: | | $(3,+\infty)$ | $0$ | $(4,+\infty)$ | $0$ | | $(2,3]$ | $1$ | $(3,4]$ | $1$ | | $[0,2]$ | $2$ | $[0,3]$ | $2$ | 对于子任务 $2$ ： | $s_1\in$ | 分值 | $s_2\in$ | 分值 | | :----------: | :----------: | :----------: | :----------: | | $(24,+\infty)$ | $0$ | $(8192,+\infty)$ | $0$ | | $(15,24]$ | $2$ | $(4100,8192]$ | $3$ | | $(13,15]$ | $5$ | $(4096,4100]$ | $7$ | | $(12,13]$ | $7$ | $(4095,4096]$ | $10$ | | $[0,12]$ | $8$ | $[0,4095]$ | $12$ | 对于子任务 $3$ ： | $s_1\in$ | 分值 | $s_2\in$ | 分值 | | :----------: | :----------: | :----------: | :----------: | | $(10^6,+\infty)$ | $0$ | $(10^9,+\infty)$ | $0$ | | $(2×10^5,10^6]$ | $2$ | $(10^7,10^9]$ | $2$ | | $(10^5,2×10^5]$ | $6$ | $(2×10^6,10^7]$ | $7$ | | $(2×10^4,10^5]$ | $10$ | $(10^6,2×10^6]$ | $15$ | | $(10^4,2×10^4]$ | $13$ | $(5×10^5,10^6]$ | $20$ | | $(8300,10^4]$ | $16$ | $(2×10^5,5×10^5]$ | $27$ | | $(8200,8300]$ | $18$ | $(10^5,2×10^5]$ | $45$ | | $(8192,8200]$ | $19$ | $(7.4×10^4,10^5]$ | $54$ | | $[0,8192]$ | $20$ | $[0,7.4×10^4]$ | $56$ | ### 样例解释 一种可能的你的程序与交互库在调用你的程序之后的运行情况： | 你的程序 | 交互库 | 说明 | | :----------: | :----------: | :----------: | | 调用 $Ask(2,3,2,3)$ | 返回 $1$ | $a_{2,2}+a_{2,3}+a_{3,2}+a_{3,3}=1$ | | 调用 $Ask(3,3,2,3)$ | 返回 $0$ | $a_{3,2}+a_{3,3}=0$ | | 调用 $Ask(2,2,3,3)$ | 返回 $1$ | $a_{2,3}=1$ | | 返回 $5$ | 打印 $Correct,s1=3,s2=5$ | 回答正确 | ### 提示 在本地调试时可使用题目下发的 simulator.cpp ，其使用方法如下 先在目录下打开终端编译： `` g++ simulator.cpp -o simulator -g -std=c++14 -O2 `` 其中````代表你的程序文件 然后在终端运行``simulator``并输入数据即可 为了让选手们更好的答题，选手们应在**模版代码**的基础上进行恰当的修改得到提交的**答案代码** ```cpp #include extern "C" { extern bool Ask(int l , int r , int u , int v); extern int Solve(int n , int m , int id); } int Solve(int n , int m , int id){ // 请开始你的表演 return ; } /* 以下代码为调用Ask函数的实例 int Solve(int n , int m , int id){ if(Ask(1,n,1,m)) return n+m; return n+m-1; } */ ``` #### 民间版本，感谢 PKU 的 [jun头吉吉](https://www.luogu.com.cn/user/174304)。