← 返回题目列表

Codeforces · 297/C

C. 分裂唯一性

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

北极熊喜欢独特的数组,即没有重复元素的数组。

你有一个唯一的数组 s ,长度为 n ,包含非负整数。由于您与 Alice 和 Bob 是好朋友,因此您决定将数组一分为二。准确地说,您需要构造两个长度同样为 n 的数组 a 和 b,对于所有 i (1 ≤ i ≤ n) 满足以下条件:

- ai, bi 是非负整数;
- si = ai + bi 。

理想情况下,a 和 b 也应该是唯一的数组。然而,北极的生活很艰难,这并不总是可能的。幸运的是,如果 Alice 和 Bob 的数组几乎是唯一的,他们仍然会很高兴。我们将长度为 n 的数组定义为几乎唯一的,当且仅当可以通过删除不超过 $$\left\lceil \frac{n}{3} \right\rceil$$ 条目将其转换为唯一数组时。

例如,数组 [1, 2, 1, 3, 2] 几乎是唯一的,因为删除前两个条目后,它变成了 [1, 3, 2]。数组 [1, 2, 1, 3, 1, 2] 几乎不是唯一的,因为我们需要删除至少 3 个条目才能将其变成唯一数组。

因此,你的任务是将给定的唯一数组 s 拆分为两个几乎唯一的数组 a 和 b。

输入

输入的第一行包含整数 n (1 ≤ n ≤ 105)。

第二行包含 n 个不同的整数 s1, s2, ... sn (0 ≤ si ≤ 109)。

输出

如果可以让 Alice 和 Bob 开心(如果你可以拆分给定的数组),请在第一行打印“YES”(不带引号)。在第二行中,打印数组 a。在第三行中,打印数组 b。可能有不止一种解决方案。其中任何一个都会被接受。

如果不可能将 s 拆分为几乎唯一的数组 a 和 b,请在第一行打印“NO”(不带引号)。

示例

输入 #1

6
12 5 8 3 11 9

输出 #1

YES
6 2 6 0 2 4
6 3 2 3 9 5

注意

在示例中,我们可以删除 a 中的前两个条目和 b 中的第二个条目,以使它们都是唯一的。