Problem:


Score : 1400 points

Problem Statement

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.

Let x = \sum_{i \in S} 2^i and B_S be the set of points \{ (i+0.5,0.5) | i \in S \}.

If there is a way to continuously move the closed curve C without touching B_S so that every point on the closed curve has a negative y-coordinate, A_x = 1.

If there is no such way, A_x = 0.

For instruction on printing a closed curve, see Output below.

Notes

C is said to be a closed curve if and only if:

C is a continuous function from [0,1] to \mathbb{R}^2 such that C(0) = C(1).

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:

There exists a function f : [0,1] \times [0,1] \rightarrow \mathbb{R}^2 that satisfies all of the following.

f is continuous.

f(0,t) = C(t).

f(1,t) = D(t).

f(x,t) \notin X.

Constraints

1 \leq N \leq 8

A_i = 0,1 \quad (0 \leq i \leq 2^N-1)

A_0 = 1

Input

Input is given from Standard Input in the following format:

N
A_0A_1 \cdots A_{2^N-1}

Output

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:

0 \leq x_i \leq N, 0 \leq y_i \leq 1, and x_i, y_i are integers. (0 \leq i \leq L)

|x_i-x_{i+1}| + |y_i-y_{i+1}| = 1. (0 \leq i \leq L-1)

(x_0,y_0) = (x_L,y_L).

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.

Sample Input 1

1
10

Sample Output 1

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.

Sample Input 2

2
1000

Sample Output 2

Possible
6
1 0
2 0
2 1
1 1
0 1
0 0
1 0

The output represents the following curve:

Sample Input 3

2
1001

Sample Output 3

Impossible

Sample Input 4

1
11

Sample Output 4

Possible
0
1 1



Sample input:
1
10


Sample output:
Possible
4
0 0
0 1
1 1
1 0
0 0

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(x) for x in input()]

holes = []

for i in range(2**n-1, -1, -1):
    if a[i] == 0:
        continue
    for j in range(i+1):
        if (i | j) == i and a[j] == 0:
            print("Impossible")
            exit()
    if any((k | i) == k for k in holes):
        continue
    else:
        holes.append(i)

print("Possible")
if holes[0] == 2**n-1:
    print(0)
    print(0, 0)
    exit()

clockwise = []
anticlockwise = []

for i in range(n):
    locus = []
    for j in range(i+1):
        locus.append((j, 0))
    locus += [(i, 1), (i+1, 1), (i+1, 0)]
    for j in range(i, -1, -1):
        locus.append((j, 0))
    clockwise.append(locus)
    anticlockwise.append(locus[::-1])

m = len(holes)
roops = []

for i in range(m):
    x = holes[i] ^ (2**n-1)
    curve = []
    for j in range(n):
        if (x >> j) & 1:
            curve += clockwise[j]
    roops.append(curve)

m = len(roops)
ans = roops[0]

for i in range(1, m):
    ans = ans + roops[i] + ans[::-1] + roops[i][::-1]

L = -1
for i, x in enumerate(ans):
    if i > 0 and ans[i] == ans[i-1]:
        continue
    else:
        L += 1

print(L)
for i, x in enumerate(ans):
    if i > 0 and ans[i] == ans[i-1]:
        continue
    else:
        print(*x)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(x) for x in input()]

holes = []

for i in range(2**n-1, -1, -1):
    if a[i] == 0:
        continue
    for j in range(i+1):
        if (i | j) == i and a[j] == 0:
            print("Impossible")
            exit()
    if any((k | i) == k for k in holes):
        continue
    else:
        holes.append(i)

print("Possible")
if holes[0] == 2**n-1:
    print(0)
    print(0, 0)
    exit()

clockwise = []
anticlockwise = []

for i in range(n):
    locus = []
    for j in range(i+1):
        locus.append((j, 0))
    locus += [(i, 1), (i+1, 1), (i+1, 0)]
    for j in range(i, -1, -1):
        locus.append((j, 0))
    clockwise.append(locus)
    anticlockwise.append(locus[::-1])

