P8374 [APIO2022] Mars

This problem only supports C++ submissions. You do not need to include the `mars.h` header when submitting; you only need to paste the contents of the attached `mars.h` at the beginning of your code. Please use C++14, C++17, etc., **not C++14 (GCC 9)**, because for some unknown reason the SPJ will cause a compilation error under that language setting. **[Note]: Luogu currently does not support the judging method described in the original statement. I implemented a simplified interactive library that Luogu supports, but it cannot effectively restrict the data being passed, so please follow the rules.**

As you know, the pharaohs were the first people to go to outer space. They launched the first spaceship that landed on the planet Thutmus I (now commonly called Mars). The surface of the planet can be modeled as a $(2n + 1) \times (2n + 1)$ grid of square cells, where each cell is either land or water. For the cell in row $i$ and column $j$ ($0 \le i, j \le 2 \cdot n$), if it is land, its state is denoted by $s[i][j] = \texttt{1}$; if it is water, it is denoted by $s[i][j] = \texttt{0}$. Two land cells are considered connected if there exists a path consisting only of land cells between them, and every pair of consecutive cells on the path shares a common edge. An island on the planet is defined as a maximal set of land cells such that every pair of cells in the set is connected. The spaceship’s mission is to count the number of islands on the planet. However, due to the spaceship’s ancient computer, this is not easy. The computer’s memory $h$ stores data as a $(2n + 1) \times (2n + 1)$ 2D array, and each position can store a string of length $100$, where each character is either $\texttt{0}$ (ASCII code $48$) or $\texttt{1}$ (ASCII code $49$). Initially, the $0$-th character of each memory cell records the corresponding grid cell state, i.e., $h[i][j][0] = s[i][j]$ (for all $0 \le i, j \le 2 \cdot n$). All other characters in $h$ are initially set to $\texttt{0}$ (ASCII code $48$). When processing the data in memory, the computer can only access a $3 \times 3$ block of memory and overwrite the value at the top-left position of that block. More formally, the computer can access the values in $h[i \dots i + 2][j \dots j + 2]$ ($0 \le i, j \le 2 \cdot (n - 1)$) and overwrite the value in $h[i][j]$. In what follows, this procedure is called **processing cell** $(i, j)$. To work around the computer’s limitations, the pharaohs use the following scheme: - The computer operates on the memory in $n$ stages. - In stage $k$ ($0 \le k \le n - 1$), let $m = 2 \cdot (n - k - 1)$. The computer will process all cells $(i, j)$ for $0 \le i, j \le m$, in increasing order of $i$, and for each fixed $i$ in increasing order of $j$. In other words, it processes the cells in the following order: $(0, 0), (0, 1),\cdots , (0, m), (1, 0), (1, 1),\cdots , (1, m),\cdots , (m, 0), (m, 1),\cdots , (m, m)$. - In the last stage ($k = n - 1$), the computer processes only cell $(0, 0)$. After this stage ends, the value written to $h[0][0]$ must equal the number of islands on the planet, represented in binary as a string, where the least significant bit corresponds to the first character of the string. The figures below show how the computer operates on a $5 \times 5$ ($n = 2$) memory. The blue cell is the cell being overwritten, and the shaded cells indicate the subarray being processed. In stage $0$, the computer processes the following subarrays in this order:  In stage $1$, the computer processes only one subarray:  Your task is to provide a method so that, under this fixed operation order, the computer can count the number of islands on planet Thutmus I. ## Implementation Details You need to implement the following function: ```cpp string process(string[][] a, int i, int j, int k, int n) ``` - $a$: a $3 \times 3$ array representing the subarray being processed. In particular, $a = h[i \dots i + 2][j \dots j + 2]$. Each element of $a$ is a string of length exactly $100$, and every character is $\texttt{0}$ (ASCII code $48$) or $\texttt{1}$ (ASCII code $49$). - $i, j$: the row and column indices of the cell currently being processed. - $k$: the index of the current stage. - $n$: the total number of stages, and also the size parameter of the planet surface; the surface contains $(2n + 1) \times (2n + 1)$ cells. - The function should return a binary string of length $100$. The return value will be stored in $h[i][j]$. - When $k = n - 1$, this is the last time the function is called. In this call, the function must return the binary representation of the number of islands as a string, where the least significant bit corresponds to the character at index $0$ (the first character of the binary string), the next bit corresponds to index $1$, and so on. - The function must be independent of any static or global variables, and its return value must depend only on the parameters passed to the function. Each test case contains $T$ independent scenarios (i.e., different planet surfaces). Your function’s behavior on each scenario must be independent of the order of the scenarios, because calls to `process` for the same scenario may not occur consecutively. However, it is guaranteed that for each scenario, `process` will be called in the order described above. In addition, for each test case, multiple instances of your program may run simultaneously. The memory limit and CPU time limit apply to the sum over all these instances. Any deliberate attempt to secretly pass data between these instances will be considered cheating, and contestants may be disqualified. **[Note]: Luogu currently does not support this judging method. I implemented a simplified interactive library that Luogu supports, but it cannot effectively restrict the data being passed, so please follow the rules.** In particular, information stored in static or global variables when `process` is called is not guaranteed to be readable in the next call.

The sample grader reads input in the following format: - Line $1$: $T$. - Block $i$ ($0 \le i \le T - 1$): this block describes scenario $i$. - Line $1$: $n$. - Line $2 + j$ ($0 \le j \le 2 \cdot n$): $s[j][0]\ s[j][1]\ \dots\ s[j][2 \cdot n]$.

The sample grader prints the result in the following format: - Line $1 + i$ ($0 \le i \le T - 1$): for scenario $i$, the decimal representation of the return value from the last call to `process`.

Translated by ChatGPT 5