Yet Another Contest 3 P5 - No More Thieves

Points: 25 (partial)

Time limit: 2.0s

Python 5.0s

Memory limit: 512M

Author:

Problem types

Mike is sick of the infamous RoboThieves who are always stealing treasure from him! So, he has set out on a mission to destroy all of the devious robots.

There are $N$ ~N~ RoboThieves hiding in distinct positions $(x_i, y_i)$ ~(x_i, y_i)~ on a 2-D cartesian plane, and Mike plans on using his special EMP device to disable them. Mike's device only has enough power to disable $N - X$ ~N - X~ robots, although he can disable any combination of $N - X$ ~N - X~ robots regardless of their positions. Luckily for him, the $X$ ~X~ remaining enabled robots can still be taken down via a strange mechanism.

Mike has discovered that the remaining robots have set up connections with each other. Through network $A$ ~A~, each enabled robot is connected to itself and its two closest enabled robots in terms of Euclidean distance. Through network $B$ ~B~, each enabled robot is connected to itself and its two closest enabled robots in terms of Manhattan distance. If there are ties in distances, then robots with lower indices are selected preferentially. Note that connections are one-way and direct; each robot is connected to exactly three robots in each network.

Furthermore, Mike has discovered that there is a special switch on each robot. For each enabled robot, Mike is able to travel to that robot and toggle its switch on or off. All of the remaining robots will become disabled if and only if each enabled robot is connected to exactly one robot that has its switch toggled on through network $A$ ~A~ and at least one robot that has its switch toggled off through network $B$ ~B~.

Can you help Mike find a way to disable all of the RoboThieves, or report that it is impossible to do so?

Note that for two points $(x_1, y_1)$ ~(x_1, y_1)~ and $(x_2, y_2)$ ~(x_2, y_2)~, the Euclidean distance between them is $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$ ~\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}~ and the Manhattan distance between them is $|x_1-x_2|+|y_1-y_2|$ ~|x_1-x_2|+|y_1-y_2|~.

Constraints

For this problem, you will NOT be required to pass ANY of the samples in order to receive points.

$N = 10^6$ ~N = 10^6~

$3 \le X \le 10^3$ ~3 \le X \le 10^3~

$-10^9 \le x_i, y_i \le 10^9$ ~-10^9 \le x_i, y_i \le 10^9~

All $N$ ~N~ points $(x_i, y_i)$ ~(x_i, y_i)~ are distinct.

Subtask 1 [10%]

$3 \le X \le 20$ ~3 \le X \le 20~

All $x_i$ ~x_i~ and $y_i$ ~y_i~ are generated uniformly at random.

Subtask 2 [20%]

$-500 \le x_i, y_i \le 500$ ~-500 \le x_i, y_i \le 500~

Subtask 3 [30%]

All $N$ ~N~ points $(x_i, y_i)$ ~(x_i, y_i)~ are on the boundary of the convex hull of all points.

Subtask 4 [40%]

No additional constraints.

Note that all previous subtasks must be passed for this subtask to be evaluated.

Input Specification

The first line contains two integers, $N$ ~N~ and $X$ ~X~.

The next $N$ ~N~ lines contain two integers $x_i$ ~x_i~ and $y_i$ ~y_i~, the coordinate location of the $i$ ~i~-th RoboThief's hiding spot.

Output Specification

If no solution exists, output -1 on a single line.

Otherwise, on a single line, output $N$ ~N~ space-separated characters where the $i$ ~i~-th character denotes the state of the $i$ ~i~-th robot. Exactly $N-X$ ~N-X~ characters should be X, denoting that the robot has been disabled initially. Each remaining character should either be 0 to denote that the robot's switch is turned off or 1 to denote that the robot's switch is turned on. The configuration should disable all $N$ ~N~ robots.

If there are multiple possible outputs, you may output any of them.

Sample Cases Note

Please note that the sample cases do not satisfy all of the constraints and are only provided to clarify the problem. Specifically, $N \ne 10^6$ ~N \ne 10^6~ in the sample cases. They will not appear in any of the test cases.

Sample Input 1

Sample Output 1

0 X 0 X X 0 1 1 X X

Explanation for Sample Output 1

After disabling robot $2$ ~2~, $4$ ~4~, $5$ ~5~, $9$ ~9~, and $10$ ~10~, Mike can choose to toggle the switch on robot $7$ ~7~ and $8$ ~8~. Below is a diagram of the situation with network $A$ ~A~ shown. Robots that were initially disabled are marked in gray, robots with their switch turned off are marked in red, and robots with their switch turned on are marked in green. Keep in mind that each enabled robot is also connected to itself for both networks.

$\text{[math]}$

Then, a diagram of the same situation with network $B$ ~B~ shown.

$\text{[math]}$

Notice that each remaining robot is connected to exactly one robot with its switch turned on in network $A$ ~A~ and at least one robot with its switch turned off in network $B$ ~B~. So, this is a valid way to disable all of the robots.

Sample Input 2

Sample Output 2

X 0 0 X 0 X 0 X X X 1 X 0 X X

Explanation for Sample Output 2

After disabling robot $1$ ~1~, $4$ ~4~, $6$ ~6~, $8$ ~8~, $9$ ~9~, $10$ ~10~, $12$ ~12~, $14$ ~14~, and $15$ ~15~, Mike can choose to only toggle the switch on robot $11$ ~11~. Again, a diagram of the situation with network $A$ ~A~ is shown below.

$\text{[math]}$

Then, a diagram of the same situation with network $B$ ~B~ shown.

$\text{[math]}$

Again, each remaining robot is connected to exactly one robot with its switch turned on in network $A$ ~A~, and at least one robot with its switch turned off in network $B$ ~B~. So, this is a valid way to disable all of the robots.

Comments

There are no comments at the moment.