P8167 [eJOI 2021] XCopy

Given positive integers $N, M$. Please construct an $N \times M$ matrix containing only non-negative integers, such that all elements are pairwise distinct, and any two adjacent (up, down, left, right) elements differ in exactly one bit in binary. Also, make the maximum element in the matrix as small as possible.

One line with two positive integers $N, M$.

Output an $N \times M$ matrix containing only non-negative integers. **The Special Judge is very strict about the output format: there must be no extra characters such as spaces at the end of each line.**

#### Scoring Rules This problem uses partial scoring. The score depends on the size of your output answer compared with the correct answer. Here, “answer” means the maximum element in the matrix. Let $S$ be the full score of this test point, and $O$ be the correct answer. If $G$ is your output answer, then the score is: $$S \times \max(1-\sqrt{\dfrac{\frac{G}{O}-1}{3}},0)$$ Because of Luogu’s scoring mechanism, the actual score for each test point is the floor of the above value, i.e. $\lfloor S \times \max(1-\sqrt{\dfrac{\frac{G}{O}-1}{3}},0) \rfloor$. For example, when $S=7, G=15, O=10$, the score by the formula is about $4.14$, but on Luogu the score is $4$. If the output matrix does not meet the requirements (i.e. all elements are distinct and any two adjacent elements differ by exactly one bit in binary), then this test point gets $0$ points. Note that, since the Special Judge has strict formatting requirements, please **do not add extra spaces at the end of each line** when printing your answer, otherwise the corresponding test point will be scored as $0$. Also, please do not output integers outside the range $[0,2^{63})$ (long long), otherwise it will be judged as a format error and scored as $0$. #### Sample Explanation The sample matrix is: |$0101_2=5_{10}$|$0100_2=4_{10}$|$0110_2=6_{10}$| | :----------: | :----------: | :----------: | |$0001_2=1_{10}$|$0000_2=0_{10}$|$0010_2=2_{10}$| |$1001_2=9_{10}$|$1000_2=8_{10}$|$1010_2=10_{10}$| It is easy to see that every pair of adjacent elements differs by exactly one bit in binary. The answer of this construction is $10$ (i.e. the maximum element), and it is the smallest among all valid constructions. Of course, other matrices with maximum element $10$ are also valid (for example, by flipping the matrix, etc.). A construction that can get partial points is: |$0110_2$|$0111_2$|$0101_2$| | :----------: | :----------: | :----------: | |$1110_2$|$1111_2$|$1101_2$| |$1010_2$|$1011_2$|$1001_2$| The maximum element of this matrix is $15$. According to the scoring rules, before flooring it can get $\max(1-\sqrt{\dfrac{\frac{15}{10}-1}{3}},0)=1-\dfrac{\sqrt{6}}{6} \approx 59\%$ of the score for this test point. #### Constraints and Notes **This problem uses bundled testdata.** - Subtask 1 (7 pts): $N=1$. - Subtask 2 (9 pts): $N, M$ are integer powers of $2$. - Subtask 3 (14 pts): $N$ is an integer power of $2$. - Subtask 4 (70 pts): no special restrictions. For $100\%$ of the data, $1 \le N, M \le 2000$. #### Notes This problem is translated from [eJOI2021](https://sepi.ro/ejoi/2021) Day 1 C XCopy. You are welcome to hack the self-written [Special Judge](https://www.luogu.com.cn/paste/cbrnaqp0) via private messages or forum posts. Translated by ChatGPT 5