roops = []

for x in holes:
    curve = []
    x ^= (2**n-1)
    for j in range(n):
        if (x >> j) & 1:
            curve += clockwise[j]
    roops.append(curve)

m = len(roops)
ans = roops[0]

for i in range(1, m):
    ans = ans + roops[i] + ans[::-1] + roops[i][::-1]

L = 0
for i, x in enumerate(ans):
    if i > 0 and ans[i] == ans[i-1]:
        continue
    else:
        L += 1

print(L)
for i, x in enumerate(ans):
    if i > 0 and ans[i] == ans[i-1]:
        continue
    else:
        print(*x)

Submission status: Wrong Answer

Solution code:
res = []

n = int(input())
a = [int(c) for c in input()]

def solve():
    if a[0] == 0:
        return False
    for x in range(1, 2**n):
        s = list(filter(lambda i: (x >> i) & 1, range(n)))
        xl = [(x >> i) & 1 for i in range(n)]
        if a[x] == 0:
            for d in s:
                y = x ^ (1 << d)
                if a[y] == 1:
                    break
            else:
                continue
            def move_ceiling(r, dest):
                i, j = r[-1]
                if i < dest:
                    for i in range(i, dest):
                        if xl[i] == 0 and j == 1:
                            r.append((i, 0))
                            j = 0
                        elif xl[i] == 1 and j == 0:
                            r.append((i, 1))
                            j = 1
                        r.append((i + 1, j))
                else:
                    for i in range(i, dest, -1):
                        if xl[i - 1] == 0 and j == 1:
                            r.append((i, 0))
                            j = 0
                        elif xl[i - 1] == 1 and j == 0:
                            r.append((i, 1))
                            j = 1
                        r.append((i - 1, j))
                return r
            def move_floor(r, dest):
                i, j = r[-1]
                if j == 1:
                    r.append((i, 0))
                for i in range(i + 1, dest + 1) if i < dest else range(i - 1, dest - 1, -1):
                    r.append((i, 0))
                return r
            r = [(s[0] + 1, 1), (s[0], 1), (s[0], 0), (s[0] + 1, 0)]
            cur = s[0] + 1
            for d in s[1:]:
                r0 = [(d + 1, 1)] if cur == d else move_ceiling([(d + 1, 1)], cur)
                r1 = move_ceiling(r.copy(), d + 1)
                r1 = move_floor(r1, cur)
                r1.pop()
                r2 = list(reversed(r))
                r2 = move_floor(r2, d + 1)
                r = r0 + r1 + r2
            r = move_floor(r, n)
            r.reverse()
            r = move_floor(r, n)
            r.pop()
            res.append(r)
        else:
            for d in s:
                y = x ^ (1 << d)
                if a[y] != 1:
                    return False
    return True

if __name__ == '__main__':
    if solve():
        print('Possible')
        r = [(i, j) for r in res for i, j in r]
        r.append((n, 0))
        print(len(r) - 1)
        for i, j in r:
            print(i, j)
    else:
        print('Impossible')

Submission status: Wrong Answer

