P15848 [NOISG 2026 Finals] 饿猫 / Famished Cats【暂无数据】

在一年一度的全国爱猫日庆祝活动中成功阻止了猫的灭绝后，猫 Ket 现在收到了来自食猫王国的饥饿投诉。因此，Ket 被委派去运送食物，以防止它们再次诉诸同类相食。 这个猫王国可以被建模为一条从西向东延伸的漫长道路。道路的西端有一个食物银行。食物银行以东有 $n$ 间猫屋，编号从 $1$ 到 $n$。保证 $n$ 是 **偶数**。第一间房子位于食物银行以东 $d[1]$ 公里处。对于 $i \geq 2$，第 $i$ 间房子位于第 $(i - 1)$ 间房子以东 $d[i]$ 公里处。 Ket 将驾驶一辆送货车向这些房子运送食物。卡车从食物银行出发，初始拥有 $x$ 单位的燃料。1 单位燃料允许 Ket 驾驶他的卡车沿道路行驶 1 公里。 第 $i$ 间房子有 $f[i]$ 单位的燃料可供卡车使用。卡车拥有无限的燃料存储空间，并且只在燃料耗尽时才会停下。卡车离开后无需返回食物银行。 :::align{center}  ::: 此外，Ket 拥有一根魔杖。挥动一次魔杖，他可以 **交换** 第 $i$ 间和第 $(n - i + 1)$ 间猫屋中储存的燃料量。只有当两个房子中的燃料都尚未被使用时，才能进行此交换。请帮助 Ket 找到他使用任意次数交换后能够到达的最远房子的索引 $D$。同时，请帮助 Ket 找到到达房子 $D$ 所需的最小交换次数 $S$。 你可以参考样例测试 #1 以获得更详细的解释。

你的程序需要从标准输入读取数据。 输入的第一行包含两个由空格分隔的整数 $n$ 和 $x$。 输入的第二行包含 $n$ 个由空格分隔的整数 $d[1], d[2], \dots, d[n]$。 输入的第三行包含 $n$ 个由空格分隔的整数 $f[1], f[2], \dots, f[n]$。

你的程序需要向标准输出写入数据。 在一行中输出 **两个** 由空格分隔的整数。第一个整数应为 $D$，即 Ket 能到达的最远房子的索引，接着是 $S$，即到达房子 $D$ 所需的最小交换次数。

### 样例测试 #1 解释 :::align{center}  ::: 有一个食物银行，其东边有 $n = 6$ 间房子。Ket 的卡车以 $x = 1$ 单位燃料出发，行驶到房子 $1$。然后他在房子 $1$ 补充燃料，并行驶到房子 $2$。此时，Ket 最优的做法是使用他的魔杖交换房子 $2$ 和房子 $5$ 的燃料量，这使他能够补充 $3$ 单位燃料并到达房子 $3$。随后，他可以在前往接下来两间房子的途中补充 $1$ 单位燃料，并分别在房子 $4$ 和房子 $5$（由于之前的交换）补充 $4$ 单位和 $1$ 单位燃料。 之后他将剩下 $4$ 单位燃料，这使他无法前往房子 $6$，因为那需要 $6$ 单位燃料。由于 Ket 在到达房子 $6$ 之前耗尽了燃料，他只能到达房子 $5$。此外，他必须使用魔杖进行一次交换。因此，$D = 5$ 且 $S = 1$。 ### 子任务 对于所有测试用例，输入数据满足以下限制： - $2 \leq n \leq 500\,000$ - $n$ 是偶数。 - 对于所有 $1 \leq i \leq n$，有 $1 \leq d[i] \leq 10^9$ - 对于所有 $1 \leq i \leq n$，有 $1 \leq f[i] \leq 10^9$ - $d[1] \leq x \leq 10^9$ 你的程序将在满足以下限制的输入实例上进行测试： | 子任务 | 分数 | 额外约束条件 | |:-:|:-:|:-:| | 0 | 0 | 样例测试用例 | | 1 | 7 | 对于所有 $1 \leq i \leq n$，$\vert f[i] - f[n - i + 1] \vert = k$ 对于某个常数 $k$ 成立 | | 2 | 12 | $n \leq 40$ | | 3 | 14 | $f$ 是非递减的（对于所有 $1 \leq i \leq n - 1$，有 $f[i] \leq f[i + 1]$） | | 4 | 19 | $D \leq \frac{n}{2}$ | | 5 | 21 | $n \leq 5000$ | | 6 | 27 | 无额外约束 | 注意：一个数 $x$ 的绝对值，记作 $\vert x \vert$，是 $0$ 与 $x$ 在数轴上的距离的非负数。例如，$\vert 5 \vert = 5$ 且 $\vert -5 \vert = 5$。 翻译由 DeepSeek V3.2 完成