QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 512 MB Total points: 100 Interactive

# 5375. Search

Statistics

这是一道交互题。

大 M 是一个充满优势的人,他尤其讨厌矩阵。现在他获得了和神交流的机会,但是神很喜欢矩阵。

现在他面前有一个矩阵,神不告诉他这个矩阵里有什么元素,但是神告诉了他这个矩阵里的元素两两不同且两两可以比较大小,神又告诉他,这个矩阵是“单调的”,即假设第 $i$ 行第 $j$ 列的矩阵元素是 $a_{i, j}$,那么 $i_1 < i_2$ 时 $a_{i_1, j} < a_{i_2, j}$,$j_1 < j_2$ 时 $a_{i,j_1} < a_{i,j_2}$。神又选定了 一个可以和矩阵里所有元素比较大小的元素 $x$,使得这个元素和矩阵中的元素都不同,大 M 不知道 $x$ 是多少。

神允许大 M 进行 $2$ 种询问:第 $1$ 种询问大 M 可以询问两个矩阵元素的大小关系, 第 $2$ 种询问大 M 可以询问一个矩阵元素和 $x$ 的大小关系。

大 M 请你帮他进行询问,并向神报告:矩阵中有多少个元素比 $x$ 小。

本题采用代码补全的方式作答,你需要在下发的样例交互程序 search.cpp 中的 namespace query 内实现一个 int main(int n) 函数,该函数接受矩阵大小 $n$ 作为参数,调用 ask1ask2 进行询问,然后返回求得的答案。

注意:

  1. 你不应当通过任何方式调用或访问除了 namespace query 里的内容、函数 askl、 函数 ask2 以外的任何函数或变址,也不应试图读入/输出任何信息或以任何方式试图改变评测程序的行为。为确保这一点,实际评测时用的代码和下发的代码将有所不同,并且我们将会进行检查,不符合要求的提交将被判为 $0$ 分。
  2. 提交时只需要提交namespace query里面的代码。
  3. 评测时的交互库使用了不超过 340MB 内存,即你可以使用至少 256MB 内存。
  4. 评测时的交互库在询问次数不超过限制的情况下运行时间不会超过2s,即你的程序至少有 2s 的运行时间。
  5. 评测时的交互库与下发的样例交互库才『本质上的区别(从输入/输出到判正确性 的方式等),但你不需要关心这些。

你需要实现的函数有:

int main(int n);

参数 $n$ 表示矩阵大小,返回值应当是问题的答案(矩阵中有多少个元素比 $x$ 小)。

你可以调用的函数有:

string askl(int x1,int y1,int x2,int y2);

对应第一种询问,参数 $(x_1, y_1)$ 和 $(x_2, y_2)$ 表示矩阵的两个元素,调用时需要保证 $1 \leq x_1, y_1, x_2, y_2 \leq n$ 且 $(x_1, y_1) \neq (X_2, y_2)$。该函数会返回字符串“<”或“>”(不含引号),表示两个元素的大小关系。

string ask2(int x,int y);

对应第二种询问,参数 $(x,y)$ 表示矩阵的某个元素,调用时需要保证 $1 \leq x,y \leq n$。该函数返回字符串“<”或“>”,表示这个元素和 $x$ 的大小关系。

输入格式

样例交互程序 search.cpp 会按以下格式从标准输入进行读入:

第一行,三个整数 $n, x, ans$,分别表示题目中的 $n$,$x$,以及答案。

接下来 $n$ 行,每行 $n$ 个整数表示矩阵。

需要保证矩阵元素及 $x$ 两两不同且矩阵满足单调性的限制。

输出格式

样例交互程序 search.cpp 会朝标准输出打印如下信息:你的答案是否正确、调用 ask1 的次数、调用 ask2 的次数、其他错误信息(如果有的话)。

样例数据

样例输入

3 7 6
1 2 4
3 6 8
5 9 10

样例输出

(取决于交互情况)

提示

子任务 1(10 分):$1 \leq n \leq 10$,允许调用至多 $64n$ 次 ask1 和至多 $45$ 次 ask2

子任务 2(20 分):$1 \leq n \leq 2\,000$,允许调用至多 $256n$ 次 ask1 和至多 $45$ 次 ask2

子任务 3(20 分):$1 \leq n \leq 2\,000$,允许调用至多 $192n$ 次 ask1 和至多 $38$ 次 ask2

子任务 4(25 分):$1 \leq n \leq 2\,000$,允许调用至多 $128n$ 次 ask1 和至多 $36$ 次 ask2

子任务 5(25 分):$1 \leq n \leq 2\,000$,允许调用至多 $64n$ 次 ask1 和至多 $34$ 次 ask2

对于 $100\%$ 的数据,$1 \leq n \leq 2\,000$。

题目保证矩阵元素和询问的数按照某种方式随机生成。

$5$ 个子任务分别有 $20, 30, 30, 30, 30$ 组测试数据,请评估自己程序的正确率。

在 QOJ 评测时,只有两个子任务,其中子任务 2 为 90 分且包含 $120$ 组测试数据。你的得分将取决于你调用 ask1ask2 的次数。