Solution code:
res = []
def main():
    n = int(input())
    a = [int(c) for c in input()]
    
    if a[0] == 0:
        return False

    for x in range(1, 2**n):
        s = list(filter(lambda i: (x >> i) & 1, range(n)))
        xl = [(x >> i) & 1 for i in range(n)]
        if a[x] == 0:
            for d in s:
                y = x ^ (1 << d)
                if a[y] == 1:
                    break
            else:
                continue
            def move_ceiling(r, dest):
                i, j = r[-1]
                if i < dest:
                    for i in range(i, dest):
                        if xl[i] == 0 and j == 1:
                            r.append((i, 0))
                            j = 0
                        elif xl[i] == 1 and j == 0:
                            r.append((i, 1))
                            j = 1
                        r.append((i + 1, j))
                else:
                    for i in range(i, dest, -1):
                        if xl[i - 1] == 0 and j == 1:
                            r.append((i, 0))
                            j = 0
                        elif xl[i - 1] == 1 and j == 0:
                            r.append((i, 1))
                            j = 1
                        r.append((i - 1, j))
                return r
            def move_floor(r, dest):
                i, j = r[-1]
                if j == 1:
                    r.append((i, 0))
                for i in range(i + 1, dest + 1) if i < dest else range(i - 1, dest - 1, -1):
                    r.append((i, 0))
                return r
            u = move_ceiling([(0, 0)], s[0] + 1)
            l = move_floor([(0, 0)], s[0] + 1)
            cur = s[0] + 1
            for d in s[1:]:
                u = move_ceiling(u, d + 1)
                u = move_floor(u, cur)
                u = move_ceiling(u, s[0])
                u = move_floor(u, d + 1)
                l = move_ceiling(l, d + 1)
                u, l = l, u
                cur = d + 1
            l.reverse()
            l.pop()
            res.append(u + l)
        else:
            for d in s:
                y = x ^ (1 << d)
                if a[y] != 1:
                    return False
    return True

if __name__ == '__main__':
    if main():
        print('Possible')
        r = [(i, j) for r in res for i, j in r]
        r.append((0, 0))
        print(len(r) - 1)
        for i, j in r:
            print(i, j)
    else:
        print('Impossible')

Submission status: Wrong Answer

Solution code:
res = []
def main():
    n = int(input())
    a = [int(c) for c in input()]
    
    if a[0] == 0:
        return False

    for x in range(1, 2**n):
        s = list(filter(lambda i: (x >> i) & 1, range(n)))
        xl = [(x >> i) & 1 for i in range(n)]
        if a[x] == 0:
            def move_ceiling(r, dest):
                i, j = r[-1]
                if i < dest:
                    for i in range(i, dest):
                        if xl[i] == 0:
                            if j == 1:
                                r.append((i, 0))
                                j = 0
                            r.append((i + 1, 0))
                        else:
                            if j == 0:
                                r.append((i, 1))
                                j = 1
                            r.append((i + 1, 1))
                else:
                    for i in range(i, dest, -1):
                        if xl[i - 1] == 0:
                            if j == 1:
                                r.append((i, 0))
                                j = 0
                            r.append((i - 1, 0))
                        else:
                            if j == 0:
                                r.append((i, 1))
                                j = 1
                            r.append((i - 1, 1))
                return r
            def move_floor(r, dest):
                i, j = r[-1]
                if j == 1:
                    r.append((i, 0))
                for i in range(i + 1, dest + 1) if i < dest else range(i - 1, dest - 1, -1):
                    r.append((i, 0))
                return r
            u = move_ceiling([(0, 0)], s[0] + 1)
            l = move_floor([(0, 0)], s[0] + 1)
            cur = s[0] + 1
            for d in s[1:]:
                u = move_ceiling(u, d + 1)
                u = move_floor(u, cur)
                u = move_ceiling(u, s[0])
                u = move_floor(u, d + 1)
                l = move_ceiling(u, d + 1)
                u, l = l, u
                cur = d + 1
            l.reverse()
            l.pop()
            res.append(u + l)
        else:
            for d in s:
                y = x ^ (1 << d)
                if a[y] != 1:
                    return False
    return True

if __name__ == '__main__':
    if main():
        print('Possible')
        r = [(i, j) for r in res for i, j in r]
        r.append((0, 0))
        print(len(r) - 1)
        for i, j in r:
            print(i, j)
    else:
        print('Impossible')

Submission status: Wrong Answer

