注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 11 及以上）

请在提交源代码前添加 #include "molecules.h"。

题目描述

彼得在一家公司工作，这家公司已经制造了一台检测分子的机器。每个分子的重量都是正整数。这台机器的 检测范围 是 $[l, u]$ ，这里 $l$ 和 $u$ 都是正整数。这台机器能够检测一个分子集合当且仅当这个集合包含了一个子集，这个子集中的分子的总重量属于机器的检测范围。

考虑 $n$ 个分子，重量记为 $w_{0}, \ldots, w_{n-1}$ 。 如果存在一个下标的集合（并且该集合中的下标都不相同）$I=\left\{i_{1}, \ldots, i_{m}\right\}$ 使得 $l \leq w_{i_{1}}+\ldots w_{i_{m}} \leq u$ ，那么检测就会成功。

由于机器的细节，$l$ 和 $u$ 之间的差距保证会大于等于最重分子和最轻分子之间的差距，即， $u-l \geq w_{\text {max }}-w_{\text {min }}$ ，其中 $w_{\text {max }}=\max \left(w_{0}, \ldots, w_{n-1}\right)$ ， $w_{\text {min }}=\min \left(w_{0}, \ldots, w_{n-1}\right)$。

你的任务是写一个程序，该程序能找到一个子集，使得该子集的总重量属于检测范围，或者判定没有这样的子集存在。

实现细节

你应该实现一个函数（方法）：

• int[] solve(int l, int u, int[] w)
  • l 和 u：分别表示检测范围的两个端点，
  • w：分子的重量．
  • 如果存在符合要求的子集，该函数应该返回一个数组，数组中的元素代表符合要求的子集中的分子的下标。如果存在多个正确答案，返回任何一个子集即可。
  • 如果不存在符合要求的子集，该函数应该返回一个空数组。

对于 C 语言，函数参数稍微不同：

• int solve(int l, int u, int[] w, int n, int[] result)
  • n：数组 w 中元素的个数（即分子的个数），
  • 其他参数同上，
  • 该函数将这些下标写入数组 result 的前 $m$ 个元素当中，然后返回 $m$ ，这和刚才描述的前一个函数（返回一个数组包含 $m$ 个下标）的做法不同，
  • 如果符合要求的子集不存在，该函数不应该写入任何信息到数组 result 中，而且返回 $0$。

你的程序可以将分子的下标以任何顺序写入返回的数组中（或者 C 语言中的数组 result）。

请使用提供的模板文件，参考关于你所使用的编程语言的实现细节。

样例 1

solve(15, 17, [6, 8, 8, 7])

这个例子当中，我们有四个分子，重量分别是 $6,8,8$ 和 $7$。这台机器可以检测子集总重量在 $15$ 到 $17$ 之间（包含 $15$ 和 $17$）的子集。注意， $17-15 \geq 8-6$ 。分子 $1$ 和分子 $3$ 的重量之和为 $w_{1}+w_{3}=8+7=15$ ，所以这个函数应该返回 [1, 3]。其他可能正确的答案有 [1, 2]（$w_{1}+w_{2}=8+8=16$）和 [2, 3]（$w_{2}+w_{3}=8+7=15$）。

样例 2

solve(14, 15, [5, 5, 6, 6])

这个例子当中，我们有四个分子，重量分别为 $5,5,6$ 和 $6$，我们要寻找一个子集，其总重量介于 $14$ 和 $15$ 之间（包含 $14$ 和 $15$）。请注意， $15-14 \geq 6-5$ 。因为不存在总重量介于 $14$ 和 $15$ 之间的子集，所以该函数返回空数组。

样例 3

solve(10, 20, [15, 17, 16, 18])

这个例子当中，我们有四个分子，重量分别为 $15,17,16$ 和 $18$，而且我们要寻找一个子集，其总重量介于 $10$ 和 $20$ 之间（包含 $10$ 和 $20$）。请注意， $20-10 \geq 18-15$ 。任何只包含一个元素的子集，其重量都在 $10$ 和 $20$ 之间，所以可能正确的答案有 [0], [1], [2] 和 [3]。

子任务

1. （9 分）： $1 \leq n \leq 100,1 \leq w_{i} \leq 100,1 \leq u, l \leq 1000$ ，所有 $w_{i}$ 都相等。
2. （10 分）： $1 \leq n \leq 100,1 \leq w_{i}, u, l \leq 1000$ ，而且 $\max \left(w_{0}, \ldots, w_{n-1}\right)-\min \left(w_{0}, \ldots, w_{n-1}\right) \leq 1$。
3. （12 分）： $1 \leq n \leq 100$ 而且 $1 \leq w_{i}, u, l \leq 1000$。
4. （15 分）： $1 \leq n \leq 10\,000$ 而且 $1 \leq w_{i}, u, l \leq 10\,000$。
5. （23 分）： $1 \leq n \leq 10\,000$ 而且 $1 \leq w_{i}, u, l \leq 500\,000$。
6. （31 分）： $1 \leq n \leq 200\,000$ 而且 $1 \leq w_{i}, u, l<2^{31}$。

样例测试程序

样例测评程序按照以下格式读入输入：

• 第一行：整数 $n, l, u$ 。
• 第二行：$n$ 个整数：$w_{0}, \ldots, w_{n-1}$ 。