P17273 [eJOI 2026] Automata

There is a field consisting of $N$ cells in a row, numbered $0$ to $N-1$ from left to right. Each cell has a distinct height: the height of cell $i$ is $p_i$, and the sequence $p_0,p_1,\ldots,p_{N-1}$ is a permutation of the numbers $0,1,\ldots,N-1$. Two cells with indices $i$ and $j$ are called close if and only if $|i-j|\le 1$. In particular, every cell is close to itself. A robot stands on the field, initially placed at some cell. The robot accepts commands of the following two types: - `MAX`: among all cells close to the robot's current cell, its next position is the unique cell with the maximum height; - `MIN`: among all cells close to the robot's current cell, its next position is the unique cell with the minimum height. Since a cell is close to itself, a command may leave the robot at the same cell. A program is a finite sequence of commands, where every command is either `MAX` or `MIN`. If the robot starts at cell $X$ and follows program $S$, it ends at a uniquely determined cell, denoted by $\operatorname{result}(S,X)$. You will be asked $Q$ queries. The $i$-th query gives a set of $K_i$ starting cells $x_0,x_1,\ldots,x_{K_i-1}$. The robot will be placed at one of them, but which one is not known in advance. For each query, determine whether there is a program that moves the robot to the same final cell regardless of the chosen starting position. Formally, determine whether there exists a program $S$ such that $\operatorname{result}(S,x_0)=\operatorname{result}(S,x_1)=\cdots=\operatorname{result}(S,x_{K_i-1}).$ The permutation $p$ is the same for all queries. You do not need to construct such a program; only report whether one exists. ### Implementation details Implement the following two functions: ```cpp void initialize(std::vector p) ``` - $p$: a permutation of the numbers from $0$ to $N-1$. ```cpp bool exists_program(std::vector x) ``` - $x$: the cells for one query, given in strictly increasing order. `initialize` is called exactly once, before any calls to `exists_program`. `exists_program` is called $Q$ times, once for each query. It must return `true` if there exists a program after which the robot ends at the same cell no matter which given cell it started from, and `false` otherwise.

Input format: - line $1$: two integers $N$ and $Q$; - line $2$: $N$ integers $p_0,p_1,\ldots,p_{N-1}$, where $p_i$ is the height of cell $i$; - line $3+i$: an integer $K_i$, followed by $K_i$ integers $x_0,x_1,\ldots,x_{K_i-1}$ describing the $i$-th query.

Output format: - line $1$: a binary string of length $Q$ whose $i$-th character is `1` if the answer to query $i$ is `true`, and `0` otherwise.

### Explanation of example 1 Here $p=[0,2,1]$. For the second query, the robot may start at cell $0$, $1$, or $2$. Consider the program $[\texttt{MAX}]$. - Starting at cell $0$, the close cells are $0$ and $1$. Since $p_0p_2$, the robot moves to cell $1$. Thus a program exists that ends at cell $1$ from all three starting cells, so the answer is `true`. Other valid programs include $[\texttt{MIN},\texttt{MAX}]$, $[\texttt{MIN},\texttt{MIN},\texttt{MAX},\texttt{MIN},\texttt{MAX},\texttt{MIN}]$, and $[\texttt{MAX},\texttt{MIN},\texttt{MAX}]$. ### Explanation of example 2 Here $p=[0,4,2,1,3,5,6]$. For the first two queries, no program can make the robot end at the same cell from every given starting cell, so both answers are `false`. For the last query, the robot may start at cell $3$ or $6$. Consider $[\texttt{MAX},\texttt{MAX},\texttt{MAX}]$. - Starting at cell $3$, the close cells are $2$, $3$, and $4$. Since $p_3