题目类型说明

这是一道提交函数题 + 构造题 + 评分题。

原题要求你实现 4 个函数：

std::vector<int> getVisionPattern1d();
int getMove1d(std::vector<int> v);
std::vector<std::vector<int>> getVisionPattern2d();
std::pair<int, int> getMove2d(std::vector<std::vector<int>> v);

其中：

• getVisionPattern1d：返回一维周期模式；
• getMove1d：给定一维扫描结果，决定下一次传送到扫描序列中的哪个位置；
• getVisionPattern2d：返回二维周期模式；
• getMove2d：给定二维扫描结果，决定下一次传送到扫描矩阵中的哪个位置。

原题的评测并不是传统的“给定输入，输出唯一答案”，而是验证你的构造与策略是否始终合法，并按照平均视野强度给分。

---

题目描述

宇宙被看作一个无限大的二维网格。每个格子 (X, Y) 中都有一个信标，其视觉强度记为 V_{X,Y}。

当飞船位于 (X,Y) 时，会利用该格子的信标扫描所有满足：

$$X-V_{X,Y} \le X' \le X+V_{X,Y}$$ $$Y-V_{X,Y} \le Y' \le Y+V_{X,Y}$$

的格子，也就是说它能看到一个边长为 2V_{X,Y}+1 的正方形区域。

对每个被看到的格子，飞船只能获知其中信标的视觉强度。扫描完成后，飞船会传送到这个可见区域中的某个格子。

但是信标存在缺陷：扫描结果的 X 轴、Y 轴都可能被翻转，因此二维情况下共有 4 种可能朝向：

• 不翻转；
• 仅翻转 Y 轴；
• 仅翻转 X 轴；
• 两轴都翻转。

飞船必须根据“扫描到的内容”来决定传送位置，并且：

• 飞船没有记忆，决策只能依赖于当前扫描结果；
• 策略必须是确定性的，同样的扫描结果必须做出同样的选择。

飞船的初始坐标未知。无论它从哪里出发，也无论每一次扫描方向如何被翻转，飞船都必须能够不断向坐标增大的方向前进。更精确地说，最终必须总能到达某个满足：

$$X,Y\ge 10^{100}$$

的位置。

你需要设计一个会在整个宇宙中周期性重复的视觉强度模式，并设计飞船的移动策略。

二维版本

你需要构造一个 N × M 的矩阵 P，使得它无限重复：

$$V_{X,Y}=P_{X\bmod N,\,Y\bmod M}$$

同时还要设计飞船在扫描到某个正方形区域后如何决定下一步传送位置。

一维练习版本

为了降低难度，原题还给出了一个一维版本：只保留 Y 轴。

此时你需要构造长度为 M 的序列 P，使得：

$$V_Y=P_{Y\bmod M}$$

扫描结果是长度为 2V_Y+1 的序列；扫描方向只有两种：正常或翻转。飞船必须始终能到达某个满足：

$$Y\ge 10^{100}$$

的位置。

一维与二维部分分别计分，即使只完成其中一个，也能得到对应部分的分数。

注：原题中 X 表示行号（向下增大），Y 表示列号（向右增大）。

---

实现要求

1D 部分

std::vector<int> getVisionPattern1d()

该函数会在 1D 测试中被调用一次。你需要返回长度为 M 的序列 P，作为周期模式。M 以及 P 中每个元素都必须在 1..60 之间。

int getMove1d(std::vector<int> v)

该函数会在 1D 测试中针对每一种可能的扫描结果被调用一次。参数 v 是长度为 2V+1 的扫描序列，其中中间位置对应当前格子。你需要返回一个下标 T，表示传送到该扫描序列中的第 T 个位置，满足：

$$0 \le T < 2V+1$$

2D 部分

std::vector<std::vector<int>> getVisionPattern2d()

该函数会在 2D 测试中被调用一次。你需要返回一个 N × M 的矩阵 P，作为周期模式。N、M 以及矩阵中的所有元素都必须在 1..60 之间。

std::pair<int,int> getMove2d(std::vector<std::vector<int>> v)

该函数会在 2D 测试中针对每一种可能的扫描结果被调用一次。参数 v 是一个边长为 2V+1 的正方形矩阵，其中中心对应当前格子。你需要返回一对下标 (S,T)，表示传送到扫描矩阵中的位置，满足：

$$0 \le S,T < 2V+1$$

评测器会检查：在给定维度 D（1 或 2）下，你构造的模式是否合法，并且在任意起点、任意翻转序列下，飞船都能保证不断向正方向前进。

---

约束条件

• 1 <= D <= 2
• 1 <= N, M, V_{X,Y}, V_Y <= 60

---

子任务与评分

子任务	分值	维度 D	目标平均值 A^*
1	24	1	1.5
2	76	2	1.125

设你在某个子任务中构造出的模式 P 的平均视觉强度为 A，目标值为 A^*。若方案合法，则该子任务得到的分数比例为：

$$1-\left(1-\frac{A^*-1}{\max(A,A^*)-1}\right)^{0.8}$$

因此，模式越优，平均视觉强度越低，得分就越高。

---

样例模式说明

原题没有给出传统的样例输入输出，而是给出了一个二维模式示例：

当 N=3, M=2 时，假设你返回的模式为：

1 2
3 4
5 6

考察位置 (0,1)，其视觉强度为 2，则会产生边长为 5 的扫描矩阵。由于存在坐标翻转，可能出现 4 种方向，其中有些方向得到的扫描内容完全相同。

如果你的程序对其中一个扫描结果返回移动 (0,1)，那么在不同翻转方向下，它对应的真实位移方向也会不同；但由于传送和扫描使用的是同一套翻转方式，飞船最终总会到达它在扫描图中所选中的那个位置。

---

样例评测器说明

原题提供的 sample grader 仅用于交互式观察你的构造，不会自动证明你的方案正确。

它首先读入维度 D，随后调用你的构造函数与移动函数，缓存所有可能扫描结果下的决策；然后允许你手动输入飞船初始坐标，并逐步查看不同翻转方向下的扫描内容与飞船移动情况。