CF1983C Have Your Cake and Eat It Too

Alice、Bob 和 Charlie 想要分享一个被切成 $n$ 块的矩形蛋糕。每个人对每一块蛋糕的价值评估都不同。第 $i$ 块蛋糕对 Alice 的价值为 $a_i$，对 Bob 的价值为 $b_i$，对 Charlie 的价值为 $c_i$。 所有 $a_i$ 的和、所有 $b_i$ 的和以及所有 $c_i$ 的和都相等，记为 $tot$。 给定每个人对每块蛋糕的价值，你需要将蛋糕分给每个人一段连续的子区间。也就是说，分配给 Alice、Bob 和 Charlie 的子区间分别可以表示为 $(l_a, r_a)$、$(l_b, r_b)$ 和 $(l_c, r_c)$。分配需要满足以下约束： - 没有任何一块蛋糕被分配给多于一个人，即 $[l_a, r_a]$、$[l_b, r_b]$ 和 $[l_c, r_c]$ 这三个区间两两不相交。 - $\sum_{i = l_a}^{r_a} a_i, \sum_{i = l_b}^{r_b} b_i, \sum_{i = l_c}^{r_c} c_i \geq \lceil \frac{tot}{3} \rceil$。 这里，$\lceil \frac{a}{b} \rceil$ 表示向上取整除法，即不小于 $a/b$ 的最小整数。例如，$\lceil \frac{10}{3} \rceil = 4$，$\lceil \frac{15}{3} \rceil = 5$。

第一行包含一个整数 $t$，表示测试用例数量，$1 \le t \le 10^4$。 对于每个测试用例： 第一行包含一个整数 $n$，$3 \le n \le 2 \cdot 10^5$。 接下来的三行每行包含 $n$ 个整数： 一行 $n$ 个整数 $a_1, a_2, \ldots, a_n$，表示 Alice 对每块蛋糕的价值（$1 \le a_i \le 10^6$）。 一行 $n$ 个整数 $b_1, b_2, \ldots, b_n$，表示 Bob 对每块蛋糕的价值（$1 \le b_i \le 10^6$）。 一行 $n$ 个整数 $c_1, c_2, \ldots, c_n$，表示 Charlie 对每块蛋糕的价值（$1 \le c_i \le 10^6$）。 保证 $\sum_{i = 1}^{n} a_i = \sum_{i = 1}^{n} b_i = \sum_{i = 1}^{n} c_i$。 所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，如果无法满足条件，输出 $-1$。 否则，输出六个数——$l_a, r_a, l_b, r_b, l_c, r_c$，分别表示 Alice、Bob 和 Charlie 所获得子区间的起始和结束下标（下标从 $1$ 开始）。

在第一个测试用例中，三组数组的总和都是 $9$。每个人需要获得一段总价值至少为 $\lceil \frac{9}{3} \rceil = 3$ 的蛋糕。 如果将区间 $(1, 1)$ 分配给 Alice，其总价值为 $5$，满足 $\ge 3$；将区间 $(2, 3)$ 分配给 Bob，其总价值为 $1 + 5 = 6$，满足 $\ge 3$；将区间 $(4, 5)$ 分配给 Charlie，其总价值为 $1 + 5 = 6$，也满足 $\ge 3$。每个人获得的蛋糕区间互不重叠，没有任何一块蛋糕被分配给多于一个人。 可以证明，对于第三个测试用例，无法满足题目要求的分配方式。 由 ChatGPT 4.1 翻译