UOJ Logo Universal Online Judge

UOJ

#52. 【UR #4】元旦激光炮

统计

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

元旦三侠立刻进入战斗。生蛋侠、圆蛋侠和零蛋侠分别有 $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$ 小的激光炮威力是多少。

任务

你需要编写一个函数 query_kth,以确定威力值第 $k$ 小的激光炮威力值是多少。

  • query_kth(n_a, n_b, n_c, k)
    • n_a:生蛋侠拥有的激光炮数目 $n_a$。保证 $n_a \geq 0$。
    • n_b:圆蛋侠拥有的激光炮数目 $n_b$。保证 $n_b \geq 0$。
    • n_c:零蛋侠拥有的激光炮数目 $n_c$。保证 $n_c \geq 0$。
    • $k$:要查询的排名 $k$。保证 $1 \leq k \leq n_a + n_b + n_c$。

你可以调用三个函数 get_a、get_b、get_c 以帮助你确定第 $k$ 小的激光炮。我们会根据你调用这三个函数的总次数评分。

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

在一组测试数据中,query_kth 只会被调用一次。

实现细节

本题只支持 C/C++/Pascal。

你只能提交一个源文件实现如上所述的 query_kth 函数,并且遵循下面的命名和接口。

C/C++

你需要包含头文件 kth.h。

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

函数 get_a, get_b, get_c 的接口信息如下。

int get_a(int p);
int get_b(int p);
int get_c(int p);

Pascal

你需要使用单元 graderhelperlib。

function query_kth(n_a, n_b, n_c, k : longint) : longint;

函数 get_a, get_b, get_c 的接口信息如下。

function get_a(p : longint) : longint;
function get_b(p : longint) : longint;
function get_c(p : longint) : longint;

如果有不清楚的地方,见样例及测评库下载,内附了样例程序

评测方式

评测系统将读入如下格式的输入数据:

  1. 第 $1$ 行: $n_a, n_b, n_c, k$
  2. 第 $2$ 行:$n_a$ 个整数,第 $i$ 个整数表示 $a_i$。
  3. 第 $3$ 行:$n_b$ 个整数,第 $i$ 个整数表示 $b_i$。
  4. 第 $4$ 行:$n_c$ 个整数,第 $i$ 个整数表示 $c_i$。

在 query_k 返回后,评测系统将输出你的答案以及 get_a, get_b, get_c 三个函数的总调用次数。

样例一

input

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

output

3 6

explanation

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

样例二

见样例及测评库下载。

限制与约定

共 $10$ 个测试点,每个测试点 $10$ 分。设你的程序 get_a, get_b, get_c 函数的调用次数为 $t$。当 $t \leq 100$ 时得 $10$ 分,否则当 $t \leq 2000$ 时得 $6$ 分,否则不得分。

测试点编号 特殊限制
1$n_a, n_b, n_c \leq 30$
2$n_c = 0$
3
4
5
6
7
8
9
10

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

交互式类型的题目怎么本地测试

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

空间限制:$256\texttt{MB}$

下载

样例及测评库下载