题面下载

样例下载

时间限制： 1.0 秒

空间限制： 256 MB

题目描述

刚刚越过绝境长城，只见天空中出现了炫目的光芒 —— 圣诞老人出现了。

元旦三侠立刻进入战斗。生蛋侠、圆蛋侠和零蛋侠分别有 $n_a, n_b, n_c$ 个激光炮。生蛋侠的激光炮的威力分别为 $a_0, a_1, \dots, a_{n_a - 1}$，圆蛋侠的激光炮的威力分别为 $b_0, b_1, \dots, b_{n_b - 1}$，零蛋侠的激光炮的威力分别为 $c_0, c_1, \dots, c_{n_c - 1}$。

元旦三侠的激光炮的威力已经按从小到大的顺序排好序了，即 $a_{i - 1} \leq a_i,\ b_{i - 1} \leq b_i,\ c_{i - 1} \leq c_i$。

由于元旦三侠精力有限，他们得废弃掉 $k$ 个激光炮。为了更好地进行战斗，他们决定废弃掉威力前 $k$ 小的激光炮。

赶快帮助元旦三侠，让激光炮投入战斗吧！你只需要告诉他们威力第 $k$ 小的激光炮威力是多少。

交互方式

这是一道函数式交互题，不需要选手考虑输入输出，也不要从标准输入读入数据，或将任何内容输出到标准输出，否则会影响判题。

你提交的代码需要包含头文件 kth.h。

你需要实现以下函数：

int query_kth(int n_a, int n_b, int n_c, int k);

• n_a：生蛋侠拥有的激光炮数目 $n_a$，保证 $n_a\ge 0$。
• n_b：圆蛋侠拥有的激光炮数目 $n_b$，保证 $n_b\ge 0$。
• n_c：零蛋侠拥有的激光炮数目 $n_c$，保证 $n_c\ge 0$。
• k：要查询的排名 $k$。保证 $1\le k\le n_a+n_b+n_c$。

返回值为威力第 $k$ 小的激光炮威力值。

你可以调用以下函数：

int get_a(int i);
int get_b(int i);
int get_c(int i);

• get_a(i) 将返回 $a_i$。如果 $i$ 在 $0\le i<n_a$ 之外，该函数将返回 $2147483647$。
• get_b(i) 将返回 $b_i$。如果 $i$ 在 $0\le i<n_b$ 之外，该函数将返回 $2147483647$。
• get_c(i) 将返回 $c_i$。如果 $i$ 在 $0\le i<n_c$ 之外，该函数将返回 $2147483647$。

以下我们给出一个代码提交实例（固定返回 233，仅作为可以通过编译的示例，不保证能得分）。

#include "kth.h"
int query_kth(int n_a, int n_b, int n_c, int k)
{
    return 233;
}

白盒交互库实例

具体请见附加文件区的 interactor.cc 和 kth.h。本题直接采用白盒交互库进行评测。

如果你本地的实现代码为 main.cc，则将交互库放在同一目录下，在 Linux 系统中输入以下命令行即可运行：

g++ main.cc interactor.cc -Wall -std=c++20 -o foo -lm -O2 -I/include

在 Windows 下会生成 foo.exe，在 Linux 下会生成 foo，你可以输入 .\foo.exe 或者 ./foo 命令行执行该文件。或者将交互库接口与你实现的函数统一在单代码文件中进行本地调试即可。

交互库将从标准输入读入如下格式的输入数据：

1. 第一行四个整数 $n_a,n_b,n_c,k$。
2. 第二行 $n_a$ 个整数，第 $i$ 个整数表示 $a_i$。
3. 第三行 $n_b$ 个整数，第 $i$ 个整数表示 $b_i$。
4. 第四行 $n_c$ 个整数，第 $i$ 个整数表示 $c_i$。

在 query_kth 返回后，交互库将输出你的答案以及 get_a、get_b、get_c 三个函数的总调用次数 $t$ 到标准输出。

2 3 3 5
1 2
1 5 6
2 3 3

3 6

样例 1 解释

所有激光炮从小到大排序后为 $1, 1, 2, 2, 3, 3, 5, 6$，所以第 $5$ 小的数为 $3$。输出的第二个整数 $6$ 为总调用次数，你可以认为这是一个调用了 $6$ 次 get_a、get_b、get_c 函数的程序的输出。

样例 2

见题目文件区的 2.in 和 2.ans。

子任务

对于所有测试点，保证 $0\le n_a,n_b,n_c\le 10^5,\ 1\le a_i,b_i,c_i\le 10^9$。

评分方式

设你的程序 get_a、get_b、get_c 三个函数的总调用次数为 $t$：

• 当你返回的答案错误或 $t>2000$ 时，该测试点不得分；
• 当你返回的答案正确且 $100<t\le 2000$ 时，则获得该测试点 $60\%$ 的分数；
• 当你返回的答案正确且 $t\le 100$ 时，获得该测试点全部分数。

提示

清华机试一直都是传统题，函数式交互题从来不会在正式场次当中出现。但是平时做 826/408 算法大题的时候，则会遇到这种函数式交互的方式，所以在学习初试《数据结构》一科，搭配曙梦 OJ 的《数据结构》辅助练习的时候可以多关注一下这种题目的本地调试。