#P12506. 「ROI 2025 Day2」沼泽里的青蛙
「ROI 2025 Day2」沼泽里的青蛙
题目描述
译自 ROI 2025 Day2 T2. Лягушки на болоте
在索契筹备 2014 年奥运会时,意外引入了来自远东的小型蝴蝶——箱树蛾。它毁掉了当地的箱树林,迫使树蛙们搬到了沼泽里生活。不过,这些聪明的树蛙依然保留了它们的神奇本领:每次跳跃后,它们的颜色会在绿色和棕色之间切换。
沼泽是一片平面,上面散布着许多小土丘,可以看作平面上的点。青蛙一次跳跃可以从当前土丘跳到任何一个距离不超过 的其他土丘。跳跃后,青蛙的颜色会变成相反的颜色。需要注意的是,青蛙无法在原地跳跃。
你的任务是,对于从 到 的每个起始土丘,判断青蛙能否通过若干次跳跃回到这个土丘,并且在回到时颜色与初始时相反。
输入格式
第一行包含两个整数 和 ,分别表示沼泽中土丘的数量和青蛙的最大跳跃距离。
接下来的 行,每行包含两个整数 和 ,表示第 个土丘的坐标。
保证任意两个土丘的坐标不重合。
输出格式
输出一个长度为 的字符串,包含字符 0
或 1
。如果从第 个土丘开始的青蛙能回到该土丘且颜色相反,则第 个字符为 1
;否则为 0
。
6 5
4 1
4 4
1 5
5 9
9 6
10 2
111000
提示
样例解释
下图展示了从第一个土丘开始,青蛙通过跳跃改变颜色的路径:
详细子任务附加限制及分值如下表所示。其中子任务 是样例。
子任务 | 分值 | 附加限制 |
---|---|---|
样例 | ||
, | ||
无附加限制 |