P8520 [IOI 2021] Fountain Park

### Due to technical limitations, please do not use C++ 14 (GCC 9) to submit this problem. This is an interactive problem. You only need to implement the function required in the code. Your code does not need to include any additional header files, and you do not need to implement the `main` function. However, your code must declare the function `void build(std::vector u, std::vector v, std::vector a, std::vector b)`. Specifically, the following is a template: ```cpp #include void build(std::vector u, std::vector v, std::vector a, std::vector b); int construct_roads(std::vector x, std::vector y) { // Code here... } ``` Due to Luogu technical limitations, this problem only includes some of the official IOI test points.

In a nearby park, there are $n$ **fountains**, numbered from $0$ to $n - 1$. We treat the fountains as points on a 2D plane. That is, fountain $i ~ (0 \leq i \leq n - 1)$ is the point $(x _ i, y _ i)$, where $x _ i$ and $y _ i$ are **even numbers**. All fountain positions are distinct. The architect Timothy is hired to plan the construction of some **roads**, and the placement of a bench for each road. Each road is a **horizontal** or **vertical** line segment of length $2$, whose endpoints are two different fountains. Visitors should be able to travel between any two fountains by walking along these roads. Initially, there are no roads in the park. For each road, exactly one bench must be placed in the park and **assigned to** (i.e., facing) this road. Each bench must be placed at a point $(a, ~ b)$, where both $a$ and $b$ are **odd numbers**. All bench positions must be **distinct**. A bench at $(a, ~ b)$ can only be assigned to a road whose two endpoints are one of the four points $(a - 1, ~ b - 1), (a - 1, ~ b + 1), (a + 1, ~ b - 1)$, and $(a + 1, ~ b + 1)$. For example, a bench at $(3, ~ 3)$ can only be assigned to one of the four roads represented by the following segments: $(2, ~ 2), - (2, ~ 4), ~ (2 , ~ 4) - (4, ~ 4), ~ (4, ~ 4) - (4, ~ 2), ~ (4, ~ 2) - (2, ~ 2)$. Help Timothy determine whether it is possible to build the roads and place and assign the benches while satisfying all the requirements above. If it is possible, provide one feasible solution. If there are multiple solutions, you may output any one of them.

You need to implement the following function: ```cpp int construct_roads(std::vector x, std::vector y) ``` - $x, ~ y$: Two arrays of length $n$. For all $i ~ (0 \leq i \leq n - 1)$, fountain $i$ is at point $(x[i], y[i])$, where $(x[i], y[i])$ are even numbers. - If there exists a construction plan, the function should call `build` (see below) exactly once to report the plan, and then immediately return $1$. - Otherwise, the function should return $0$ and must not call `build`. - This function will be called exactly once. Your function may call the following function to provide a feasible road construction and bench placement plan: ```cpp void build(std::vector u, std::vector v, std::vector a, std::vector b) ``` - Let $m$ be the number of roads in the plan. - $u, v$: Two arrays of length $m$, describing the roads to be built. The roads are numbered from $0$ to $m - 1$. For all $j ~ (0 \leq j \leq m - 1)$, road $j$ connects fountains $u[j]$ and $v[j]$. Each road must be a horizontal or vertical segment of length $2$. Any two different roads may share at most one common endpoint (a fountain). After building these roads, it must be possible to travel between any two fountains by walking along them. - $a, b$: Two arrays of length $m$, describing the benches. For all $j ~ (0 \leq j \leq m - 1)$, a bench will be placed at $(a[j], b[j])$ and assigned to road $j$. Different benches must not be placed at the same position.

N/A

**Example 1** Consider the following call: ```cpp construct_roads([4, 4, 6, 4, 2], [4, 6, 4, 2, 4]) ``` This means there are $5$ fountains in total: - Fountain $0$ is located at $(4, 4)$. - Fountain $1$ is located at $(4, 6)$. - Fountain $2$ is located at $(6, 4)$. - Fountain $3$ is located at $(4, 2)$. - Fountain $4$ is located at $(2, 4)$. We can build the following $4$ roads, where each road connects two fountains and has its assigned bench. | Road ID | Fountain IDs connected by the road | Assigned bench position | | :----------: | :----------: | :----------: | | $0$ | $0, 2$ | $(5, 5)$ | | $1$ | $0, 1$ | $(3, 5)$ | | $2$ | $3, 0$ | $(5, 3)$ | | $3$ | $4, 0$ | $(3, 3)$ | This plan corresponds to the figure below:  To report this plan, `construct_roads` should make the following call: ```cpp build([0, 0, 3, 4], [2, 1, 0, 0], [5, 3, 5, 3], [5, 5, 3, 3]) ``` Then it should return $1$. Note that in this example, there are multiple valid plans, and any of them is considered correct. **Example 2** Consider the following call: ```cpp construct_roads([2, 4], [2, 6]) ``` Fountain $0$ is located at $(2, 2)$, and fountain $1$ is located at $(4, 6)$. Since it is impossible to build roads that satisfy the requirements, `construct_roads` should return $0$ and must not call `build`. **Constraints** - $1 \leq n \leq 2 \times 10 ^ 5$ - $2 \leq x[i], y[i] \leq 2 \times 10 ^ 5$ - $x[i], y[i]$ are even numbers. - No two fountains share the same position. **Subtasks** 1. ($5$ points) $x[i] = 2$ 2. ($10$ points) $2 \leq x[i] \leq 4$ 3. ($15$ points) $2 \leq x[i] \leq 6$ 4. ($20$ points) There is at most one road construction plan that allows visitors to travel between any two fountains along the roads. 5. ($20$ points) No four fountains form the four vertices of a $2 \times 2$ square. 6. ($30$ points) No additional constraints. Translated by ChatGPT 5