311320: CF1970B3. Exact Neighbours (Hard)
Description
After some recent attacks on Hogwarts Castle by the Death Eaters, the Order of the Phoenix has decided to station $n$ members in Hogsmead Village. The houses will be situated on a picturesque $n\times n$ square field. Each wizard will have their own house, and every house will belong to some wizard. Each house will take up the space of one square.
However, as you might know wizards are very superstitious. During the weekends, each wizard $i$ will want to visit the house that is exactly $a_{i}$ $(0 \leq a_{i} \leq n)$ away from their own house. The roads in the village are built horizontally and vertically, so the distance between points $(x_{i}, y_{i})$ and $(x_{j}, y_{j})$ on the $n\times n$ field is $ |x_{i} - x_{j}| + |y_{i} - y_{j}|$. The wizards know and trust each other, so one wizard can visit another wizard's house when the second wizard is away. The houses to be built will be big enough for all $n$ wizards to simultaneously visit any house.
Apart from that, each wizard is mandated to have a view of the Hogwarts Castle in the north and the Forbidden Forest in the south, so the house of no other wizard should block the view. In terms of the village, it means that in each column of the $n\times n$ field, there can be at most one house, i.e. if the $i$-th house has coordinates $(x_{i}, y_{i})$, then $x_{i} \neq x_{j}$ for all $i \neq j$.
The Order of the Phoenix doesn't yet know if it is possible to place $n$ houses in such a way that will satisfy the visit and view requirements of all $n$ wizards, so they are asking for your help in designing such a plan.
If it is possible to have a correct placement, where for the $i$-th wizard there is a house that is $a_{i}$ away from it and the house of the $i$-th wizard is the only house in their column, output YES, the position of houses for each wizard, and to the house of which wizard should each wizard go during the weekends.
If it is impossible to have a correct placement, output NO.
InputThe first line contains $n$ ($2 \leq n \leq 2\cdot 10^{5}$), the number of houses to be built.
The second line contains $n$ integers $a_{1}, \ldots, a_{n}$ $(0 \leq a_{i} \leq n)$
OutputIf there exists such a placement, output YES on the first line; otherwise, output NO.
If the answer is YES, output $n + 1$ more lines describing the placement.
The next $n$ lines should contain the positions of the houses $1 \leq x_{i}, y_{i} \leq n$ for each wizard.
The $i$-th element of the last line should contain the index of the wizard, the house of which is exactly $a_{i}$ away from the house of the $i$-th wizard. If there are multiple such wizards, you can output any.
If there are multiple house placement configurations, you can output any.
ExamplesInput4 0 4 2 4Output
YES 4 4 1 3 2 4 3 1 1 1 1 3Input
4 1 3 0 1Output
YES 2 1 4 1 1 1 3 1 3 3 3 1Note
For the sample, the house of the 1st wizard is located at $(4, 4)$, of the 2nd at $(1, 3)$, of the 3rd at $(2, 4)$, of the 4th at $(3, 1)$.
The distance from the house of the 1st wizard to the house of the 1st wizard is $|4 - 4| + |4 - 4| = 0$.
The distance from the house of the 2nd wizard to the house of the 1st wizard is $|1 - 4| + |3 - 4| = 4$.
The distance from the house of the 3rd wizard to the house of the 1st wizard is $|2 - 4| + |4 - 4| = 2$.
The distance from the house of the 4th wizard to the house of the 3rd wizard is $|3 - 2| + |1 - 4| = 4$.
The view and the distance conditions are satisfied for all houses, so the placement is correct.
Output
输入输出数据格式：
输入：
- 第一行包含一个整数n（2≤n≤2×10^5），表示要建造的房屋数量。
- 第二行包含n个整数a1, ..., an（0≤ai≤n），表示每个巫师想要访问的房屋距离。
输出：
- 如果存在这样的安排，则第一行输出YES；否则输出NO。
- 如果答案为YES，则输出n+1行描述安排。
- 接下来的n行应包含每个巫师房屋的位置（xi, yi），1≤xi, yi≤n。
- 最后一行的第i个元素应包含距离第i个巫师房屋恰好为ai的巫师的索引。如果有多个这样的巫师，可以输出其中任何一个。
- 如果存在多个房屋布置配置，可以输出其中任何一个。
示例：
输入：
```
4
0 4 2 4
```
输出：
```
YES
4 4
1 3
2 4
3 1
1 1 1 3
```
注意：对于示例，第1个巫师的房子位于(4, 4)，第2个巫师的房子位于(1, 3)，第3个巫师的房子位于(2, 4)，第4个巫师的房子位于(3, 1)。所有房子的视野和距离条件都得到满足，因此这种布置是正确的。题目大意：凤凰社决定在霍格莫德村为n个成员安排房屋，房屋位于一个n×n的正方形区域中。每个巫师都有自己的房子，每座房子都属于某个巫师，每座房子占据一个方格。巫师们在周末想要访问距离自己房屋恰好为ai的房子(ai为0到n之间的整数)。村子的道路是水平或垂直建造的，所以两点(xi, yi)和(xj, yj)之间的距离是|x_i - x_j| + |y_i - y_j|。巫师们彼此信任，可以在其他巫师不在时访问他们的房子。要建造的房子足够大，可以同时容纳所有n个巫师访问任何房子。此外，每个巫师的房子都必须能够看到北方的霍格沃茨城堡和南方的禁林，所以每个巫师的房子都应该是他们所在列中唯一的房子。需要帮助设计一个方案，以使所有巫师都能满足访问和视野要求。 输入输出数据格式： 输入： - 第一行包含一个整数n（2≤n≤2×10^5），表示要建造的房屋数量。 - 第二行包含n个整数a1, ..., an（0≤ai≤n），表示每个巫师想要访问的房屋距离。 输出： - 如果存在这样的安排，则第一行输出YES；否则输出NO。 - 如果答案为YES，则输出n+1行描述安排。 - 接下来的n行应包含每个巫师房屋的位置（xi, yi），1≤xi, yi≤n。 - 最后一行的第i个元素应包含距离第i个巫师房屋恰好为ai的巫师的索引。如果有多个这样的巫师，可以输出其中任何一个。 - 如果存在多个房屋布置配置，可以输出其中任何一个。 示例： 输入： ``` 4 0 4 2 4 ``` 输出： ``` YES 4 4 1 3 2 4 3 1 1 1 1 3 ``` 注意：对于示例，第1个巫师的房子位于(4, 4)，第2个巫师的房子位于(1, 3)，第3个巫师的房子位于(2, 4)，第4个巫师的房子位于(3, 1)。所有房子的视野和距离条件都得到满足，因此这种布置是正确的。