Score : 1400 points
Given are a positive integer N and a sequence of length 2^N consisting of 0s and 1s: A_0,A_1,\ldots,A_{2^N-1}. Determine whether there exists a closed curve C that satisfies the condition below for all 2^N sets S \subseteq \{0,1,\ldots,N-1 \}. If the answer is yes, construct one such closed curve.
For instruction on printing a closed curve, see Output below.
C is said to be a closed curve if and only if:
We say that a closed curve C can be continuously moved without touching a set of points X so that it becomes a closed curve D if and only if:
Input is given from Standard Input in the following format:
N A_0A_1 \cdots A_{2^N-1}
If there is no closed curve that satisfies the condition, print Impossible
.
If such a closed curve exists, print Possible
in the first line.
Then, print one such curve in the following format:
L x_0 y_0 x_1 y_1 : x_L y_L
This represents the closed polyline that passes (x_0,y_0),(x_1,y_1),\ldots,(x_L,y_L) in this order.
Here, all of the following must be satisfied:
Additionally, the length of the closed curve L must satisfy 0 \leq L \leq 250000.
It can be proved that, if there is a closed curve that satisfies the condition in Problem Statement, there is also a closed curve that can be expressed in this format.
1 10
Possible 4 0 0 0 1 1 1 1 0 0 0
When S = \emptyset, we can move this curve so that every point on it has a negative y-coordinate.
When S = \{0\}, we cannot do so.
2 1000
Possible 6 1 0 2 0 2 1 1 1 0 1 0 0 1 0
The output represents the following curve:
2 1001
Impossible
1 11
Possible 0 1 1