#P4934. 礼物

    ID: 3863 远端评测题 2000ms 500MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>Special JudgeO2优化枚举暴力排序拓扑排序洛谷月赛

礼物

题目背景

由于你出色的完成了前面两道题目,善良的 __stdcall 决定给你一个小礼物,给拼搏在 AK 这套题之路上的你,一个有力的援助。

题目描述

__stdcall 决定给你 nn 个礼物,每个礼物有一个魔力值 aia_i

这些礼物的魔力值都是独一无二的,两两互不相同。这些礼物都有着神奇的魔力,如果两个礼物 i,ji, j 的魔力值满足 aibitandajmin(ai,aj)a_i \operatorname{bitand} a_j \ge \min(a_i, a_j),那么这两个礼物的魔力将会相互抵消,因此它们不能放在一个箱子里。

这里的 bitand\operatorname{bitand} 表示按位与运算,如果你对这一运算不够了解,请参考:https://baike.baidu.com/item/按位与/9601818

作为发礼物苦力的 ljt12138 的箱子并不多,不过幸运的是,每个箱子都足够大。现在他请求你帮助他合理分配,用尽可能少的箱子装下所有礼物。换言之,使得每个礼物都被恰好装入一个箱子中,且同一个箱子中的礼物魔力不会相互抵消。如果有多种合法的方案,你只需要给出任意一种

ljt12138 十分善良,如果你只能求出所需要的箱子数,也可以获得该测试点 60%60\% 的分数,关于这一点,请参考下面的提示与说明。

输入格式

  • 第一行两个数 nnkknn 为礼物总数,kk 为一个参数,方便你进行计算。
  • 第二行 nn 个两两不同的数aia_i,满足 0ai<2k0\le a_i < 2^k,表示礼物的魔力值。

输出格式

  • 第一行输出一个数。如果你不希望输出方案,请输出0;如果你希望输出方案,请输出 11如果你在这一行输出了不符合要求的信息,将被判为 WA
  • 第二行一个数 mm,表示你将礼物装到了 mm 个箱子里。
  • 如果你在第一行输出了 11,接下来 mm 行,每行表示一个箱子:首先一个数 sis_i,表示当前箱子中礼物的个数;接下来 sis_i 个数,表示当前子集。
5 3
0 4 7 1 6 

1
4
1 0
2 1 4
1 6
1 7 

提示

附加样例

你可以在 https://pan.baidu.com/s/1A8_ZA4yXXi5y6771x9JKUw 下载附加样例。

关于输出方案

  • 如果你在第一行输出了 00,而正确回答了最小所需的箱子数,将获得测试点 60%60\% 的分数。
  • 如果你在第一行输出了 11,正确回答了最小所需的箱子数,但没有给出正确的方案,也将获得该测试点 60%60\% 的分数。
  • 如果你没有正确回答最小所需的箱子数,将不会获得该测试点的分数。
  • 请选手注意,如果你未按照上述格式输出答案,将无法获得任何分数。

数据 n,kn, k 的关系由下面的表格给出:

数据编号 nn kk
11 55 33
22 66
33 77 1010
44 88
55 1616 77
66 1717 88
77 99
88 2020
99 2×1032\times 10^3 1717
1010 2.5×1032.5\times 10^3 1818
1111 3×1033\times 10^3 1919
1212 2020
1313 2.5×1042.5\times 10^4 1515
1414
1515 5×1045\times 10^4 1616
1616
1717 2.5×1052.5\times 10^5 1818
1818 5×1055\times 10^5 1919
1919 10610^6 2020
2020