CF1250G Discarding Game

Eulampius 设计了一个游戏，规则如下： - 游戏有两名玩家：一个人类和一台电脑； - 游戏最多进行 $n$ 轮。初始时两位玩家的分数均为 $0$。在第 $j$ 轮，人类获得 $a_j$ 分，电脑获得 $b_j$ 分。两者得分是同时进行的； - 当任意一名玩家的分数达到或超过 $k$ 时，游戏立即结束，该玩家判负。如果两位玩家同时分数达到或超过 $k$，则两人都判负； - 如果 $n$ 轮结束后，两位玩家的分数都小于 $k$，则游戏以平局结束； - 每轮结束后，人类可以按下“重置”按钮。如果此时人类有 $x$ 分，电脑有 $y$ 分（当然 $x < k$ 且 $y < k$），按下按钮后，人类的分数变为 $x' = \max(0,\, x - y)$，电脑的分数变为 $y' = \max(0,\, y - x)$。例如，状态 $(x=3,\, y=5)$ 经过重置后变为 $(x'=0,\, y'=2)$，状态 $(x=8,\, y=2)$ 经过重置后变为 $(x'=6,\, y'=0)$。 Eulampius 让他的朋友 Polycarpus 测试这个游戏。Polycarpus 很快发现，每一轮人类和电脑获得的分数在游戏开始前就已经生成并存储在文件中。换句话说，按下“重置”按钮不会影响 $a_j$ 和 $b_j$ 的值，因此序列 $a$ 和 $b$ 是固定且已知的。 Polycarpus 想为游戏制定一个计划。他希望通过尽可能少地按“重置”按钮来赢得游戏。你的任务是确定最少需要按多少次“重置”按钮才能获胜，或者判断 Polycarpus 无法获胜。

输入的第一行包含一个整数 $t$（$1 \le t \le 10000$），表示测试用例的数量。接下来是 $t$ 个测试用例。 每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 2 \cdot 10^5$，$2 \le k \le 10^9$），分别表示游戏的最大轮数和达到该分数即判负的分数。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_j < k$），表示人类在第 $j$ 轮获得的分数。 第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$（$1 \le b_j < k$），表示电脑在第 $j$ 轮获得的分数。 所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

按输入顺序输出每个测试用例的答案。 如果 Polycarpus 无法获胜，则输出一行“-1”（不带引号）。在这种情况下，不要为该测试用例输出其他内容。否则，第一行输出一个整数 $d$，表示获胜所需的最小“重置”按钮次数。第二行输出 $d$ 个不同的整数 $r_1, r_2, \dots, r_d$（$1 \le r_i < n$），表示需要在第 $r_i$ 轮结束后按下“重置”按钮，顺序任意。如果 $d=0$，可以将第二行留空，或者直接不输出第二行。 如果有多种方案，输出任意一种即可。

在第二个测试用例中，如果人类在第二轮和第四轮结束后按下“重置”按钮，游戏过程如下： 1. 第一轮后，人类有 $5$ 分，电脑有 $4$ 分； 2. 第二轮后，人类有 $7$ 分，电脑有 $10$ 分； 3. 人类按下“重置”按钮，此时人类分数变为 $0$，电脑分数变为 $3$； 4. 第三轮后，人类有 $8$ 分，电脑有 $6$ 分； 5. 第四轮后，人类有 $10$ 分，电脑有 $9$ 分； 6. 人类再次按下“重置”按钮，此时人类分数为 $1$，电脑分数为 $0$； 7. 第五轮后，人类有 $5$ 分，电脑有 $5$ 分； 8. 第六轮后，人类有 $11$ 分，电脑有 $6$ 分； 9. 第七轮后，人类有 $12$ 分，电脑有 $13$ 分； 10. 第八轮后，人类有 $14$ 分，电脑有 $17$ 分； 11. 人类获胜，因为电脑分数达到或超过 $k$，而人类分数严格小于 $k$。 由 ChatGPT 4.1 翻译