Solution code:
res = []
def main():
    n = int(input())
    a = [int(c) for c in input()]
    
    if a[0] == 0:
        return False

    for x in range(1, 2**n):
        s = list(filter(lambda i: (x >> i) & 1, range(n)))
        xl = [(x >> i) & 1 for i in range(n)]
        if a[x] == 0:
            def move_ceiling(r, dest):
                i, j = r[-1]
                if i < dest:
                    for i in range(i, dest):
                        if xl[i] == 0:
                            if j == 1:
                                r.append((i, 0))
                                j = 0
                            r.append((i + 1, 0))
                        else:
                            if j == 0:
                                r.append((i, 1))
                                j = 1
                            r.append((i + 1, 1))
                else:
                    for i in range(i, dest, -1):
                        if xl[i - 1] == 0:
                            if j == 1:
                                r.append((i, 0))
                                j = 0
                            r.append((i - 1, 0))
                        else:
                            if j == 0:
                                r.append((i, 1))
                                j = 1
                            r.append((i - 1, 1))
                return r
            def move_floor(r, dest):
                i, j = r[-1]
                if j == 1:
                    r.append((i, 0))
                for i in range(i + 1, dest + 1) if i < dest else range(i - 1, dest - 1, -1):
                    r.append((i, 0))
                return r
            u = move_ceiling([(0, 0)], s[0] + 1)
            l = move_floor([(0, 0)], s[0] + 1)
            cur = s[0] + 1
            for d in s[1:]:
                u = move_ceiling(u, d + 1)
                u = move_floor(u, cur)
                u = move_ceiling(u, 0)
                u = move_floor(u, d + 1)
                l = move_ceiling(u, d + 1)
                u, l = l, u
            l.reverse()
            l.pop()
            res.append(u + l)
        else:
            for d in s:
                y = x ^ (1 << d)
                if a[y] != 1:
                    return False
    return True

if __name__ == '__main__':
    if main():
        print('Possible')
        r = [(i, j) for r in res for i, j in r]
        r.append((0, 0))
        print(len(r) - 1)
        for i, j in r:
            print(i, j)
    else:
        print('Impossible')

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [1 - int(c) for c in input()]

s = [a[1 << i] for i in range(n)]

for x in range(2 ** n):
    t = any(s[i] for i in filter(lambda i: (x >> i) & 1, range(n)))
    if a[x] != t:
        possible = False
        break
else:
    possible = True

if possible:
    print('Possible')
    res = [(0, 0)]
    for i in range(n):
        if s[i]:
            res.append((i, 1))
            res.append((i+1, 1))
        res.append((i+1, 0))
    for i in range(n - 1, -1, -1):
        res.append((i, 0))
    print(len(res) - 1)
    for x, y in res:
        print(x, y)
else:
    print('Impossible')

Submission status: Wrong Answer

Solution code:
import sys
from heapq import *

def first_1(x):
  if x:
    i = 0
    while x & 1 == 0:
      x >>= 1
      i += 1
    return i

def sep_single(s):
  if s:
    r = 1 << (s.bit_length()-1)
    i = s.bit_length()-1
    while s:
      if r & s:
        yield -i, r
        s ^= r
      r >>= 1
      i -= 1

def prepare_to_right(g, x):
  x0, y0 = g[-1]
  if x0 < x and y0:
    y0 = 0
    g.append((x0, 0))
  while x0 < x:
    x0 += 1
    g.append((x0, 0))

def prepare_to_left(g, x):
  x0, y0 = g[-1]
  if x+1 < x0 and y0:
    y0 = 0
    g.append((x0, 0))
  while x+1 < x0:
    x0 -= 1
    g.append((x0, 0))

def append_to_right(g, x, y):
  prepare_to_right(g, x)
  x0, y0 = g[-1]
  if y != y0:
    g.append((x, y))
  g.append((x+1, y))

