P11357 [eJOI 2023] Square Grid Puzzle

There is an $N \times N$ matrix, whose elements are labeled from $0 \sim N^2 - 1$. We want to make the element in row $i$ and column $j$ become $i \cdot N + j$ using **fewer than** $3N$ operations. You can perform two kinds of operations on the matrix: - `D a[0] a[1] ... a[N-1]`: Rearrange the first row of the matrix, then cyclically shift each column upward by one. You must ensure that the given $a$ is a permutation of the first row of the matrix. - `R b[0] b[1] ... b[N-1]`: Rearrange the first column of the matrix, then cyclically shift each row leftward by one. You must ensure that the given $b$ is a permutation of the first column of the matrix. For example, if the current matrix is: |R/C|0|1|2| |:-:|:-:|:-:|:-:| |0|2|4|6| |1|8|1|5| |2|7|3|0| If we perform `D 2 6 4` on the original matrix, the matrix becomes: |R/C|0|1|2| |:-:|:-:|:-:|:-:| |0|8|1|5| |1|7|3|0| |2|**6**|**2**|**4**| If we perform `R 2 8 7` on the original matrix, the matrix becomes: |R/C|0|1|2| |:-:|:-:|:-:|:-:| |0|4|6|**2**| |1|1|5|**8**| |2|3|0|**7**| Even if you use $\geq 3N$ operations, or some numbers are not restored, you can still get partial score. See the **Scoring** section.

The first line contains an integer $N$. The next $N$ lines each contain $N$ integers $F_{i,j}$, representing the initial matrix.

The first line contains an integer $M$, representing the number of operations. The next $M$ lines each describe one operation, in the format given above.

**Scoring** Let $A = 3N$, $B = 2N^2$, and let $C$ be the number of positions that satisfy the requirement after the operations. If your program does not terminate normally, or the output format is wrong, or $M > B$, then you get $0$ points for this test point. Otherwise, if $C < N^2$, you get $50\% \cdot \frac{C}{N^2}$ of the score for this test point. Otherwise, if $A \leq M \leq B$, you get $(40 \cdot (\frac{B - M}{B - A})^2 + 50)\%$ of the score for this test point. Otherwise, you get the full score. **Sample Explanation** In the first sample, $4$ operations are used to restore the matrix, so you can get a score of $100\%$. In the second sample, $0$ operations are used to restore $\frac{2}{4} = 50\%$ of the positions, so you can get a score of $25\%$ for this test point. **Constraints** For $100\%$ of the testdata, it is guaranteed that $2 \leq N \leq 9$, and $N$ is uniformly distributed among the test points. Translated by ChatGPT 5