← 返回题目列表

Codeforces · 353/B

B. 两堆

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

Valera有2·n个立方体,每个立方体包含一个从10到99的整数。他任意选择n个立方体并将它们放入第一个堆中。剩余的立方体形成第二堆。

瓦莱拉决定玩立方体。在游戏过程中,他从第一堆中取出一个立方体并写下它的数字。然后,他从第二堆中取出一个立方体,并在他所写的两个数字附近(在它们的右侧)写下它的两个数字。最后他得到了一个四位数的整数——它的前两位数字写在第一堆的立方体上,后两位数字写在第二堆的第二个立方体上。

Valera 非常了解算术。因此,他可以轻松地数出他在游戏中可以获得的不同四位数字的数量。另一个问题是:如何将立方体分成两个堆,以使这个数字(Valera 可以获得的不同四位整数的数量)尽可能大?

输入

第一行包含整数 n (1 ≤ n ≤ 100)。第二行包含 2·n 个空格分隔的整数 ai (10 ≤ ai ≤ 99),表示立方体上的数字。

输出

在第一行打印一个数字——Valera 可以获得的不同四位数的最大可能数量。在第二行中打印 2·n 个数字 bi (1 ≤ bi ≤ 2)。这些数字的意思是:第 i 个立方体属于您除法中的第 bi 堆。

如果有多种将多维数据集拆分为堆的最佳方法,请打印其中任何一个。

示例

输入 #1

1
10 99

输出 #1

1
2 1

输入 #2

2
13 24 13 45

输出 #2

4
1 2 2 1

注意

在第一个测试用例中,Valera 可以将第一个立方体放入第一个堆中,将第二个立方体放入第二个堆中。在这种情况下,他获得数字 1099。如果他将第二个立方体放入第一个堆,并将第一个立方体放入第二个堆,那么他可以获得数字 9910。在这两种情况下,不同整数的最大数量都等于 1。

在第二个测试用例中,Valera 可以获得数字 1313、1345、2413、2445。注意,如果他将第一个和第三个立方体放入第一个堆中,他只能获得两个数字 1324 和 1345。