CF1446A Knapsack

你有一个容量为 $W$ 的背包。现在有 $n$ 个物品，第 $i$ 个物品的重量为 $w_i$。 你希望选择一些物品放入背包，使得它们的总重量 $C$ 至少为背包容量的一半，但（显然）不能超过背包容量。形式化地，$C$ 需要满足：$\lceil \frac{W}{2}\rceil \le C \le W$。 请输出你选择放入背包的物品的编号列表，或者判断无法满足条件。 如果存在多种满足条件的物品列表，你可以输出任意一种。注意，你不需要使背包内物品的总重量最大化。

每组测试数据包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 10^4$）。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $W$（$1 \le n \le 200\,000$，$1 \le W \le 10^{18}$）。 每个测试用例的第二行包含 $n$ 个整数 $w_1, w_2, \dots, w_n$（$1 \le w_i \le 10^9$），表示每个物品的重量。 所有测试用例中 $n$ 的总和不超过 $200\,000$。

对于每个测试用例，如果无解，输出一行 $-1$。 如果存在由 $m$ 个物品组成的解，第一行输出 $m$，第二行输出 $m$ 个整数 $j_1, j_2, \dots, j_m$（$1 \le j_i \le n$，所有 $j_i$ 互不相同），表示你选择放入背包的物品编号。 如果存在多种满足条件的物品列表，你可以输出任意一种。注意，你不需要使背包内物品的总重量最大化。

在第一个测试用例中，你可以选择重量为 $3$ 的物品，正好装满背包。 在第二个测试用例中，所有物品的重量都大于背包容量，因此答案为 $-1$。 在第三个测试用例中，你正好装满背包的一半。 由 ChatGPT 4.1 翻译