← 返回题目列表

Codeforces · 1446/A

A. 背包

中文机器翻译题面 查看原题

你有一个背包,容量为$$$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$$$, ..., $$$j_m$$$ ($$$1 \le j_i \le n$$$,所有 $$$j_i$$$ 都是不同的)输出的 - 您想要装入背包的物品的索引。

如果有多个可能的满足条件的项目列表,则可以输出任何一个。请注意,您不必最大化背包中物品的重量总和。

示例

输入 #1

3
1 3
3
6 2
19 8 19 69 9 4
7 12
1 1 1 17 1 1 1

输出 #1

1
1
-1
6
1 2 3 5 6 7

注意

在第一个测试用例中,您可以取出重量为 $$$3$$$ 的物品并恰到好处地装满背包。

在第二个测试用例中,所有物品都大于背包的容量。因此,答案是$$$-1$$$。

在第三个测试用例中,您将背包正好装满了一半。