Infinite RGB Tiling

原点为红色。其余格子位于 $r=\max(|x|,|y|)$ 的正方形外圈上。将红、绿、蓝编码为 $0,1,2$。

将上边的骨牌从左到右编号为 $k=0,\ldots,r-1$，颜色为 $(r+k)\bmod3$。将右边的骨牌从下到上编号，颜色为 $(r+1+k)\bmod3$。下边和左边分别与上边和右边绕原点旋转 $180$ 度后的颜色相同。

此规则符合最初的绿色骨牌和红色原点。同一骨牌的两个格子得到同一颜色。分别检查同圈相邻骨牌、相邻两圈之间的骨牌以及四个角处的骨牌，按奇偶性及模三余数代入可知，不同的相邻图形颜色始终不同。因此该规则满足全部条件，由唯一性可知它就是所求染色。

上方区域为 $y>0$ 且 $-y\leq x<y$，此时 $r=y$，$k$。右方区域为 且 ，此时 ，。若位于下方或左方，先将 变为 。注意对角线上的严格不等号。

每个格子可在 $O(1)$ 时间内求出。设总输出面积为 $A$，则时间复杂度为 $O(T+A)$，逐行直接输出时额外空间为 $O(1)$。不能一直模拟到最大的坐标。

子任务 1 可以显式建立骨牌邻接图。固定原点与第一块绿色骨牌，用队列传播：当一个骨牌已有两种不同颜色的邻居时，它只能使用第三种颜色。在此布局中所有颜色都会确定。逐圈考虑，每一圈从接触内圈两种颜色的骨牌开始，其余颜色被依次确定。坐标上限为 $C$ 时，时间为 $O(C^2+A+T)$，空间为 $O(C^2+T)$。所附 naive 不使用颜色公式，而是采用此方法。

坐标绝对值不超过 $10^{18}$。主解法的表达式不超过 $2\cdot10^{18}+1$，独立解法的线性表达式绝对值不超过 $4\cdot10^{18}+1$，有符号 位整数足够。输入验证程序先用除法检查面积上限，再进行乘法。

Solution written by GPT6