← 返回题目列表

Codeforces · 1276/C

C. 美丽的矩形

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

给你 $$$n$$$ 个整数。您需要选择一个子集并将所选数字放入一个漂亮的矩形(矩形矩阵)中。每个选定的数字应占据其矩形单元格之一,每个单元格必须恰好填充一个选定的数字。某些 $$$n$$$ 数字可能不会被选择。

如果一个矩形(矩形矩阵)的每一行和每一列的所有值都不同,则该矩形(矩形矩阵)被称为漂亮矩形。

你能构造的最大(按单元格总数计算)的漂亮矩形是多少?打印矩形本身。

输入

第一行包含 $$$n$$$ ($$$1 \le n \le 4\cdot10^5$$$)。第二行包含 $$$n$$$ 整数 ($$$1 \le a_i \le 10^9$$$)。

输出

在第一行打印 $$$x$$$ ($$$1 \le x \le n$$$) — 所需最大漂亮矩形的单元格总数。在第二行中打印 $$$p$$$ 和 $$$q$$$ ($$$p \cdot q=x$$$):其大小。在接下来的 $$$p$$$ 行中打印所需的矩形本身。如果有多个答案,请打印其中一个。

示例

输入 #1

12
3 1 4 1 5 9 2 6 5 3 5 8

输出 #1

12
3 4
1 2 3 5
3 1 5 4
5 6 8 9

输入 #2

5
1 1 1 1 1

输出 #2

1
1 1
1