← 返回题目列表

Codeforces · 439/C

C. Devu 和数组的分区

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

Devu是个小孩子,很喜欢玩,但他只喜欢玩数组。在玩的时候他提出了一个他无法解决的有趣问题,你能帮他解决一下吗?

给定一个由不同整数组成的数组。是否可以将整个数组划分为 k 个不相交的非空部分,使得其中 p 个部分的和为偶数(每个部分的和必须为偶数),而剩余的 k - p 的和为奇数? (请注意,各部分不必是连续的)。

如果可以对数组进行分区,还请给出任何可能的有效分区方式。

输入

第一行将包含三个空格分隔的整数 n、k、p (1 ≤ k ≤ n ≤ 105;0 ≤ p ≤ k)。下一行将包含 n 个以空格分隔的不同整数,表示数组 a 的内容:a1, a2, ..., an (1 ≤ ai ≤ 109)。

输出

如果可以按所需方式对数组进行分区,则在第一行打印“YES”(不带引号)。否则打印“NO”(不带引号)。

如果所需分区存在,则在第一行后打印 k 行。其中第 i 个应该包含第 i 部分的内容。按以下方式打印该行中该部分的内容:首先打印该部分的元素数量,然后以任意顺序打印该部分的所有元素。必须恰好有 p 个部分的和为偶数,其余 k - p 个部分的每一个必须为奇数和。

由于可以有多个分区,因此您可以打印任何有效的分区。

示例

输入 #1

5 5 3
2 6 10 5 9

输出 #1

YES
1 9
1 5
1 10
1 6
1 2

输入 #2

5 5 3
7 14 2 9 5

输出 #2

NO

输入 #3

5 3 1
1 2 3 7 5

输出 #3

YES
3 5 1 3
1 7
1 2