UOJ Logo Universal Online Judge

UOJ

附件下载 统计

这是一道交互题,仅支持 C++ 语言提交。

UOJ NOI Round 2077 有 $n$ 天,每天有 $n$ 道题。第 $i$ 天的第 $j$ 道题难度是 $a_{i,j}$。每一天的题目难度都是不降的,而且对于同一位置的题,每天的这道题的难度也是不降的。也就是说,对于 $\forall 1\le x\le n,1\le y_1< y_2\le n$,都有 $a_{x,y_1} \le a_{x,y_2}$ 且 $a_{y_1,x} \le a_{y_2, x}$。

小重和小庆想要知道这 $n^2$ 道题中第 $k$ 简单的题的难度。然而,他们现在并不知道每道题的难度是什么。他们只能在比赛的 $10^6$ 天内,每天选出一道题并鉴定其难度。

题目保证所有 $a_{i,j}$ 是预先给定的,不会根据你的操作而动态生成。

实现细节

你需要引用头文件 #include "matrix.h"。你可以调用以下函数与交互库进行交互:

long long query(int x, int y);

  • 这个函数会返回第 $x$ 天第 $y$ 题的难度。
  • 你需要保证 $1 \le x,y \le n$。
  • 在一个测试点中,你最多可以调用该函数 $10^6$ 次。

你不需要,也不应该实现主函数。在本题中,你只需要实现如下函数:

long long solve(int n, long long k);

  • 其中 $n$ 为比赛的天数和每天的题目数,函数的返回值应为所有 $a_{i,j}$ 中第 $k$ 小的值。
  • 最终测试时,对于每个测试点,交互库会调用恰好一次 solve 函数,并根据函数的返回值是否正确来评分。

在选手目录(题目附件)中,我们提供了 sample.cpp 供你参考,你可以在此基础上实现你的程序。

测试程序方式

本题目录下提供了 grader.cpp 文件。最终测试的交互库与下发交互库有不同,因此你的实现不应依赖交互库实现。

你需要将你的程序 matrix.cppgrader.cppmatrix.h 放置在同一目录下,并在该目录下使用如下编译命令得到可执行程序 matrix(.exe)

g++ -o matrix matrix.cpp grader.cpp -O2 -std=c++17

可执行程序从标准输入读入以下格式的数据:

  • 第一行,共两个整数 $n,k$。
  • 第二行一个整数 $type$ 表示数据生成方式。
  • 如果 $type=0$,那么接下来输入 $n$ 行,每行 $n$ 个整数,表示每道题的难度。

在本地测试时,请务必保证你的输入格式符合要求,否则我们不保证交互库会正常运行

如果你的输入合法且没有运行错误,下发的交互库将会根据你的调用输出如下信息:

  • 如果某次 query 函数的调用违反了 $1 \le x,y \le n$ 的限制或调用 query 次数超过 $10^6$ 次,输出错误信息:Wrong Answer 0!,并且交互库立即终止。
  • 如果 solve 函数的返回值正确,那么交互库会输出三个数,依次表示:solve 函数的返回值,$n$ 的值,query 函数的调用次数。

你的程序不应该操作标准输入输出,否则视为攻击交互库

样例一

input

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

output

5

样例二/三/四/五/六/七

见附件下载。

限制与约定

对于全部数据,保证 $1\leq n\le 2\times 10^5$,$1\le k\le n^2$,$0\le a_{i,j}\le 10^{18}$。

子任务编号 $n=$ 分值
1 $1000$ $10$
2 $5000$ $20$
3 $3\times 10^4$ $10$
4 $8\times 10^4$ $20$
5 $1.5\times 10^5$ $20$
6 $2\times 10^5$ $20$

时间限制:$\texttt{2s}$

空间限制:$\texttt{1GB}$

保证交互库的运行时间不超过 $\texttt{1s}$,使用空间不超过 $\texttt{512MB}$。