LED

각 성분을 따로 생각한다. 한 번 갱신하면 성분은 가로와 세로로 각각 최대 한 칸 이동한다. 귀납적으로 $T$번 뒤 $(X,Y)$에 도달할 수 있는 초기 점은 정확히 $\max(|x_i-X|,|y_i-Y|)\leq T$를 만족한다. 필요성은 매초 좌표 차이를 최대 1만 줄일 수 있다는 사실에서 나온다. 충분성은 두 좌표를 동시에 목표 쪽으로 움직이고 남은 시간에는 제자리에 머무르면 된다. 해당 점들의 색을 비트 OR하면 된다. 시간 $O(N)$, 추가 공간 $O(1)$이다. 서브태스크 1은 맵에 성분을 저장하고 아홉 이웃으로 $T$번 전파하는 직접 시뮬레이션으로 해결한다. 시간 $O(TN(2T+1)^2\log(N(2T+1)^2))$이다. 좌표 차이의 최댓값은 $2\cdot10^6$, 성분 마스크는 최대 7이므로 64비트 정수 범위에 충분하다.

Solution written by GPT6.1