← 返回题目列表

Codeforces · 1342/D

D. 多个测试用例

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

所以您决定在 Codeforces 上举办一场竞赛。您准备了问题:陈述、解决方案、检查器、验证器、测试...突然,您的协调员要求您将所有测试更改为最简单问题中的多个测试用例!

最初,该问题中的每个测试只是一个数组。数组的最大大小为 $$$k$$$。为简单起见,数组的内容并不重要。您有 $$$n$$$ 测试 - 第 $$$i$$$ 个测试是大小为 $$$m_i$$$ 的数组 ($$$1 \le m_i \le k$$$)。

您的协调员要求您将所有数组分配到多个测试用例中。每个测试用例可以包含多个数组。但是,每个测试用例应包含不超过 $$$c_1$$$ 大小大于或等于 $$$1$$$ ($$$\ge 1$$$) 的数组,不超过 $$$c_2$$$ 大小大于或等于 $$$2$$$、$$$\dots$$$ 的数组,不超过 $$$c_k$$$ 大小大于或等于 $$$k$$$ 的数组。另外,$$$c_1 \ge c_2 \ge \dots \ge c_k$$$。

所以现在您的目标是以以下方式创建新的测试用例:

- 每个初始数组都出现在一个测试用例中;
- 对于每个测试用例,给定的条件都成立;
- 测试用例的数量尽可能少。

打印您可以实现的最小可能数量的测试用例以及每个测试用例中包含的数组的大小。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n, k \le 2 \cdot 10^5$$$) - 初始测试的数量和每个数组的大小限制。

第二行包含 $$$n$$$ 整数 $$$m_1, m_2, \dots, m_n$$$ ($$$1 \le m_i \le k$$$) - 原始测试中数组的大小。

第三行包含 $$$k$$$ 整数 $$$c_1, c_2, \dots, c_k$$$ ($$$n \ge c_1 \ge c_2 \ge \dots \ge c_k \ge 1$$$); $$$c_i$$$ 是单个测试用例中可以拥有的大小大于或等于 $$$i$$$ 的数组的最大数量。

输出

在第一行中打印一个整数 $$$ans$$$ ($$$1 \le ans \le n$$$) — 您可以实现的最小测试用例数。

接下来的 $$$ans$$$ 行应包含以下格式的测试用例的描述:

$$$t$$$ $$$a_1$$$ $$$a_2$$$ $$$\dots$$$ $$$a_{t}$$$ ($$$1 \le t\le n$$$) - 测试用例包含 $$$t$$$ 数组,$$$a_i$$$ 是该测试用例中第 $$$i$$$ 个数组的大小。

每个初始数组应该恰好出现在一个测试用例中。特别是,它意味着所有 $$$ans$$$ 测试用例的 $$$t$$$ 总和应等于 $$$n$$$。

请注意,由于 $$$c_k \ge 1$$$ (因此 $$$c_1 \ge 1$$$),答案始终存在。

如果有多个答案,则可以输出其中任意一个。

示例

输入 #1

4 3
1 2 2 3
4 1 1

输出 #1

3
1 2
2 1 3
1 2

输入 #2

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

输出 #2

2
3 8 5 7
3 10 8 1

输入 #3

5 1
1 1 1 1 1
5

输出 #3

1
5 1 1 1 1 1

输入#4

5 1
1 1 1 1 1
1

输出#4

5
1 1
1 1
1 1
1 1
1 1

注意

在第一个示例中,无法将测试分配到少于 $$$3$$$ 的测试用例中。给定的答案满足条件:每个测试用例包含不超过 $$$4$$$ 大小大于或等于 $$$1$$$ 的数组,不超过 $$$1$$$ 大小大于或等于 $$$2$$$ 和 $$$3$$$ 的数组。

请注意,此测试有多个有效答案。例如,大小为 $$$[[2], [1, 2], [3]]$$$ 的测试用例也是正确的。

但是,大小为 $$$[[1, 2], [2, 3]]$$$ 的测试用例将是不正确的,因为第二个测试用例中存在大小大于或等于 $$$2$$$ 的 $$$2$$$ 数组。

请注意第三个示例和第四个示例之间的区别。在第三个示例中,您最多可以包含 $$$5$$$ 大小大于或等于 $$$1$$$ 的数组,因此您可以将所有数组放入单个测试用例中。在第四个示例中,最多只能有 $$$1$$$ 数组。因此,每个数组都应该包含在单独的测试用例中。