← 返回题目列表

Codeforces · 1983/C

C. 鱼与熊掌兼得

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

Alice、Bob 和 Charlie 想分享一个切成 $$$n$$$ 块的矩形蛋糕。每个人认为每件作品都有不同的价值。 Alice 认为第 $$$i$$$ 块有价值 $$$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,\ldots,r_a]$$$、$$$[l_b,\ldots, r_b]$$$ 和 $$$[l_c,\ldots, 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$$$ 索引)。

示例

输入 #1

10
5
5 1 1 1 1
1 1 5 1 1
1 1 1 1 5
6
1 2 3 4 5 6
5 6 1 2 3 4
3 4 5 6 1 2
4
4 4 4 4
4 4 4 4
4 4 4 4
5
5 10 5 2 10
9 6 9 7 1
10 7 10 2 3
3
4 5 2
6 1 4
1 8 2
3
10 4 10
8 7 9
10 4 10
7
57113 65383 19795 53580 74452 3879 23255
12917 16782 89147 93107 27365 15044 43095
33518 63581 33565 34112 46774 44151 41756
6
6 3 1 8 7 1
10 2 6 2 2 4
10 9 2 1 2 2
5
5 5 4 5 5
1 6 3 8 6
2 4 1 9 8
10
1 1 1 1 1001 1 1 1001 1 1
1 1 1 1 1 1 2001 1 1 1
1 1 1 1 1 1001 1 1 1 1001

输出 #1

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

注意

在第一个测试用例中,三个数组中任意一个的总和为 $$$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$$$。每个人都有自己独立的一块蛋糕,没有一块蛋糕是两个或更多人共同的。

可以看出,对于第三个测试用例,不可能以满足给定约束的方式给出蛋糕切片。