306949: CF1276C. Beautiful Rectangle

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Beautiful Rectangle

题意翻译

我们称一个矩阵是美丽的,当且仅当该这矩阵中不存在两个相同的数在同一列或在同一行。 给定 $n$ 个数,要求你选出尽量多的数,使它们能够组成一个美丽的矩形。 注意,本题要求**输出选出的数的个数与组成矩形大小和具体方案**。

题目描述

You are given $ n $ integers. You need to choose a subset and put the chosen numbers in a beautiful rectangle (rectangular matrix). Each chosen number should occupy one of its rectangle cells, each cell must be filled with exactly one chosen number. Some of the $ n $ numbers may not be chosen. A rectangle (rectangular matrix) is called beautiful if in each row and in each column all values are different. What is the largest (by the total number of cells) beautiful rectangle you can construct? Print the rectangle itself.

输入输出格式

输入格式


The first line contains $ n $ ( $ 1 \le n \le 4\cdot10^5 $ ). The second line contains $ n $ integers ( $ 1 \le a_i \le 10^9 $ ).

输出格式


In the first line print $ x $ ( $ 1 \le x \le n $ ) — the total number of cells of the required maximum beautiful rectangle. In the second line print $ p $ and $ q $ ( $ p \cdot q=x $ ): its sizes. In the next $ p $ lines print the required rectangle itself. If there are several answers, print any.

输入输出样例

输入样例 #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

Input

题意翻译

我们称一个矩阵是美丽的,当且仅当该这矩阵中不存在两个相同的数在同一列或在同一行。 给定 $n$ 个数,要求你选出尽量多的数,使它们能够组成一个美丽的矩形。 注意,本题要求**输出选出的数的个数与组成矩形大小和具体方案**。

加入题单

上一题 下一题 算法标签: