CF1814C Search in Parallel

假设你有 $n$ 个盒子，第 $i$ 个盒子中有无限多个颜色为 $i$ 的球。有时候你需要取出某种特定颜色的球，但你太懒了，不想自己动手。 你买了两个机器人来帮你取球。现在你需要为它们编程。你需要构造两个列表 $[a_1, a_2, \dots, a_k]$ 和 $[b_1, b_2, \dots, b_{n-k}]$，其中列表 $a$ 表示分配给第一个机器人的盒子，列表 $b$ 表示分配给第二个机器人的盒子。每个整数 $1$ 到 $n$ 必须且仅能出现在其中一个列表中。 当你请求颜色为 $x$ 的球时，两个机器人按如下方式工作：每个机器人会按照列表中的顺序依次检查分配给自己的盒子。第一个机器人检查一个盒子需要 $s_1$ 秒，第二个机器人需要 $s_2$ 秒。当某个机器人找到包含颜色 $x$ 的盒子（并完成检查）时，搜索立即结束。搜索时间是从开始到某个机器人完成检查第 $x$ 个盒子的时间。如果某个机器人检查完了分配给自己的所有盒子还没找到目标盒子，则该机器人停止搜索。 例如，假设 $s_1 = 2$，$s_2 = 3$，$a = [4, 1, 5, 3, 7]$，$b = [2, 6]$。如果你请求颜色为 $3$ 的球，过程如下： - 一开始，第一个机器人开始检查盒子 $4$，第二个机器人开始检查盒子 $2$； - 第 $2$ 秒结束时，第一个机器人检查完盒子 $4$。不是目标盒子，继续检查盒子 $1$； - 第 $3$ 秒结束时，第二个机器人检查完盒子 $2$。不是目标盒子，继续检查盒子 $6$； - 第 $4$ 秒结束时，第一个机器人检查完盒子 $1$。不是目标盒子，继续检查盒子 $5$； - 第 $6$ 秒结束时，第一个机器人检查完盒子 $5$。不是目标盒子，继续检查盒子 $3$。同时，第二个机器人检查完盒子 $6$。不是目标盒子，且已检查完所有分配的盒子，于是停止搜索； - 第 $8$ 秒结束时，第一个机器人检查完盒子 $3$。这就是目标盒子，搜索结束； - 所以，搜索时间为 $8$ 秒。 你知道你会请求颜色为 $1$ 的球 $r_1$ 次，颜色为 $2$ 的球 $r_2$ 次，依此类推。你希望为机器人构造列表 $a$ 和 $b$，使得所有请求的总搜索时间尽可能小。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例数量。 每个测试用例包含两行： - 第一行包含三个整数 $n$、$s_1$、$s_2$（$2 \le n \le 2 \cdot 10^5$；$1 \le s_1, s_2 \le 10$）； - 第二行包含 $n$ 个整数 $r_1, r_2, \dots, r_n$（$1 \le r_i \le 10^6$）。 输入额外保证：所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出两行。第一行输出列表 $a$，第二行输出列表 $b$。每个列表的输出格式为：先输出元素个数，然后输出所有元素。 如果有多组答案，输出任意一组均可。

由 ChatGPT 4.1 翻译