本来是打算出进模拟赛里的，因为一些原因先咕咕了。以下是原本想放进模拟赛中的部分分：

每个测试点中至多能询问 $200$ 次。

Subtask 1（$10$ 分）：保证 $T \le 10$，$n \le 5$。在此子任务中，你只需要在 $200$ 次询问内找出 $n$ 个车的位置，即可获得满分。

Subtask 2（$10$ 分）：保证 $T \le 10$，$n \le 32$。在此子任务中，你只需要在 $200$ 次询问内找出 $n$ 个车的位置，即可获得满分。

Subtask 3（$10$ 分）：保证第一行没有车。在此子任务中，你的得分情况将由询问次数的多少决定：

若你询问了 $x$ 次，则你可以获得 $\min(\max(21-x,0),10)$ 分。

Subtask 4（$10$ 分）：保证存在一行没有车。在此子任务中，你的得分情况将由询问次数的多少决定：

若你询问了 $x$ 次，则你可以获得 $\min(\max(21-x,0),10)$ 分。

Subtask 5（$20$ 分）：保证 $n = 500$，每行每列恰有一个车，且车的位置在所有方案中随机生成。在此子任务中，你的得分情况将由询问次数的多少决定：

若你询问了 $x$ 次：

• 若 $x \le 26$，则你可以获得 $\min(31-x,20)$ 分。
• 若 $x > 26$，则你可以获得 $5$ 分。

Subtask 6（$40$ 分）：无特殊限制。在此子任务中，你的得分情况将由询问次数的多少决定：

若你询问了 $x$ 次：

• $x \le \lceil \log n \rceil + 2$，则你可以获得 $40$ 分。
• $x \le \lceil \log n \rceil + 42$，则你可以获得 $30 - \frac{1}{2}(x - \lceil \log n \rceil - 2)$ 分。
• $x > \lceil \log n \rceil + 42$，则你可以获得 $10$ 分。

以下是题解：

Subtask 1：

读题分，直接把每一个格子拿出来单独询问即可，询问次数 $n^2$ 次，可以获得 $10$ 分。

Subtask 2：

性质 1：对于一个初始所有格子都是被支配的棋盘，要么满足每一行都有至少一个车，要么满足每一列都有一个车。

证明就是，你考虑若有一行没有车，且此行所有格子都是被支配的，则每列都要有至少一个车，列同理，得证。

那么我们先花 $n$ 次询问是否每行都有车，然后直接对每一行 / 列二分出其车的位置即可，询问次数 $n(1 + \log n)$ 次，可以获得 $20$ 分。

Subtask 3：

根据性质 1，因为第一行没有车，因此每一列都有至少一个车。

我们将第一行作为检验格，可以对每一列的车的位置都一起二分，只需要 $\log n$ 次询问，可以获得 $10$ 分。

Subtask 4：

考虑延续 Subtask 3 的做法，此时我们需要在 $2$ 次询问内找到没有任何一个车的行。

考虑第一次询问进行以下询问：

00000000
11000000
10100000
10010000
10001000
10000100
10000010
10000001

即 $a_{i,j} = [i=j \| j=1][i\neq 1]$。

考虑我们可以通过这个询问来得到什么信息，具体地，对于所有 $a_{i,i} = 1$（记 $b_{i,j}$ 为交互库返回的矩阵中 $(i,j)$ 的值）：

• 若 $b_{i,i} = 0$，则说明位置 $(1,i),(i,i)$ 一定不是车。
• 若 $b_{i,i} = 1$，则说明位置 $(1,i),(i,i)$ 中有至少一个车。

那么第二次询问比较简单，具体地，我们只需要将上一次询问中所有满足 $b_{i,i} = 0$ 的 $i$，将所有 $a_{i,1 \sim n}$ 全都赋值为 $1$，且将 $a_{1,1 \sim n}$ 赋值为 $1$ 即可。

对于所有存在 $a_{i,j} = 1$ 的 $i$，分讨其 $b_{i,1}$ 的值，具体地：

• 若 $b_{i,1} = 0$，则说明这一行没有车。
• 若 $b_{i,1} = 1$，则说明这一行有车。

那么我们此时容易找到一个没有车的行，将其重编号到第一行，跑 Subtask 3 的做法即可，询问次数为 $\log n + 2$ 次，可以获得 $20$ 分。

Subtask 5：

