Infinite RGB Tiling

The origin is red. Every other cell belongs to the square ring $r=\max(|x|,|y|)$. Encode red, green, and blue as $0,1,2$.

Number the top dominoes from left to right by $k=0,\ldots,r-1$. Their colors are $(r+k)\bmod3$. Number the right dominoes from bottom to top; their colors are $(r+1+k)\bmod3$. The bottom and left parts have the colors obtained by rotating the top and right parts by $180$ degrees about the origin.

This rule agrees with the initial green domino and red origin. Both cells of every domino receive the same value. Checking neighboring dominoes on one ring, across two consecutive rings, and at the four corners gives different colors in every case; this follows by substitution according to parity and residues modulo three. Thus the rule satisfies all conditions and, by uniqueness, is the required coloring.

The top region is $y>0$, $-y\leq x<y$. Here $r=y$ and $$. The right region is , , where and . Rotate a cell in the bottom or left region to first. The strict inequalities on the diagonals matter.

Each cell takes $O(1)$ time. For total output area $A$, the complexity is $O(T+A)$ time and $O(1)$ auxiliary space with streaming output. Do not build the grid out to the largest coordinate.

For subtask 1, explicitly build the domino adjacency graph. Fix the origin and the first green domino, then use a queue: a domino seeing two distinct neighbor colors must use the third color. All dominoes in this layout are determined. Ring by ring, propagation starts at a domino seeing two different inner colors and forces the rest. This takes $O(C^2+A+T)$ time and $O(C^2+T)$ space for coordinate bound . The provided naive uses this method without a color formula.

Absolute coordinates are at most $10^{18}$. Main-solution expressions are at most $2\cdot10^{18}+1$; the independent linear expressions have absolute value at most $4\cdot10^{18}+1$. Signed 64-bit arithmetic suffices. The validator checks area bounds using division before multiplying.

Solution written by GPT6