U402145 THUWC Day1T3
题目描述
**这是一道交互题。**
## 题目描述
小 C 有一个 $n\times m$ 的 $01$ 矩阵 $A$，他想让小 R 猜一猜，矩阵中最接近 $(n,m)$ 的 $1$ 在哪里。 形式化地说，他想让小 R 猜出满足 $A_{i,j}=1$ 的最大的 $i+j$。小 C 保证了他的矩阵里至少有一个 $1$。
小 C 允许 小 R 询问他一个子矩阵内是否有 $1$。每次询问小 R 可以选定 $1\le u\le d\le n$，$1\le l\le r\le m$，小 C 将会告诉他 $\sum_{i=u}^d\sum_{j=l}^rA_{i,j}$ 是否非零。
小 C 不希望小 R 问他太多个问题，也不希望小 R 询问的子矩形过大。他决定统计小 R 的询问次数（记作 $C_1$），以及小 R 所有询问的 $\max(d-u+1,r-l+1)$ 之和（记作 $C_2$）。
你需要帮助小 R 问出满足 $A_{i,j}=1$ 的最大的 $i+j$，同时保证 $C_1,C_2$ 不超过小 C 的限制。当然，只要你的询问次数不超过 $10^6$，小 C 都会根据 $C_1,C_2$ 给出一部分的分数。如果你的询问次数超过 $10^6$，小 C 将会拒绝你之后的询问并直接判定你回答错误。
## 实现细节
你不需要，也不应该实现主函数，你只需要实现如下函数：
```cpp
extern "C" int Find (int n, int m, int id);
```
- $n,m$ 的含义如【题目描述】中所示，$id$ 表示该测试点所属的子任务标号。特别地，样例的子任务编号为 $0$。
- 你需要返回一个正整数表示满足 $A_{i,j}=1$ 的最大的 $i+j$。
你可以通过调用一下函数来和交互库进行交互：
```cpp
extern "C" int Ask (int u, int d, int l, int r);
```
- $u,d,l,r$ 的含义如【题目描述】中所示，你需要保证 $1\le u\le d\le n$，$1\le l\le r\le m$。
- 该函数返回一个非负整数 $0$ 或 $1$，返回值为 $0$ 代表该子矩形中没有 $1$，返回值为 $1$ 代表该子矩形中有 $1$。
评测时，交互库会恰好调用 `Find` 一次。
本题保证所使用的矩阵再交互开始之前已经完全确定，不会根据和你的程序的交互过程动态构造，因此题目中的交互操作都是确定性的，你不需要关心这些操作再交互库中的具体实现。
## 样例输入
```plain
3 3 0
010
001
100
```
## 样例输出
```plain
Correct.
C_1=3, C_2=4.
```
## 样例解释
以下是一种可能的交互过程:
| 选手程序 | 交互库 | 说明 |
| :----------: | :----------: | :----------: |
| | 调用 `Find(3, 3, 0)` | |
| 调用 `Ask(2, 3, 2, 3)` | 返回 $1$ | $A_{2,2}+A_{2,3}+A_{3,2}+A_{3,3}=1>0$ |
| 调用 `Ask(3, 3, 3, 3)` | 返回 $0$ | $A_{3,3}=0$ |
| 调用 `Ask(2, 2, 2, 2)` | 返回 $0$ | $A_{2,2}=0$ |
| 返回 $5$ | 输出 `Correct.` | $A_{2,3}=1$，$2+3=5$ |
| | 输出 `C_1=3, C_2=4.` | 评分参数 $C_1=3$，$C_2=4$ |
输入格式
无
输出格式
无
说明/提示
代码模板：
```cpp
extern "C" int Ask (int u, int d, int l, int r);
extern "C" int Find (int N, int M, int id){
//write your code here
}
```
你的程序不需要包含 `matrix.h` 头文件。
## 子任务
| 子任务编号 | 分值 | $n=$ | $m=$ |
| :----------: | :----------: | :----------: | :----------: |
| $1$ | $4$ | $2$ | $2$ |
| $2$ | $20$ | $1$ | $4096$ |
| $3$ | $76$ | $4096$ | $4096$ |
## 评分方式
对于每个子任务，该子任务得分为其中所有测试点得分的最小值。
对于所有测试点，若询问不符合要求或 $C_1>10^6$ 或答案不正确，得 $0$ 分。否则，将根据该测试点所属的子任务编号，按照评分参数 $C_1,C_2$ 分别给出分数 $s_1,s_2$，该测试点的最终得分为 $s_1+s_2$。
对于第一个子任务，$s_1,s_2$ 的计算方式如下：
| $C_1\in$ | $s_1=$ | $C_2\in$ | $s_2=$ |
| :----------: | :----------: | :----------: | :----------: |
| $(3,+\infty)$ | $0$ | $(4,+\infty)$ | $0$ |
| $(2,3]$ | $1$ | $(3,4]$ | $1$ |
| $[0,2]$ | $2$ | $[0,3]$ | $2$ |
对于第二个子任务，$s_1,s_2$ 的计算方式如下：
| $C_1\in$ | $s_1=$ | $C_2\in$ | $s_2=$ |
| :----------: | :----------: | :----------: | :----------: |
| $(4096,+\infty)$ | $0$ | $(10^6,+\infty)$ | $0$ |
| $(2048,4096]$ | $2$ | $(10^5,10^6]$ | $1$ |
| $(1024,2048]$ | $3$ | $(5\times10^4,10^5]$ | $2$ |
| $(160,1024]$ | $4$ | $(2\times10^4,5\times10^4]$ | $3$ |
| $(80,160]$ | $5$ | $(10^4,2\times10^4]$ | $5$ |
| $(16,80]$ | $6$ | $(8192,10^4]$ | $7$ |
| $(13,16]$ | $7$ | $(6144,8192]$ | $8$ |
| $(12,13]$ | $8$ | $(4096,6144]$ | $9$ |
| $[0,12]$ | $10$ | $[0,4096]$ | $10$ |
对于第三个子任务，$s_1,s_2$ 的计算方式如下：
| $C_1\in$ | $s_1=$ | $C_2\in$ | $s_2=$ |
| :----------: | :----------: | :----------: | :----------: |
| $(10^6,+\infty)$ | $0$ | $(10^9,+\infty)$ | $0$ |
| $(6\times10^5,10^6]$ | $4$ | $(4\times10^7,10^9]$ | $3$ |
| $(3\times10^5,6\times10^5]$ | $6$ | $(1.7\times10^7,4\times10^7]$ | $5$ |
| $(10^5,3\times10^5]$ | $7$ | $(2\times10^6,1.7\times10^7]$ | $7$ |
| $(5\times10^4,10^5]$ | $9$ | $(10^6,2\times10^6]$ | $25$ |
| $(3.5\times10^4,5\times10^4]$ | $10$ | $(3\times10^5,10^6]$ | $29$ |
| $2\times10^4,3.5\times10^4$ | $13$ | $(2\times10^5,3\times10^5]$ | $31$ |
| $(1.3\times10^4,2\times10^4]$ | $15$ | $(10^5,2\times10^5]$ | $36$ |
| $(8300,1.3\times10^4]$ | $17$ | $(8\times10^4,10^5]$ | $46$ |
| $(8192,8300]$ | $19$ | $(7.4\times10^4,8\times10^4]$ | $50$ |
| $[0,8192]$| $20$ | $[0,7.4\times10^4]$ | $56$ |