CF1446E Long Recovery

一位病人感染了一种未知疾病。他的身体可以看作是一个无限大的三角形格子，如下图所示：  如果两个格子共享一条边，则它们是相邻的。因此，每个格子 $(x, y)$ 恰好有三个相邻格子： - $(x+1, y)$ - $(x-1, y)$ - 如果 $x$ 为偶数，则为 $(x+1, y-1)$，否则为 $(x-1, y+1)$。 初始时有一些格子被感染，其余格子均为健康。随后开始恢复过程。每一秒，恰好有一个格子（即使有多个格子满足条件，也只选择其中一个）发生如下变化之一： - 一个健康格子如果有至少 $2$ 个相邻格子被感染，则也会被感染。 - 一个被感染的格子如果有至少 $2$ 个相邻格子是健康的，则也会变为健康。 如果不存在满足条件的格子，恢复过程就会停止。如果恢复过程停止且所有格子均为健康，则认为病人已经康复。 我们关注最坏情况：是否有可能病人永远无法康复？如果不可能，恢复过程最长可能持续多少秒？

第一行包含一个整数 $n$ $(1 \leq n \leq 250000)$，表示被感染的格子数量。 接下来的 $n$ 行，每行包含两个用空格分隔的整数 $x_i$ 和 $y_i$ $(0 \leq x_i, y_i < 500)$，表示格子 $(x_i, y_i)$ 被感染。所有 $(x_i, y_i)$ 互不相同，其余格子均为健康。

如果存在病人永远无法康复的情况，输出 SICK。否则，输出 RECOVERED，并在下一行输出一个整数 $k$，表示最长可能的恢复过程持续时间，对 $998244353$ 取模。

对于第一个测试用例，下图描述了最长的恢复过程。可以证明不存在长度为 $5$ 或更长的恢复过程，并且在此测试用例中病人总能康复。  $\hspace{40pt} \downarrow$  $\hspace{40pt} \downarrow$  $\hspace{40pt} \downarrow$  $\hspace{40pt} \downarrow$ $\hspace{15pt}$ RECOVERED 对于第二个测试用例，格子 $(2, 0)$、$(2, 1)$、$(0, 1)$ 可能被感染。此后，没有格子可以改变状态，因此答案为 SICK，因为并非所有格子都是健康的。 由 ChatGPT 4.1 翻译