#1741. Search

    ID: 1741 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 普及 上传者: 标签>CTT赛事:contest1087来源:qoj.ac数据:公开样例二分答案

Search

Search

题目描述

标题: Search - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

The problem is available in the following languages: C++14, C++17, C++20, C++23

这是一道交互题。

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

现在他面前有一个矩阵,神不告诉他这个矩阵里有什么元素,但是神告诉了他这个矩阵里的元素两两不同且两两可以比较大小,神又告诉他,这个矩阵是"单调的",即假设第 i 行第 j 列的矩阵元素是 ai,j,那么 i1<i2 时 ai1,j<ai2,j,j1<j2 时 ai,j1<ai,j2。神又选定了 一个可以和矩阵里所有元素比较大小的元素 x,使得这个元素和矩阵中的元素都不同,大 M 不知道 x 是多少。

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

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

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

注意:

  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);

对应第一种询问,参数 (x1,y1) 和 (x2,y2) 表示矩阵的两个元素,调用时需要保证 1≤x1,y1,x2,y2≤n 且 (x1,y1)≠(X2,y2)。该函数会返回字符串"<"或">"(不含引号),表示两个元素的大小关系。

string ask2(int x,int y);

对应第二种询问,参数 (x,y) 表示矩阵的某个元素,调用时需要保证 1≤x,y≤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≤n≤10,允许调用至多 64n 次 ask1 和至多 45 次 ask2。

子任务 2(20 分):1≤n≤2000,允许调用至多 256n 次 ask1 和至多 45 次 ask2。

子任务 3(20 分):1≤n≤2000,允许调用至多 192n 次 ask1 和至多 38 次 ask2。

子任务 4(25 分):1≤n≤2000,允许调用至多 128n 次 ask1 和至多 36 次 ask2。

子任务 5(25 分):1≤n≤2000,允许调用至多 64n 次 ask1 和至多 34 次 ask2。

对于 100% 的数据,1≤n≤2000。

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

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

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

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

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