Easy 没什么启发性，直接考虑 Medium。
考虑到 \(a_1 = 0\)，那么 \(1\) 明显直接和自己配对就行，考虑分配到一个特殊的位置 \((1, 1)\)。
接下来考虑如果还有 \(a_i = 0\)，那么明显 \(i\) 也是和自己配对，此时因为这是无关紧要的就可以离特殊的 \((1, 1)\) 尽量远一点，也就是让 \(x\) 坐标尽量大。
同时如果有 \(a_i = a_j\)，那么就可以让 \(i, j\) 互相配对，还是一样尽量远，可以让两个的 \(x\) 坐标就相差 \(1\)，构造 \((x, 1), (x + 1, a_i)\) 即可。
剩下的不同的 \(a_i\) 的取值肯定就只存在一个 \(a_i\) 了。
这个时候考虑到 \((2, y)\) 与 \((1, i)\) 的距离可以为 \(1\sim n\)，\((3, y)\) 与 \((2, i)\) 的距离可以为 \(2\sim n + 1\)……
那么就可以把剩下的 \(a_i\) 从小到大排序，然后 \(x\) 从 \(2\) 开始依次往大了去填，因为 \(a_i\le n\) 且因为每种取值最多存在一个有 \(a_i\ge x - 1\)，肯定可以分配出 \(y\)。
那么就构造完了，按照这个方式可以知道肯定有解。
时间复杂度 \(\mathcal{O}(n)\)。
代码写丑了写成了 \(\mathcal{O}(n\log n)\)，把 map 换成桶即可。
代码
#include<bits/stdc++.h>
const int maxn = 2e5 + 10;
int a[maxn];
int dx[maxn], dy[maxn], to[maxn];
bool vis[maxn];
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
dx[1] = dy[1] = to[1] = 1;
std::map<int, int> mp;
int w = n;
for (int i = 2; i <= n; i++) {
if (! a[i]) {
dx[i] = w--, dy[i] = 1, to[i] = i;
} else {
if (mp[a[i]]) {
int j = mp[a[i]];
dx[i] = w--, dx[j] = w--, to[i] = j, to[j] = i;
dy[i] = 1, dy[j] = a[i];
mp[a[i]] = 0;
} else
mp[a[i]] = i;
}
}
w = 2;
for (auto _ : mp) {
int v = _.first, id = _.second;
if (! id) continue;
dx[id] = w, dy[id] = 1 + v - (w - 1), to[id] = 1, w++;
}
puts("YES");
for (int i = 1; i <= n; i++) printf("%d %d\n", dx[i], dy[i]);
for (int i = 1; i <= n; i++) printf("%d ", to[i]);
return 0;
}
接下来考虑 Hard。
首先如果存在 \(a_i = 0\)，那么还是像 Medium 那样做就行了。
否则考虑用一些其他的替代掉 \(a_i = 0\) 的作用。
一个想法是对于 \(a_i = a_j\) 的，可以分配到 \((1, 1), (2, a_i)\)，然后就像 Medium 一样构造。
但是能发现这个有个小问题，就是因为 \(x = 2\) 已经被占了，导致如果存在 \(a_k = 1\) 这个 \(k\) 没有位置了。
但是可以考虑把 \(k\) 拎出来，先填完 \(2\sim n\) 的。
因为 \(a_k = 1\) 实际上就是 \(x\) 坐标差 \(1\)，\(y\) 坐标相同，设填完 \(2\sim n\) 最后一个填的的坐标是 \((x, y)\)，给 \(k\) 分配 \((x + 1, y)\) 即可。
还有一种方式是一开始分配成 \((1, a_i), (2, 1)\)，然后特殊点就变为 \((2, 1)\)，就是完全一样的了。
发现还是会漏掉情况。
但是能发现漏掉的情况只会有 \(1\sim n\) 都只刚好出现 \(1\) 次。
这个时候能发现 \(n = 2\) 时无解。
否则对于 \(a_i = 1, a_j = 2, a_k = 3\)，可以分别构造出 \((1, 1), (2, 1), (3, 2)\)，其中 \(i\to j, j\to k, k\to i\)。
然后对于 \(4\sim n\) 的和其他的一样构造即可。
时间复杂度 \(\mathcal{O}(n\log n)\)。
代码
#include<bits/stdc++.h>
const int maxn = 2e5 + 10;
int a[maxn];
int dx[maxn], dy[maxn], to[maxn];
int lst[maxn];
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
int f = 0, fid = 0, bk = n, edy = 0, edid = 0;
for (int i = 1; i <= n; i++) {
if (! a[i]) {
if (! f) dx[i] = ++f, fid = i, edy = 1, edid = i;
else dx[i] = bk--;
dy[i] = 1, to[i] = i;
} else if (lst[a[i]]) {
int &j = lst[a[i]];
if (! f) dx[i] = ++f, dx[j] = ++f, fid = i, edy = a[i], edid = j;
else dx[i] = bk--, dx[j] = bk--;
dy[i] = 1, dy[j] = a[i], to[i] = j, to[j] = i;
j = 0;
} else lst[a[i]] = i;
}
if (! f) {
if (n == 2)
return puts("NO");
int &x = lst[1], &y = lst[2], &z = lst[3];
f = 3, fid = x, edy = 2, edid = z;
dx[x] = 1, dy[x] = 1;
dx[y] = 2, dy[y] = 1;
dx[z] = 3, dy[z] = 2;
to[x] = y, to[y] = z, to[z] = x;
x = y = z = 0;
}
for (int i = 2; i <= n; i++)
if (lst[i]) {
int p = lst[i];
dx[p] = ++f, dy[p] = 1 + i - (f - 1), to[p] = fid;
edy = dy[p], edid = p;
}
if (lst[1]) {
int p = lst[1];
dx[p] = ++f, dy[p] = edy, to[p] = edid;
}
puts("YES");
for (int i = 1; i <= n; i++) printf("%d %d\n", dx[i], dy[i]);
for (int i = 1; i <= n; i++) printf("%d ", to[i]);
return 0;
}