Exact Neighbours (Medium)

官解的方法二就是这篇博客（注意要先将\(a\)从小到大排序），补充一下，博客中说当\(a_j-j+1<0\)时，我们就找第\(j-a_j\)列的那个房子即可

我在做的时候，也想到了逐个构造的方法，然而我在构造新的一列时，却总是想让这一列的房子与前一列的房子来配对，事实证明，我们构造的时候不要拘泥于数学归纳法，可以从强数学归纳的思想出发，去找前面所有构造好了的房子

官解的方法一没有看懂英文是啥意思

我的方法与上述两种方法都不同：

显然\(1\)号房子是最特殊的，所以我们将其放在\((1,1)\)，然后我们采用逐个构造法，发现如果存在两个\(a\)相同的房子就不太好构造，于是我们将相同的房子两两配对，并且从最后一列依次往前面放（显然合法），最后剩下的还没有配对的房子的\(a\)都不同，于是尝试将其与\(1\)号房子配对，注意此时第二列的距离可以放\(1\)到\(n\)，第三列的距离可以放\(2\)到\(n\)，依次类推，于是我们将剩下的房子排序，显然从小到大依次放置就合法；具体见以下代码，非常easy

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+10;
const ll mod=998244353;
int n;
bool mark[N];
struct node
{
	int id,a;//id表示房子的编号，a如题目所述 
}t[N];
struct Node
{
	int x,y,to;//(x,y)是房子的坐标，to是与其配对的房子编号 
}ans[N];
bool cmp(node i,node j)
{
	if(i.a==j.a) return i.id<j.id;
	return i.a<j.a;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) 
	{
		t[i].id=i;
		scanf("%d",&t[i].a);
	}
	sort(t+1,t+n+1,cmp);
	for(int i=2,last=n;i<=n;i++)//last表示最后的还没有放置房子的列，我们从后往前依次放置 
	if(t[i].a==0)//注意0的单独放置一列就好了 
	{
		ans[t[i].id].x=last--,ans[t[i].id].y=1;
		ans[t[i].id].to=t[i].id;
		mark[i]=1;
	}
	else if(t[i].a==t[i-1].a)
	{
		ans[t[i].id].x=last--,ans[t[i].id].y=1;
		ans[t[i-1].id].x=last--,ans[t[i-1].id].y=t[i].a;
		ans[t[i].id].to=t[i-1].id,ans[t[i-1].id].to=t[i].id;
		mark[i]=mark[i-1]=1;
		i++;
	}
	ans[1].x=ans[1].y=ans[1].to=1;
	for(int i=2,last=2;i<=n;i++)
	if(!mark[i])
	{
		ans[t[i].id].x=last++,ans[t[i].id].y=t[i].a-ans[t[i].id].x+2;
		ans[t[i].id].to=1;
	}
	puts("YES");
	for(int i=1;i<=n;i++)
	printf("%d %d\n",ans[i].x,ans[i].y);
	for(int i=1;i<=n;i++) printf("%d ",ans[i].to);
	return 0;
}