Infinite RGB Tiling

원점의 색은 빨간색이다. 나머지 칸은 $r=\max(|x|,|y|)$인 정사각형 테두리에 속한다. 색을 빨강 $0$, 초록 $1$, 파랑 $2$로 나타내자.

테두리의 위쪽 도미노를 왼쪽부터 $k=0,\ldots,r-1$로 번호 매기면 색은 $(r+k)\bmod3$이다. 오른쪽 도미노를 아래쪽부터 번호 매기면 색은 이다. 아래쪽과 왼쪽은 각각 위쪽과 오른쪽을 원점에 대해 도 회전한 색이다.

이 규칙은 $r=1$의 녹색 도미노와 빨간 원점에 일치한다. 각 도미노의 두 칸에는 같은 번호가 부여된다. 같은 테두리에서 인접한 도미노, 안쪽 테두리와 접하는 도미노, 네 모서리의 도미노를 비교하면 서로 다른 색이다. 이를 $k$의 홀짝과 $r$의 나머지에 따라 대입해 확인할 수 있다. 따라서 이 규칙은 지문의 모든 조건을 만족하며, 유일성에 의해 원하는 색칠이다.

위쪽 영역은 $y>0$, $-y\leq x<y$이며, $r=y$, $k$이다. 오른쪽 영역은 , 이며, , 이다. 아래쪽이나 왼쪽 영역이라면 먼저 를 로 바꾼다. 대각선 위의 칸을 어느 영역에 넣는지에 주의해야 한다.

각 칸을 $O(1)$에 계산한다. 총 출력 넓이를 $A$라 하면 시간 복잡도는 $O(T+A)$이고, 스트리밍 출력 시 추가 공간은 $O(1)$이다. 큰 좌표까지 격자를 만들면 안 된다.

서브태스크 1은 실제 도미노와 인접 그래프를 만든다. 원점과 첫 녹색 도미노의 색을 정하고, 이웃에서 서로 다른 두 색을 확인한 도미노의 색을 나머지 한 색으로 정하여 큐로 전파한다. 이 배치에서는 모든 색이 결정된다. 작은 테두리부터 확인하면, 각 새 테두리에서 안쪽의 두 색을 보는 도미노를 시작점으로 나머지가 강제된다. 반지름 $C$까지 $O(C^2)$ 시간과 공간으로 색칠하고, 질의는 출력 넓이만큼 처리한다. 제공한 naive는 색 공식을 사용하지 않는 이 방법이다.

좌표의 절댓값은 $10^{18}$ 이하이다. 정답 코드의 합은 $2\cdot10^{18}+1$ 이하이며, 독립 검증 코드의 선형식도 절댓값 $4\cdot10^{18}+1$ 이하이므로 signed 64-bit 정수로 충분하다. validator는 넓이를 곱하기 전에 나눗셈으로 한도를 검사한다.

Solution written by GPT6