def subloop_tp_group(g):
  x = 0
  while g&1 == 0:
   g >>= 1
   x += 1
  loop = [(x+1, 0)]
  tail = [(x, 0), (x, 1), (x+1, 1)]
  g >>= 1
  x += 1
  while g:
    while g&1==0:
      g >>= 1
      x += 1
    prepare_to_right(loop, x)
    prepare_to_right(tail, x)
    rev = reversed(loop)
    append_to_right(loop, x, 1)
    loop.append((x+1, 0))
    loop.extend(rev)
    loop.extend(tail)
    append_to_right(loop, x, 0)
    append_to_right(tail, x, 1)
    g >>= 1
    x += 1
  loop.extend(reversed(tail))
  return loop

N = int(input())

single = 0
tpg = []
for i in range(1<<N):
  a = int(sys.stdin.read(1))
  if bin(i).count("1") == 1:
    if a == 0:
      single |= i
  else:
    b = i & single
    if i and b | a == 0 and all(p & i != p for n, p in tpg):
      heappush(tpg, (-first_1(i), i))
    elif i | a == 0 or a and (b or any(p & i == p for n, p in tpg)):
      print("Impossible")
      break
else:
  print("Possible")
  loop = []
  for n, g in merge(sep_single(single), tpg):
    subloop = subloop_tp_group(g)
    if loop:
      prepare_to_left(loop, subloop[0][0])
      if loop[-1] == subloop[0]:
        loop.pop()
    loop.extend(subloop)
  
  if not loop:
    loop.append((0, 0))
  prepare_to_right(loop, loop[0][0])
  
  print(len(loop)-1)
  for p in loop:
    print(*p)

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())

on = 0
for i in range(1<<N):
  a = int(sys.stdin.read(1))
  if bin(i).count("1") == 1 and not a:
    on |= i
else:
  print("Possible")
  x = 0
  while on and on & 1 == 0:
    x += 1
    on >>= 1
  init = x
  prev = 0
  P = [(x, prev)]
  while on:
    b = on & 1
    if prev != b:
      P.append((x, b))
    x += 1
    P.append((x, b))
    prev = b
    on >>= 1
  for x in range(x+prev-1, init-1, -1):
    P.append((x, 0))
  print(len(P)-1)
  for p in P:
    print(*p)

Submission status: Wrong Answer

Solution code:
print("Impossible")

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())

on = 0
for i in range(1<<N):
  a = int(sys.stdin.read(1))
  if bin(i).count("1") == 1 and not a:
    on |= i
  if not a ^ bool(i & on):
    print("Impossible")
    break
else:
  print("Possible")
  x = 0
  while on and on & 1 == 0:
    x += 1
    on >>= 1
  init = x
  prev = 0
  P = [(x, prev)]
  while on:
    b = on & 1
    if prev != b:
      P.append((x, b))
    x += 1
    P.append((x, b))
    prev = b
    on >>= 1
  for x in range(x+prev-1, init-1, -1):
    P.append((x, 0))
  print(len(P)-1)
  for p in P:
    print(*p)

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())

on = 0
for i in range(1<<N):
  a = int(sys.stdin.read(1))
  if bin(i).count("1") == 1 and not a:
    on |= i
  if not a ^ bool(i & on):
    print("Impossible")
    break
else:
  print("Possible")
  prev = 0
  x = 0
  P = [(x, prev)]
  while on:
    b = on & 1
    if prev != b:
      P.append((x, b))
    x += 1
    P.append((x, b))
    prev = b
    on >>= 1
  for x in range(x+prev-1, -1, -1):
    P.append((x, 0))
  print(len(P)-1)
  for p in P:
    print(*p)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

