| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 2048 MB | 39 | 7 | 6 | 60.000% |
В Сочи при подготовке Олимпиады-2014 была завезена самшитовая огнёвка (небольшая бабочка с Дальнего Востока). Она уничтожила самшитовую рощу, поэтому древесным лягушкам теперь приходится жить на болоте. Но они сохранили способность после прыжка менять свой цвет с зелёного на коричневый и наоборот.
Болото представляет собой плоскость, в некоторых точках которой располагаются кочки. Размером кочек можно пренебречь и считать их точками на плоскости. За один прыжок лягушка может перепрыгнуть с кочки, на которой она находится, на любую другую кочку, которая находится от неё на расстоянии не более $r$. После каждого прыжка цвет лягушки меняется на противоположный. Прыгать на месте лягушка не умеет.
Вам необходимо для каждой стартовой кочки лягушки от 1ドル$ до $n$ определить, может ли она, совершив некоторое количество прыжков, вернуться на стартовую кочку, поменяв при этом свой цвет.
Первая строка содержит два целых числа $n$ и $r$ (2ドル \le n \le 10^5,ドル $ 1 \le r \le 10^9$) --- число кочек на болоте и расстояние, на которое прыгает лягушка.
Каждая из следующих $n$ строк описывает расположение кочек. В $i$-й из них содержатся два целых числа $x_i$ и $y_i$ (0ドル \le x_i, y_i \le 5 \cdot 10^8$) --- координаты $i$-й кочки.
Никакие две кочки не располагаются в одной точке.
Выведите строку, состоящую из $n$ символов. Если лягушка, стартовав с кочки $i,ドル может вернуться на неё, имея противоположный цвет, $i$-й символ должен быть <<1>>, а иначе --- <<0>>.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 10 | $n \le 3$ |
| 2 | 20 | $n \le 200$ |
| 3 | 6 | $n \le 1,000円$ |
| 4 | 9 | $n \le 10,000円$ |
| 5 | 16 | $y_i = 0$ |
| 6 | 5 | $r \le 2$ |
| 7 | 5 | $r \le 4$ |
| 8 | 5 | $r \le 10$ |
| 9 | 12 | $(x_i - x_j)^2 + (y_i - y_j)^2 \ge \frac{r^2}{4},ドル $i \ne j$ |
| 10 | 12 |
6 5 4 1 4 4 1 5 5 9 9 6 10 2
111000
Прыжки, которые позволяют лягушке поменять цвет, начав с первой кочки, показаны на рисунке ниже.