CF297C Splitting the Uniqueness

北极熊喜欢“唯一数组”，即没有重复元素的数组。 你得到一个长度为 $n$ 的唯一数组 $s$，其中包含非负整数。由于你和 Alice 以及 Bob 是好朋友，你决定将该数组拆分成两个数组。具体地，你需要构造两个长度也为 $n$ 的数组 $a$ 和 $b$，满足以下条件，对于所有的 $i$ $(1\leq i\leq n)$： - $a_i,b_i$ 是非负整数； - $s_i = a_i + b_i$。 理想情况下，$a$ 和 $b$ 也应该是唯一数组。然而，在北极的生活很艰难，这并不总是可能的。幸运的是，Alice 和 Bob 只要数组“几乎唯一”也会感到高兴。如果一个长度为 $n$ 的数组，通过删除不超过 $\left\lfloor \frac{n}{2} \right\rfloor$ 个元素，它就能变成唯一数组，那么它被称为“几乎唯一数组”。 例如，数组 $[1,2,1,3,2]$ 是“几乎唯一数组”，因为删除前两个元素后得到 $[1,3,2]$，这是唯一数组。而数组 $[1,2,1,3,1,2]$ 不是“几乎唯一数组”，因为至少需要删除 $3$ 个元素才能变成唯一数组。 因此，你的任务是，将给定的唯一数组 $s$ 拆分为两个“几乎唯一数组” $a$ 和 $b$。

第一行包含整数 $n$ $(1\leq n\leq 10^5)$。 第二行包含 $n$ 个两两不同的整数 $s_1, s_2, \ldots, s_n$，其中 $0\leq s_i\leq 10^9$。

如果存在拆分方法使 Alice 和 Bob 满意（可以拆分该数组），则第一行输出 "YES"（不带引号）。第二行输出数组 $a$，第三行输出数组 $b$。可能有多种方案，任意一种都被接受。 如果无法将 $s$ 拆分为两个“几乎唯一数组” $a$ 和 $b$，则第一行输出 "NO"（不带引号）。

在样例中，可以删除 $a$ 的前两个元素，以及 $b$ 的第二个元素，从而使它们都变为唯一数组。 由 ChatGPT 5 翻译