CF297C Splitting the Uniqueness 题解
非常好构造题，使我的草稿纸旋转。
解法
我们记输入的数组为 a a a，需要输出的两个数组为 b , c b,c b,c（因为当时起变量名起的）。
考虑利用 a i a_i ai 互不相同的性质。
先将 a i a_i ai 升序排序。因为题中保证 a i a_i ai 互不相同，所以相邻两数的差至少为 1 1 1，从而 a i ≥ i − 1 a_i \ge i - 1 ai≥i−1。
考虑到最多有 ⌈ n 3 ⌉ \lceil \dfrac{n}{3} \rceil ⌈3n⌉ 个重复数字，即为需要至少有 ⌊ 2 n 3 ⌋ \lfloor \dfrac{2n}{3} \rfloor ⌊32n⌋ 种不同数字。我们可以将整个数组等分为 3 3 3 段，分别是 [ 1 , ⌊ n 3 ⌋ ] [1,\lfloor \dfrac{n}{3} \rfloor ] [1,⌊3n⌋]， ( ⌊ n 3 ⌋ , ⌊ 2 n 3 ⌋ ] (\lfloor \dfrac{n}{3} \rfloor,\lfloor \dfrac{2n}{3} \rfloor] (⌊3n⌋,⌊32n⌋]， ( ⌊ 2 n 3 ⌋ , n ] (\lfloor \dfrac{2n}{3} \rfloor,n] (⌊32n⌋,n]。具体构造如下图。
为什么这么构造是对的？
显然对于 c c c 数组，第二段和第三段的数互不相同，满足至少有 ⌊ 2 n 3 ⌋ \lfloor \dfrac{2n}{3} \rfloor ⌊32n⌋ 种不同数字。考虑为什么 b b b 数组至少有 ⌊ 2 n 3 ⌋ \lfloor \dfrac{2n}{3} \rfloor ⌊32n⌋ 种不同数字。
观察第一段和第三段，因为 a i ≥ i − 1 a_i \ge i-1 ai≥i−1，所以第三段的第一个 a i a_i ai 满足 a i ≥ 2 n 3 a_i \ge \dfrac{2n}{3} ai≥32n，而 n − ⌊ 2 n 3 ⌋ − 1 = ⌈ n 3 ⌉ − 1 n - \lfloor \dfrac{2n}{3} \rfloor -1 = \lceil \dfrac{n}{3} \rceil - 1 n−⌊32n⌋−1=⌈3n⌉−1，所以 c i c_i ci 满足 c i ≥ n 3 c_i \ge \dfrac{n}{3} ci≥3n，而在第三段 a a a 单调上升， c c c 单调下降，所以 b b b 单调上升，所以 b b b 数组在第一段和第三段互不相同。
代码
#include<bits/stdc++.h>
namespace fast_IO
{
/**
* 没啥用的快读快写
*/
};
using namespace fast_IO;
int n,b[100010],c[100010],fir,sec;
struct node
{
int val,ord;
inline bool operator<(const node rhs) const
{
return val<rhs.val;
}
};
node a[100010];
int main()
{
in>>n,fir=n/3,sec=n*2/3;
for(int i=1;i<=n;i++) in>>a[i].val,a[i].ord=i;
std::sort(a+1,a+n+1);
for(int i=1;i<=fir;i++) b[a[i].ord]=i-1,c[a[i].ord]=a[i].val-b[a[i].ord];
for(int i=fir+1;i<=sec;i++) c[a[i].ord]=i-1,b[a[i].ord]=a[i].val-c[a[i].ord];
for(int i=n;i>sec;i--) c[a[i].ord]=n-i,b[a[i].ord]=a[i].val-c[a[i].ord];
out<<"YES\n";
for(int i=1;i<=n;i++) out<<b[i]<<' ';
out<<'\n';
for(int i=1;i<=n;i++) out<<c[i]<<' ';
fwrite(Ouf,1,p3-Ouf,stdout),fflush(stdout);
return 0;
}