AT_agc068_b.[AGC068B] 01 Graph Construction

我们称仅由 0 和 1 组成的字符串对 $ (S,T) $ 满足以下所有条件时（且仅当满足时）为好字符串对：

• $ S,T $ 中包含的 0 的个数相等。
• $ S,T $ 中包含的 1 的个数相等。

特别地，对于好字符串对 $ (S,T) $，$ S,T $ 的长度相同。

对于好字符串对 $ (S,T) $，定义无向图 $ G(S,T) $ 如下：

• 设 $ S $ 的长度为 $ L $。构建一个包含顶点 $ 1,2,\cdots,L $ 的图 $ g $。
• 设 $ S $ 中 0 的个数为 $ n $。记 $ S $ 中 0 的下标为 $ 1\leq a_1<a_2<\cdots<a_n\leq L $，$ T $ 中 0 的下标为 $ 1\leq b_1<b_2<\cdots<b_n\leq L $。对于每个 $ 1\leq i\leq n $，在 $ g $ 中添加一条连接顶点 $ a_i $ 和 $ b_i $ 的边。
• 设 $ S $ 中 1 的个数为 $ m $。记 $ S $ 中 1 的下标为 $ 1\leq c_1<c_2<\cdots<c_m\leq L $，$ T $ 中 1 的下标为 $ 1\leq d_1<d_2<\cdots<d_m\leq L $。对于每个 $ 1\leq i\leq m $，在 $ g $ 中添加一条连接顶点 $ c_i $ 和 $ d_i $ 的边。
• 经过上述步骤得到的 $ g $ 即为 $ G(S,T) $。

给定一个长度为 $ N $ 的整数序列 $ A=(A_1,A_2,\cdots,A_N) $。请找到一个满足以下所有条件的好字符串对 $ (S,T) $：

• 设 $ S $ 的长度为 $ L $，满足 $ N\leq L\leq 10^5 $。
• 对于任意 $ 1\leq i,j\leq N $，当且仅当 $ G(S,T) $ 中顶点 $ i $ 和顶点 $ j $ 属于同一连通分量时，有 $ A_i=A_j $。

可以证明，在本题的限制下，解一定存在。

输入通过标准输入给出，格式如下：

$ N $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $

请输出如下格式的答案：

$ L $ $ S $ $ T $

其中，$ L $ 是 $ S,T $ 的长度。若有多个解，输出任意一个均可。

限制条件

• $ 1\leq N\leq 100 $
• $ 1\leq A_i\leq N $
• 输入的所有值均为整数

样例解释 1

对于输出样例中的 $ S,T $，构造 $ G(S,T) $ 如下：

• 准备一个包含 $ 4 $ 个顶点的图 $ g $。
• $ S $ 中 0 的下标为 $ (1,2) $，$ T $ 中 0 的下标为 $ (3,4) $。在 $ g $ 中添加边 $ (1,3),(2,4) $。
• $ S $ 中 1 的下标为 $ (3,4) $，$ T $ 中 1 的下标为 $ (1,2) $。在 $ g $ 中添加边 $ (3,1),(4,2) $。
• $ G(S,T)=g $。

$ G(S,T) $ 的连通分量为顶点 $ (1,3) $ 和顶点 $ (2,4) $。这满足所有条件，因此该 $ (S,T) $ 是正确的输出。

由 ChatGPT 4.1 翻译