P6829 [IOI 2020] Plant Comparisons

**This is an interactive problem**. This problem only supports the C++ family of languages. You do not need to include the `plant.h` header file when submitting.

Botanist Hazel visited a special exhibition at the Singapore Botanic Gardens. In this exhibition, there are $n$ plants with **pairwise distinct** heights, arranged in a circle. The plants are numbered clockwise from $0$ to $n-1$, and plant $n-1$ is adjacent to plant $0$. For each plant $i\ (0 \le i \le n-1)$, Hazel compares it with the next $k-1$ plants in the clockwise direction, and records a value $r[i]$, which indicates how many of those $k-1$ plants are taller than plant $i$. Therefore, each value $r[i]$ is determined by the relative heights within some consecutive block of $k$ plants. For example, suppose $n=5$, $k=3$, and $i=3$. The next $k-1=2$ plants clockwise from plant $3$ are plants $4$ and $0$. If plant $4$ is taller than plant $3$, and plant $0$ is shorter than plant $3$, then Hazel records $r[3]=1$. You may assume that all the values $r[i]$ recorded by Hazel are correct. That is, there exists at least one set of pairwise distinct heights that matches Hazel’s recorded values. In this problem, you need to compare the heights of $q$ pairs of plants. Since you did not get to visit the exhibition, the only information you have is Hazel’s notebook, which contains $k$ and the sequence $r[0],\ldots, r[n-1]$. For each pair of plants $x$ and $y$ to be compared (with $x \ne y$), determine which of the following cases applies: - Plant $x$ is definitely taller than plant $y$: for any set of pairwise distinct heights $h[0],\ldots,h[n-1]$ that matches array $r$, we have $h[x] > h[y]$. - Plant $x$ is definitely shorter than plant $y$: for any set of pairwise distinct heights $h[0],\ldots,h[n-1]$ that matches array $r$, we have $h[x] < h[y]$. - The comparison is inconclusive: neither of the above two cases holds. #### Implementation Details You are required to implement the following functions: ```cpp void init(int k, std::vector r) ``` - $k$: the number of consecutive plants that determine each value $r[i]$. - $r$: an array of size $n$, where $r[i]$ is the number of plants among the next $k-1$ plants clockwise from plant $i$ that are taller than it. - This function is called exactly once, before any call to `compare_plants`. ```cpp int compare_plants(int x, int y) ``` - $x,y$: the indices of the plants to be compared. - This function should return: - $1$, if plant $x$ is definitely taller than plant $y$, - $-1$, if plant $x$ is definitely shorter than plant $y$, - $0$, if the comparison is inconclusive. - This function is called exactly $q$ times.

N/A

N/A

#### Sample Explanation #### Example 1 Consider the following call: ```cpp init(3, [0, 1, 1, 2]) ``` Suppose the grader calls `compare_plants(0, 2)`. From $r[0]=0$, we can conclude that plant $2$ is not taller than plant $0$, so this call should return $1$. Suppose the grader then calls `compare_plants(1, 2)`. Since for every set of plant heights satisfying the above conditions, plant $1$ is shorter than plant $2$, this call should return $-1$. #### Example 2 Consider the following call: ```cpp init(2, [0, 1, 0, 1]) ``` Suppose the grader calls `compare_plants(0, 3)`. From $r[3]=1$, we can conclude that plant $0$ is taller than plant $3$, so this call should return $1$. Suppose the grader then calls `compare_plants(1, 3)`. Two height assignments $[3,1,4,2]$ and $[3,2,4,1]$ both match Hazel’s observations. Since in the first case plant $1$ is shorter than plant $3$, while in the second case it is taller than plant $3$, this call should return $0$. #### Constraints - $2\le k\le n\le 200\ 000$. - $1\le q\le 200\ 000$. - $0 \le r[i]\le k-1$ (for all $0 \le i \le n-1$). - $0\le x n$. 3. (13 points) $2 \cdot k > n$. 4. (17 points) The correct answer to each `compare_plants` call is $1$ or $-1$. 5. (11 points) $n\le 300, q\le \frac{n\cdot (n-1)}{2}$. 6. (15 points) In each `compare_plants` call, $x=0$. 7. (25 points) No additional constraints. #### Example Grader The example grader reads the input in the following format: Line $1$: $n\ k\ q$ Line $2$: $r[0]\ r[1]\ \cdots\ r[n-1]$ Line $3+i\ (0\le i\le q-1)$: $x\ y$, representing the parameters of the $i$-th call to `compare_plants` The example grader prints your answers in the following format: Line $1+i\ (0\le i\le q-1)$: the return value of the $i$-th call to `compare_plants` Translated by ChatGPT 5