def solve(A):
    H,N = A.shape
    if N == 1:
        if np.all(A == 0):
            return np.array([1], np.int64)
        else:
            return np.array([0], np.int64)
    while True:
        if np.all(A[:,0] == 0):
            vals = solve(A[:,1:])
            return np.concatenate([[np.abs(vals).sum() + 1], vals])
        d = 10 ** 18
        h = 0
        for i in range(H):
            if A[i,0] < 0:
                A[i] *= -1 
            if d > A[i,0] > 0:
                d = A[i,0]
                h = i
        temp = A[0].copy()
        A[0] = A[h]
        A[h] = temp
        if np.count_nonzero(A[:,0]) == 1:
            vals = solve(A[1:,1:])
            vals *= d
            x = np.dot(vals, A[0,1:])
            return np.concatenate([[-x//d], vals])
        q = A[1:,0] // d
        A[1:] -= q[:,None] * A[0][None,:]

N = int(readline())
A = list(map(int,readline().rstrip().decode()))

N,A

eqs = []
for i in range(1<<N):
    if A[i]:
        eqs.append([1 if (i>>n)&1 else 0 for n in range(N)])

eqs = np.array(eqs, np.int64)

vals = solve(eqs)

for i in range(1<<N):
    S = sum(vals[j] for j in range(N) if (i>>j)&1)
    if S == 0 and A[i] == 0:
        print('Impossible')
        exit()

def output(vals):
    pts = []
    for n,x in enumerate(vals):
        pts.append([n,0])
        positive = [[n+1,0],[n+1,1],[n,1],[n,0]]
        negative = [[n,1],[n+1,1],[n+1,0],[n,0]]
        if x > 0:
            pts += positive * x
        if x < 0:
            pts += negative * (-x)
    pts.append([N,0])
    for n in range(N-1,0,-1):
        pts.append([n,0])
    pts.append([0,0])
    print('Possible')
    print(len(pts) - 1)
    print('\n'.join('{} {}'.format(x,y) for x,y in pts))

output(vals)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

def solve(A):
    H,N = A.shape
    if N == 1:
        if np.all(A == 0):
            return np.array([1], np.int64)
        else:
            return np.array([0], np.int64)
    while True:
        if np.all(A[:,0] == 0):
            vals = solve(A[:,1:])
            return np.concatenate([[np.abs(vals).sum() + 1], vals])
        d = 10 ** 18
        h = 0
        for i in range(H):
            if A[i,0] < 0:
                A[i] *= -1 
            if d > A[i,0] > 0:
                d = A[i,0]
                h = i
        temp = A[0].copy()
        A[0] = A[h]
        A[h] = temp
        if np.count_nonzero(A[:,0]) == 1:
            vals = solve(A[1:,1:])
            vals *= d
            x = np.dot(vals, A[0,1:])
            return np.concatenate([[-x//d], vals])
        q = A[1:,0] // d
        A[1:] -= q[:,None] * A[0][None,:]

N = int(readline())
A = list(map(int,readline().rstrip().decode()))

N,A

eqs = []
for i in range(1<<N):
    if A[i]:
        eqs.append([1 if (i>>n)&1 else 0 for n in range(N)])

eqs = np.array(eqs, np.int64)

vals = solve(eqs)

for i in range(1<<N):
    S = sum(vals[j] for j in range(N) if (i>>j)&1)
    if S == 0 and A[i] == 0:
        print('Impossible')
        exit()

def output(vals):
    pts = []
    for n,x in enumerate(vals):
        pts.append([n,0])
        positive = [[n+1,0],[n+1,1],[n,1],[n,0]]
        negative = [[n,1],[n+1,1],[n+1,0],[n,0]]
        if x > 0:
            pts += positive * x
        if x < 0:
            pts += negative * (-x)
    pts.append([N,0])
    pts.append([N,-1])
    for n in range(N-1,0,-1):
        pts.append([n,-1])
    pts.append([0,-1])
    pts.append([0,0])
    print('Possible')
    print(len(pts) - 1)
    print('\n'.join('{} {}'.format(x,y) for x,y in pts))

output(vals)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

def solve(A):
    H,N = A.shape
    if N == 1:
        if np.all(A == 0):
            return np.array([1], np.int64)
        else:
            return np.array([0], np.int64)
    while True:
        if np.all(A[:,0] == 0):
            vals = solve(A[:,1:])
            return np.concatenate([[np.abs(vals).sum() + 1], vals])
        d = 10 ** 18
        h = 0
        for i in range(H):
            if A[i,0] < 0:
                A[i] *= -1 
            if d > A[i,0] > 0:
                d = A[i,0]
                h = i
        temp = A[0].copy()
        A[0] = A[h]
        A[h] = temp
        if np.count_nonzero(A[:,0]) == 1:
            vals = solve(A[1:,1:])
            vals *= d
            x = np.dot(vals, A[0,1:])
            return np.concatenate([[-x//d], vals])
        q = A[1:,0] // d
        A[1:] -= q[:,None] * A[0][None,:]

N = int(readline())
A = list(map(int,readline().rstrip().decode()))

N,A

eqs = []
for i in range(1<<N):
    if A[i]:
        eqs.append([1 if (i>>n)&1 else 0 for n in range(N)])

eqs = np.array(eqs, np.int64)

vals = solve(eqs)

for i in range(1<<N):
    S = sum(vals[j] for j in range(N) if (i>>j)&1)
    if S == 0 and A[i] == 0:
        print('Impossible')
        exit()

def output(vals):
    pts = []
    for n,x in enumerate(vals):
        pts.append([n,0])
        positive = [[n+1,0],[n+1,n+1],[n,n+1],[n,0]]
        negative = [[n,n+1],[n+1,n+1],[n+1,0],[n,0]]
        if x > 0:
            pts += positive * x
        if x < 0:
            pts += negative * (-x)
    pts.append([N,0])
    pts.append([N,-1])
    pts.append([0,-1])
    pts.append([0,0])
    print('Possible')
    print(len(pts) - 1)
    print('\n'.join('{} {}'.format(x,y) for x,y in pts))

output(vals)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

def solve(A):
    H,N = A.shape
    if N == 1:
        if np.all(A == 0):
            return np.array([1], np.int64)
        else:
            return np.array([0], np.int64)
    while True:
        if np.all(A[:,0] == 0):
            vals = solve(A[:,1:])
            return np.concatenate([[np.abs(vals).sum() + 1], vals])
        d = 10 ** 18
        h = 0
        for i in range(H):
            if A[i,0] < 0:
                A[i] *= -1 
            if d > A[i,0] > 0:
                d = A[i,0]
                h = i
        temp = A[0].copy()
        A[0] = A[h]
        A[h] = temp
        if np.count_nonzero(A[:,0]) == 1:
            vals = solve(A[1:,1:])
            vals *= d
            x = np.dot(vals, A[0,1:])
            return np.concatenate([[-x//d], vals])
        q = A[1:,0] // d
        A[1:] -= q[:,None] * A[0][None,:]

N = int(readline())
A = list(map(int,readline().rstrip().decode()))

N,A

eqs = []
for i in range(1<<N):
    if A[i]:
        eqs.append([1 if (i>>n)&1 else 0 for n in range(N)])

eqs = np.array(eqs, np.int64)

vals = solve(eqs)

for i in range(1<<N):
    S = sum(vals[j] for j in range(N) if (i>>j)&1)
    if S == 0 and A[i] == 0:
        print('Impossible')
        exit()

def output(vals):
    pts = []
    for n,x in enumerate(vals):
        pts.append([n,0])
        positive = [[n+1,0],[n+1,n+1],[n,n+1],[n,0]]
        negative = [[n,n+1],[n+1,n+1],[n+1,0],[n,0]]
        if x > 0:
            pts += positive * x
        if x < 0:
            pts += negative * (-x)
    pts.append([N,0])
    pts.append([N,-1])
    pts.append([0,-1])
    pts.append([0,0])
    print('Possible')
    print(len(pts))
    print('\n'.join('{} {}'.format(x,y) for x,y in pts))

output(vals)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

def solve(A):
    H,N = A.shape
    if N == 1:
        if np.all(A == 0):
            return np.array([1], np.int64)
        else:
            return np.array([0], np.int64)
    while True:
        if np.all(A[:,0] == 0):
            vals = solve(A[:,1:])
            return np.concatenate([[np.abs(vals).sum() + 1], vals])
        d = 10 ** 18
        h = 0
        for i in range(H):
            if A[i,0] < 0:
                A[i] *= -1 
            if d > A[i,0] > 0:
                d = A[i,0]
                h = i
        temp = A[0].copy()
        A[0] = A[h]
        A[h] = temp
        if np.count_nonzero(A[:,0]) == 1:
            vals = solve(A[1:,1:])
            vals *= d
            x = np.dot(vals, A[0,1:])
            return np.concatenate([[-x//d], vals])
        q = A[1:,0] // d
        A[1:] -= q[:,None] * A[0][None,:]

N = int(readline())
A = list(map(int,readline().rstrip().decode()))

N,A

eqs = []
for i in range(1<<N):
    if A[i]:
        eqs.append([1 if (i>>n)&1 else 0 for n in range(N)])

eqs = np.array(eqs, np.int64)

vals = solve(eqs)

for i in range(1<<N):
    S = sum(vals[j] for j in range(N) if (i>>j)&1)
    if S == 0 and A[i] == 0:
        print('Impossible')
        exit()

def output(vals):
    pts = []
    for n,x in enumerate(vals):
        pts.append([n,0])
        positive = [[n+1,0],[n+1,n+1],[n,n+1],[n,0]]
        negative = [[n,n+1],[n+1,n+1],[n+1,0],[n,0]]
        if x > 0:
            pts += positive * x
        if x < 0:
            pts += negative * (-x)
    pts.append([N,0])
    pts.append([N,-1])
    pts.append([0,-1])
    pts.append([0,0])
    print('Possible')
    print('\n'.join('{} {}'.format(x,y) for x,y in pts))

output(vals)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

def solve(A):
    H,N = A.shape
    if N == 1:
        if np.all(A == 0):
            return np.array([1], np.int64)
        else:
            return np.array([0], np.int64)
    while True:
        if np.all(A[:,0] == 0):
            vals = solve(A[:,1:])
            return np.concatenate([[np.abs(vals).sum() + 1], vals])
        d = 10 ** 18
        h = 0
        for i in range(H):
            if A[i,0] < 0:
                A[i] *= -1 
            if d > A[i,0] > 0:
                d = A[i,0]
                h = i
        temp = A[0].copy()
        A[0] = A[h]
        A[h] = temp
        if np.count_nonzero(A[:,0]) == 1:
            vals = solve(A[1:,1:])
            vals *= d
            x = np.dot(vals, A[0,1:])
            return np.concatenate([[-x//d], vals])
        q = A[1:,0] // d
        A[1:] -= q[:,None] * A[0][None,:]

N = int(readline())
A = list(map(int,readline().rstrip().decode()))

N,A

eqs = []
for i in range(1<<N):
    if A[i]:
        eqs.append([1 if (i>>n)&1 else 0 for n in range(N)])

eqs = np.array(eqs, np.int64)

vals = solve(eqs)

for i in range(1<<N):
    S = sum(vals[j] for j in range(N) if (i>>j)&1)
    if S == 0 and A[i] == 0:
        print('Impossible')
        exit()

def output(vals):
    pts = []
    for n,x in enumerate(vals):
        pts.append([n,0])
        positive = [[n+1,0],[n+1,n+1],[n,n+1],[n,0]]
        negative = [[n,n+1],[n+1,n+1],[n+1,0],[n,0]]
        if x > 0:
            pts += positive * x
        if x < 0:
            pts += negative * (-x)
    pts.append([N,0])
    pts.append([N,1])
    pts.append([0,1])
    pts.append([0,0])
    print('Possible')
    print('\n'.join('{} {}'.format(x,y) for x,y in pts))

output(vals)