Building Skyscrapers
Contest: CEOI 2019 day 1 online mirror (unrated, IOI format)
Tags: *special

We are going to build a new city: the Metropolis. The city is going to be built on an infinite square grid. The finished city will consist of $$$n$$$ skyscrapers, each occupying a different cell of the grid. At any moment during the construction, the cells that currently do not contain a skyscraper are called empty.

You are given the planned coordinates of the $$$n$$$ skyscrapers. Your task is to find an order in which they can be built while satisfying the rules listed below.

- The building crew has only one crane, so the Metropolis has to be constructed one skyscraper at a time.
- The first skyscraper can be built anywhere on the grid.
- Each subsequent skyscraper has to share a side or a corner with at least one of the previously built skyscrapers (so that it's easier to align the new skyscraper to the grid properly).
- When building a skyscraper, there has to be a way to deliver material to the construction site from the outside of Metropolis by only moving it through empty cells that share a side. In other words, there should be a path of side-adjacent empty cells that connects the cell that will contain the skyscraper to some cell $$$(r,c)$$$ with $$$|r|>10^9$$$ and/or $$$|c|>10^9$$$.

If a solution exists, let's denote the numbers of skyscrapers in the order in which they should be built by $$$s_1, \dots, s_n$$$. There are two types of subtasks:

Type 1: You may produce any valid order.

Type 2: You must find the order that maximizes $$$s_n$$$. Among those, you must find the one that maximizes $$$s_{n-1}$$$. And so on. In other words, you must find the valid order of building for which the sequence $$$(s_n,s_{n-1},\dots,s_1)$$$ is lexicographically largest.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 150,000$$$) – the number of skyscrapers.

The second line contains a single integer $$$t$$$ ($$$1 \le t \le 2$$$) describing the type of the subtask as defined above.

Then, $$$n$$$ lines follow. The $$$i$$$-th of these lines contains two space-separated integers $$$r_i$$$ and $$$c_i$$$ ($$$|r_i|, |c_i| \le 10^9$$$) denoting the coordinates of the cell containing skyscraper $$$i$$$.

(The skyscrapers are not numbered in any particular order. The only reason why they have numbers is that they are used in the output format.)

It is guaranteed that no two skyscrapers coincide.

Output format:
If it is impossible to build the skyscrapers according to the given rules, print a single line containing the string "NO".

Otherwise, print $$$n+1$$$ lines. The first of these lines should contain the string "YES". For each $$$i$$$, the $$$i$$$-th of the remaining $$$n$$$ lines should contain a single integer $$$s_i$$$.

In subtasks with $$$t = 1$$$, if there are multiple valid orders, you may output any one of them.

Constraints:
Time limit: 3.5 s
Memory limit: 1024.0 MB

Note:
Scoring:
Subtask 1 (8 points): $$$t = 1$$$ and $$$n \le 10$$$

Subtask 2 (14 points): $$$t = 1$$$ and $$$n \le 200$$$

Subtask 3 (12 points): $$$t = 1$$$ and $$$n \le 2,000$$$

Subtask 4 (17 points): $$$t = 2$$$ and $$$n \le 2,000$$$

Subtask 5 (20 points): $$$t = 1$$$

Subtask 6 (10 points): $$$t = 2$$$, $$$n \le 70,000$$$ and $$$|r_i|, |c_i| \le 900$$$ for each $$$i$$$

Subtask 7 (19 points): $$$t = 2$$$

In the first example, there are three skyscrapers in a row. All of them can always be reached from outside the Metropolis, and there are four build orders which preserve connectivity:

- 1, 2, 3
- 2, 1, 3
- 2, 3, 1
- 3, 2, 1

Since $$$t = 2$$$, we must choose the first option.

In the second example, the only difference from the first example is that skyscraper 2 shares only corners with skyscrapers 1 and 3, the same set of orders as in the first sample is valid. Since $$$t = 1$$$, each of these answers is correct.

In the third example, the Metropolis is disconnected. We obviously can't build that.

Example input:
3
2
0 0
0 1
0 2

Example output:
YES
1
2
3

Example input:
3
1
0 0
1 1
2 2

Example output:
YES
2
3
1

