← 返回题目列表

Codeforces · 1168/E

E. 异或排列

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

Toad Mikhail 有一个 $$$2^k$$$ 整数数组 $$$a_1, a_2, \ldots, a_{2^k}$$$。

找到整数 $$$0, 1, \ldots, 2^k-1$$$ 的两个排列 $$$p$$$ 和 $$$q$$$,使得对于所有可能的 $$$i$$$,$$$a_i$$$ 等于 $$$p_i \oplus q_i$$$,或者确定不存在这样的排列。这里$$$\oplus$$$表示按位异或运算。

输入

第一行包含一个整数$$$k$$$ ($$$2 \leq k \leq 12$$$),表示数组的大小为$$$2^k$$$。

下一行包含 $$$2^k$$$ 空格分隔的整数 $$$a_1, a_2, \ldots, a_{2^k}$$$ ($$$0 \leq a_i < 2^k$$$) - 给定数组的元素。

输出

如果给定数组无法表示为整数 $$$0, 1, \ldots, 2^k-1$$$ 的两个排列的按元素异或,则打印“Fou”。

否则,在第一行打印“Shi”。

接下来的两行应包含两个合适的排列的描述。第一行应包含 $$$2^k$$$ 以空格分隔的不同整数 $$$p_{1}、p_{2}、\ldots、p_{2^k}$$$,第二行应包含 $$$2^k$$$ 以空格分隔的不同整数 $$$q_{1}、q_{2}、\ldots、q_{2^k}$$$。

$$$p$$$ 和 $$$q$$$ 的所有元素应在 $$$0$$$ 和 $$$2^k - 1$$$ 之间(含);对于所有$$$i$$$,$$$p_i \oplus q_i$$$ 应等于$$$a_i$$$,使得$$$1 \leq i \leq 2^k$$$。如果有多种可能的解决方案,您可以打印任何一个。

示例

输入 #1

2
0 1 2 3

输出 #1

Shi
2 0 1 3 
2 1 3 0

输入 #2

2
0 0 0 0

输出 #2

Shi
0 1 2 3 
0 1 2 3

输入 #3

2
0 1 2 2

输出 #3

Fou