#5729. 「NOISG 2026 Final」Famished Cats

标签: 传统 | 时间限制: 1000 ms | 内存限制: 1024 MiB |

题目描述

译自 NOISG 2026 Final T2. Famished Cats

在年度全国猫咪日（NCD）庆典期间成功防止猫咪灭绝后，猫咪 Ket 现在收到了来自同类相食猫王国的饥饿投诉。因此，Ket 被指派去运送食物，以防止它们再次诉诸同类相食。

这个猫王国可以建模为一条由西向东延伸的长路。道路的西端有一个食品库。食品库以东有 $n$ 座猫舍，编号从 $1$ 到 $n$。保证 $n$ 是偶数。第一座猫舍位于食品库以东 $d[1]$ 公里处。对于 $i \geq 2$，第 $i$ 座猫舍位于第 $(i-1)$ 座猫舍以东 $d[i]$ 公里处。

Ket 将驾驶一辆运货卡车向这些猫舍运送食物。卡车从食品库出发，初始拥有 $x$ 单位燃油。$1$ 单位燃油可以让 Ket 的卡车沿路行驶 $1$ 公里。

第 $i$ 座猫舍备有 $f[i]$ 单位燃油供卡车使用。卡车拥有无限的燃油储存能力，且仅在燃油耗尽时才会停止。卡车出发后不需要返回食品库。

此外，Ket 有一根魔法棒。挥动一次魔法棒，他可以交换第 $i$ 座和第 $(n-i+1)$ 座猫舍中储存的燃油量。只有当两座猫舍的燃油都尚未被使用时，这种交换才能进行。请帮助 Ket 找到在可以使用任意次数交换的前提下，他能到达的最远猫舍索引 $D$。同时，请帮助 Ket 找到到达猫舍 $D$ 所需的最少交换次数 $S$。

有关详细解释，请参考样例 1。

输入格式

你的程序必须从标准输入读取数据。

第一行包含两个由空格分隔的整数 $n$ 和 $x$。

第二行包含 $n$ 个由空格分隔的整数 $d[1], d[2], \ldots, d[n]$。

第三行包含 $n$ 个由空格分隔的整数 $f[1], f[2], \ldots, f[n]$。

输出格式

你的程序必须输出到标准输出。

在单行中输出两个由空格分隔的整数。第一个整数应为 $D$，即 Ket 能到达的最远猫舍索引，随后是 $S$，即到达猫舍 $D$ 所需的最少交换次数。

样例 1

输入

6 1
1 1 3 1 1 6
1 1 1 4 3 2

输出

5 1

有一个食品库，其东边有 $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,5$ 和 $6$ 的限制。

样例 2

输入

6 5
3 8 3 1 4 1
2 7 1 6 2 7

输出

6 1

此样例满足子任务 $1,2,5$ 和 $6$ 的限制。

样例 3

输入

6 2
2 24 25 40 5 11
4 12 14 16 20 30

输出

3 2

此样例满足子任务 $2,3,4,5$ 和 $6$ 的限制。

样例 4

输入

6 10
3 6 3 7 8 6
4 3 1 7 1 6

输出

5 1

此样例满足子任务 $2,5$ 和 $6$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $2 \leq n \leq 500000$
• $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$

详细子任务附加限制及分值如下表所示：

子任务	分值	附加限制
$1$	$7$	对于所有 $1 \leq i \leq n$，$
$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$ 的绝对值（记作 $|x|$）是指在数轴上 $0$ 到 $x$ 之间的距离，为一个非负数。例如，$|5|=5$ 且 $|-5|=5$。