Editorial:
Let's look at the problem in reverse: $$$n$$$ times, we want to find an arbitrary non-8-articulation 4-reachable from infinity and remove it. This doesn't work if we can reach a situation where no such cell exists, so we need to prove that each 8-connected figure contains at least one non-articulation 4-reachable from infinity.
Proof: If there is a cell with 1 neighbour that is 4-reachable, we are done. Therefore, let's assume all 4-reachable (we always take this to mean "from infinity") cells have at least 2 neighbours.
For any pair of 4-adjacent cells $$$(c_1, c_2)$$$ such that $$$c_1$$$ is full and $$$c_2$$$ empty, the region of $$$(c_1, c_2)$$$ is the set of empty cells which are 8-adjacent to $$$c_1$$$ and 4-reachable from $$$c_2$$$ by only moving between these cells. The regions for fixed $$$c_1$$$ can be found simply by looking at all 8-neighbours of $$$c_1$$$ in cyclic order and removing full cells from this cycle; connected segments are regions.
We can now find an 8-cycle of full 4-reachable cells and a corresponding 4-path of empty cells. First, let's pick a pair $$$(c_f, c_e) = (c_{fi}, c_{ei})$$$ = (a 4-reachable full cell, an empty cell 4-reachable from infinity and 4-adjacent to it). Then, let's build a sequence of such pairs by repeating the following:
1. Find the region $$$R$$$ of $$$(c_f, c_e)$$$.
2. Find 2 full cells that border this region and are 8-adjacent to $$$c_f$$$ (i.e. full cells that were removed to create this region); two such distinct cells must exist since $$$c_f$$$ has at least 2 full neighbours.
3. Choose one of these cells (let's denote it by $$$c_{fn}$$$) that was not chosen in the sequence immediately before $$$c_f$$$ and the 4-neighbour of $$$c_{fn}$$$ (let's denote it by $$$c_{en}$$$) from region $$$R$$$. Note that this relation is bidirectional, i.e. if we start from $$$(c_{fn}, c_{en})$$$, then $$$c_e$$$ is in the region of $$$(c_{fn}, c_{en})$$$ and $$$c_f$$$ borders this region.
4. Change $$$(c_f, c_e)$$$ to $$$(c_{fn}, c_{en})$$$.
This is repeated until we reach $$$c_{fn} = c_{fi}$$$ (initial $$$c_f$$$). The process must terminate since the number of full cells is finite. At the end, the full cells from this sequence form a simple 8-connected cycle $$$C$$$ and the empty cells form a 4-connected path $$$P$$$. Each of the full cells from this cycle is therefore 4-reachable from infinity.
Now, let's compute the minimum $$$r$$$, minimum $$$c$$$, maximum $$$r$$$ and maximum $$$c$$$ coordinates of empty cells from cycle $$$C$$$. Since the cycle contains at least 2 cells, there must be a cell $$$c_0$$$ which is distinct from $$$c_{fi}$$$ and at least one of its coordinates $$$(r, c)$$$ is one of these four extremum coordinates. We need to show that this cell is not an articulation.
It is sufficient to show that $$$c_0$$$ has 3 empty 8-neighbours on one side, i.e. the 3x3 square around it looks as follows (center: $$$c_0$$$, top center: empty cell 4-reachable from infinity).
If it has this form, the top 3 cells are in the same region and if we find the full cells bordering this region (among cells marked *), then these cells are on cycle $$$C$$$ as well, since $$$c_0$$$ is not $$$c_{fi}$$$. Each cell marked * is 8-adjacent to one of these full cells, so emptying the central cell does not break connectivity.
W.l.o.g. let the top 3 cells in the figure above be outside the $$$(\text{min r},\text{ max r}) \times (\text{min c},\text{ max c})$$$ rectangle. Let's prove it by contradiction – assume that there is a full cell among those three; this cell cannot be part of cycle $$$C$$$. Since path $$$P$$$ consists of cells adjacent to those from cycle $$$C$$$, it cannot contain any cells above this figure, so the top middle cell cannot be part of path $$$P$$$ either (it is not 4-adjacent to $$$c_{fi}$$$ and it is either full or has at most 1 empty neighbour in the top row). Path $$$P$$$ and cell $$$c_{fi}$$$ form a 4-cycle, which splits the grid into two 8-components, one of which contains all cells from $$$C$$$ other than $$$c_{fi}$$$. Since everything above our figure does not contain any cells from $$$P+c_{fi}$$$, it must be part of the latter component, and since it is 4-connected to the top middle cell, which cannot be part of $$$P+c_{fi}$$$, the top middle cell must also be part of this component. But then, the middle cell is 4-adjacent to the second component and it is part of the first component, which is a contradiction. QED.
Hopefully, you've had enough math by now. (If not, you can try to prove the same claim for 4-connected full cells and 8-adjacency to empty cells 8-reachable from infinity.) We can finally get back to the programming problem!
Subtasks 4, 6 and 7
Checking reachability from infinity is easy. We can store the 4-connected components of empty cells, remember which component corresponds to the outside and whenever we make a new empty cell, we can update this information with the simple "merge smaller to larger" strategy. We just have to choose which empty cells to consider, since the naive estimate is $$$\mathcal O(n^2)$$$ empty cells; however, empty cells which have no full 8-neighbours in the original figure are not interesting, so we are left with $$$\mathcal O(n)$$$ interesting cells and the total time complexity of calculating connected components is $$$\mathcal O(n \log n)$$$.
When is a full cell $$$c$$$ an articulation? Let's look at all its regions that aren't isolated empty corners (since their neighbours on the border of $$$c$$$ are 8-connected, so the following argument doesn't apply). For each pair of different regions $$$r_1$$$ and $$$r_2$$$, if there is no 4-path of empty cells connecting them, then for each pair of full non-adjacent 8-neighbours of $$$c$$$ ($$$c_1$$$ and $$$c_2$$$) such that $$$c_1, r_1, c_2, r_2$$$ are in this order around $$$c$$$, there is an 8-path of full cells connecting $$$c_1$$$ and $$$c_2$$$ that does not contain $$$c$$$. Vice versa, if there is a path connecting two such cells $$$c_1$$$ and $$$c_2$$$ that does not contain $$$c$$$, then there is no 4-path connecting $$$r_1$$$ and $$$r_2$$$. Since for each pair of non-corner regions $$$r_1$$$ and $$$r_2$$$, we can find 2 cells $$$c_1$$$ and $$$c_2$$$, we get an equivalent definition of a non-articulation: all non-corner regions belong to different 4-connected components of empty cells.
This simplifies things. We're already updating connected components, so the information about articulation-ness of cells is local – if we know the empty 4-neighbours and connected components of a full cell, we can compute whether it is an articulation in $$$\mathcal O(1)$$$ time. This information only needs recomputing if empty neighbours appear or are moved to a different component.
Now, we only need to realise that we already have to look at all empty cells that appear or are moved to a different component. It's done in the "merge smaller to larger" union-find for empty cells – when merging component $$$K_s$$$ into component $$$K_l$$$, we have to look at all cells from $$$K_s$$$ to update which component they belong to, and we only create an empty cell $$$\mathcal O(n)$$$ times along with that. For each cell at which we look in the union-find, we can just check all its full 8-neighbours, and for each of these neighbours, we can update the information abouts its neighbours, decide whether it is an articulation and if it is reachable from the outer component, all in $$$\mathcal O(1)$$$ time.
We are left with updates saying "this cell can be removed" / "this cell cannot be removed". With them, it's easy to keep the set of removable cells in amortised $$$\mathcal O(\log n)$$$ and choose the cell to remove in each step in $$$\mathcal O(\log n)$$$. The subtask type is irrelevant, we could just as well support queries "remove this cell or report that it's not allowed".
Obviously, the answer is "NO" if and only if the final configuration isn't 8-connected.
Total time complexity: $$$\mathcal O(n \log n)$$$, memory complexity $$$\mathcal O(n)$$$.
In subtask 6, we can afford to store the graph as a 2D array, with complexity $$$\mathcal O(n\log n + r_{max} c_{max})$$$. Also, we are checking if a cell is an articulation in $$$\mathcal O(d)$$$, where $$$d = 8$$$ is the number of neighbours of a cell, but less efficient implementations like finding regions and checking all pairs of regions in $$$\mathcal O(d^2)$$$ become possible.
In subtask 4, we only need to determine if it's possible to remove a skyscraper in $$$\mathcal O(1)$$$. Whenever we're removing a skyscraper, we can simply find the last removable one, then update the connected components, either by merging existing ones or running BFS on the interesting cells. This works in $$$\mathcal O(n^2)$$$.
Subtasks 3 and 5
When we are allowed to choose the output sequence, a much simpler approach becomes possible:
• First, build an arbitrary skyscraper.
• Store the set of skyscrapers which haven't been built, but are 8-adjacent to those which have been built.
• While we need to build a skyscraper, pick the rightmost one from this set (with the maximum $$$c_i$$$); if there is more than one such skyscraper, pick the one with the maximum $$$r_i$$$. Then, update the set.
This takes $$$\mathcal O(n \log n)$$$ time when the skyscrapers are stored efficiently (e.g. in an STL set<>), or $$$\mathcal O(n^2)$$$ by brute force.
The set of built skyscrapers is 8-connected, but it isn't immediately clear why we can't fail by closing an 8-cycle and then building a skyscraper inside it. However, it makes sense – informally, before building the last skyscraper from this cycle, we can already build everything on its inner border, and if the final configuration is 8-connected and there is something inside the cycle we still need to build, there will be a skyscraper we haven't built yet on this border with greater $$$c_i$$$ (or equal $$$c_i$$$ and greater $$$r_i$$$). We'll build everything inside a cycle before we finish the cycle itself.
Subtask 2
We can use the approach for $$$t = 1$$$, or we can guess that the hypothesis about existence of a removable skyscraper is true. Then, we can choose a skyscraper to remove by checking which ones can be removed (by removing and running BFS on the remaining graphs of empty and full cells). If we do this $$$n$$$ times, the time complexity is $$$\mathcal O(n^3)$$$.
Subtask 1
We can try all $$$\mathcal O(n!)$$$ possible orders and check if they are valid.