Background

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<int> u, std::vector<int> v, std::vector<int> a, std::vector<int> b).

Specifically, the following is a template:

#include <vector>

void build(std::vector<int> u, std::vector<int> v, std::vector<int> a, std::vector<int> b);

int construct_roads(std::vector<int> x, std::vector<int> y) {
    // Code here...
}

Due to Luogu technical limitations, this problem only includes some of the official IOI test points.

Problem Description

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.

Input Format

You need to implement the following function:

int construct_roads(std::vector<int> x, std::vector<int> 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:

void build(std::vector<int> u, std::vector<int> v, std::vector<int> a, std::vector<int> 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.

5
4 4
4 6
6 4
4 2
2 4

1
4
0 2 5 5
0 1 3 5
3 0 5 3
4 0 3 3

2
2 2
4 6

0

Hint

Example 1

Consider the following call:

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.

This plan corresponds to the figure below:

To report this plan, construct_roads should make the following call:

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:

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