Subtask 6 的一部分，如果你没有考虑完全或者写挂了可以拿到这档分。

Subtask 6：

发现此时我们需要知道一个事情，就是到底是每行都有车还是每列都有车。

考虑延续 Subtask 4 部分的第一次询问的思路，第一次询问后，若 $b_{1,1} = 0$，则说明第一行一定没有车，直接跑 Subtask 3 的做法即可。否则说明第一行一定有车。

考虑找出任意一个 $b_{i,i} = 0(2 \le i \le n)$ 的 $i$ 作为 $p$，进行以下分讨：

不存在一个 $p$：

则此时，除了第一行，所有行的 $(i,1),(i,i)$ 中都有至少一个车，考虑询问一次 $a_{i,j} = [i=j]$，然后对于第一行的车二分查找其位置即可，询问次数为 $2 + \lceil \log n \rceil$ 次。

存在一个 $p$：

则我们第二次询问中将 $a_{1,1},a_{1,p},a_{p,p}$ 赋值为 $1$，并且将所有满足在第一次询问中 $b_{i,i} = 1(2 \le i \le n)$ 的 $i$ 在第二次询问中将 $a_{i,1}$ 赋值为 $1$，其余赋值为 $0$ 后进行第二次询问。

在进行询问后，考虑询问中所有 $a_{i,1} = 0$（所有 $a_{i,1} = 0$ 的格子一定满足 $(i,1),(i,i)$ 没有车）的返回值 $b_{i,1}$，若 $b_{i,1} = 0$，则说明此行没有车，直接跑 Subtask 4 的做法即可，否则说明此行有车。

那么若没有跑 Subtask 4 的算法，则说明所有行都有至少一个车。且此时只会存在两种类型的行，第一种是车一定在第 $(i,2 \sim n)$ 列中，第二种是车一定在 $(i,1)$ 或 $(i,i)$ 中。

不过这是不完全的，因为此时第一行的车可能在任意位置，这时我们的 $a_{1,1} = a_{1,p} = a_{p,p}$ 就有效果了，我们进行以下分讨：

• 若 $b_{p,p} = 1$，则说明 $(1,p)$ 有车。
• 若 $b_{p,p} = 0$ 且 $b_{1,p} = 1$，则说明 $(1,1)$ 有车。
• 否则，则说明 $(1,1)$ 无车，我们确定了第一行的车在 $(1,2 \sim n)$ 中。

因此此时所有行均为两种类型的行之一。

考虑仅存在第一种类型的行怎么做，这是比较 trivial 的，只需要将 $(i,1)$ 作为检测位，每一行同时进行二分即可。

现在考虑两种类型的行都存在怎么做，我们考虑到这么一个事实：由于初始时第一种类型的行的车的所有范围都在 $[2,n]$ 中，那么此时我们考虑第一次询问时所有第一种类型的行二分时都问同一边，设第 $i$ 行（所有第一种类型的行 $i$）其询问的区间为 $[l,r]$，我们将所有满足 $l \le j \le r$ 的 $a_{i,j}$ 和 $a_{i,1}$ 都赋值为 $0$，其余赋值为 $1$ 即可进行二分（$a_{i,1}$ 作为检验格，因为此时所有 $(i,1)$ 一定都不为车），那么此时，在第一种类型的行进行二分时，我们可以顺带询问掉第二种类型的行 $i$ 满足 $a_{i,i} = 0$ 时不会被任何第一种类型的车影响到的位置 $(i,i)$，那么询问后，若 $b_{i,i} = 1$，则说明 $(i,i)$ 是车，否则说明 $(i,1)$ 是车。

不过这样实际上还是有问题的，有可能第一种类型的车最后一个二分的区间还是包含了第 $i$ 列并且第 $i$ 行为第二种类型的行，那么你就问不出来第 $i$ 行的车是 $(i,1)$ 还是 $(i,i)$，那么怎么办呢，我们直接考虑对于第一种类型的行的每次二分中对于第 $p$ 列靠拢进行二分即可，因为 $(1,p),(p,p)$ 不为车，因此第 $p$ 行为第一种类型的行，最后一次二分所有第一种类型的行的聚集区间一定不会对其造成影响，因此此时所有的第二种类型的车的位置都能被问出来，询问次数为 $2 + \lceil \log n \rceil$ 次。

于是我们就在 $2 + \lceil \log n \rceil$ 次询问解决了该问题。