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:
def main():
    N = int( input())
    A = list( map(int, list( input())))
    P = [False]*N
    for i in range(N):
        if A[2**i] == 1:
            P[i] = True
    ans = True
    for x in range(2**N):
        now = True
        y = x
        for i in range(N):
            if y%2 == 1:
                if not P[i]:
                    now = False
                    break
            y //= 2
        if (A[x] == 1 and not now) or ( A[x] == 0 and now):
            ans = False
            break
    if ans:
        print("Possible")
    else:
        print("Impossible")
        return
    L = 0
    ANS = ["0 0"]

    for i in range(N):
        if not P[i]:
            ANS.append( str(i) + " " + str(1))
            ANS.append( str(i+1) + " " + str(1))
            ANS.append( str(i+1) + " " + str(0))
            L += 3
        else:
            ANS.append( str(i+1) + " " + str(0))
            L += 1
    for i in range(N):
        ANS.append( str(N-1-i) + " " + str(0))
        L += 1
    print(L)
    print("\n".join(ANS))
            
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
a = [c == "0" for c in input().rstrip()]

xs = [a[2**i] for i in range(N)]
bs = [False]
for x in xs:
    bs_add = [b or x for b in bs]
    bs = bs + bs_add
pos = all(a_ == b_ for a_, b_ in zip(a, bs))

if not pos:
    print("Impossible")
else:
    print("Possible")
    points = [(0, 0)]
    for i, x in enumerate(xs):
        if x:
            points.append((i, 1))
            points.append((i + 1, 1))
        points.append((i + 1, 0))
    for i in range(N):
        points.append((N - 1 - i, 0))
    print(len(points) - 1)
    for x, y in points:
        print(x, y)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = [c == "0" for c in input().rstrip()]

xs = [a[2**i] for i in range(N)]
bs = [False]
for x in xs:
    bs_add = [b or x for b in bs]
    bs = bs + bs_add
pos = a == bs

if not pos:
    print("Impossible")
else:
    print("Possible")
    points = [(0, 0)]
    for i, x in enumerate(xs):
        if x:
            points.append((i, 1))
            points.append((i + 1, 1))
        points.append((i + 1, 0))
    for i in range(N):
        points.append((N - 1 - i, 0))
    print(len(points) - 1)
    for x, y in points:
        print(x, y)

Submission status: Wrong Answer

Solution code:
print("Possible")
print(0)
print(1, 1)

Submission status: Wrong Answer

Solution code:
def rev(a):
    return [-v for v in a]

def make(s):
    assert len(s)>0
    pre_s = s[:-1]
    v = s[-1]
    if len(pre_s)==0:
        return [v]
    return make(pre_s) + [v] + rev(make(pre_s)) + [-v]

def make_pre_path(v):
    if v>0:
        return [(i,0) for i in range(1,v+1)] + [(v,1), (v-1,1)] + [(i,0) for i in range(v-1,0,-1)]
    elif v<0:
        return make_pre_path(-v)[::-1]
    assert False

def make_path(v):
    return make_pre_path(v)+[(0,0)]

def test():
    #print(make([1,2,3]))
    main("1","11")
    #main("8","1"+"0"*(2**8-1))

def main(s1,s2):
    ok = True
    n = int(s1)
    ret_gp = []
    for i in range(2**n-1,-1,-1):
        s = [v+1 for v in range(n) if (i>>v)%2==1 ]
        if s2[i]=="0":
            for ind in range(n):
                if (i>>ind)%2==0 and s2[(i+2**ind)]=="1":
                    ok = False
            ret_gp += make(s)
    ret_path = [(0,0)] + [p for v in ret_gp for p in make_path(v)]
    if ok:
        print("Possible")
        print(len(ret_path) - 1)
        for x,y in ret_path:
            print(str(x)+" "+str(y))
    else:
        print("Impossible")

s1 = raw_input()
s2 = raw_input()
main(s1,s2)

Submission status: Accepted

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

holes = []

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

print("Possible")
if len(holes) == 0:
    print(0)
    print(1, 1)
    exit()

clockwise = []

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)

m = len(holes)
roops = []

for i in range(m):
    x = holes[i]
    curve = []
    is_first = True
    for j in range(n):
        if (x >> j) & 1 and is_first:
            curve += clockwise[j]
            is_first = False
        elif (x >> j) & 1:
            curve = curve + clockwise[j] + curve[::-1] + clockwise[j][::-1]
    roops.append(curve)

ans = []
for x in roops:
    ans += x

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: Accepted

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
                cur = d + 1
            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: Accepted

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), nsmallest(len(tpg),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: Accepted

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

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

minimal_sets = []
for n in range(1<<N):
    s = n
    is_min = (A[n] == 0)
    while s:
        s = (s - 1) & n
        if A[n] == 1 and A[s] == 0:
            print('Impossible')
            exit()
        if A[s] == 0:
            is_min = False
    if is_min:
        minimal_sets.append(n)

def make(nums, x):
    if not nums:
        return [(x,0)]
    path = []
    if len(nums) == 1:
        n = nums[0]
        for i in range(x, n+1):
            path.append((i,0))
        path += [(n+1,0),(n+1,1),(n,1),(n,0)]
        for i in range(n-1,x-1,-1):
            path.append((i,0))
        return path
    n = nums[0]
    for i in range(x, n+1):
        path.append((i,0))
    P = make(nums[1:], n+1)
    path += P
    path += [(n,0), (n,1), (n+1,1), (n+1, 0)]
    path += P[::-1][1:]
    path += [(n+1,1), (n,1), (n,0)]
    for i in range(n-1,x-1,-1):
        path += [(i,0)]
    return path

path = [(0,0)]
for n in minimal_sets:
    path += make([i for i in range(N) if n & (1<<i)], 0)[1:]

print('Possible')
print(len(path) - 1)
print('\n'.join('{} {}'.format(x,y) for x,y in path))

Submission status: Accepted

Solution code:
def rev(a):
    return [-v for v in a[::-1]]

def make(s):
    assert len(s)>0
    pre_s = s[:-1]
    v = s[-1]
    if len(pre_s)==0:
        return [v]
    return make(pre_s) + [v] + rev(make(pre_s)) + [-v]

def make_pre_path(v):
    if v>0:
        return [(i,0) for i in range(1,v+1)] + [(v,1), (v-1,1)] + [(i,0) for i in range(v-1,0,-1)]
    elif v<0:
        return make_pre_path(-v)[::-1]
    assert False

def make_path(v):
    return make_pre_path(v)+[(0,0)]

def test():
    #print(make([1,2,3]))
    main("3","11111110")
    #main("8","1"+"0"*(2**8-1))

def main(s1,s2):
    ok = True
    n = int(s1)
    ret_gp = []
    for i in range(2**n-1,-1,-1):
        s = [v+1 for v in range(n) if (i>>v)%2==1 ]
        if s2[i]=="0":
            for ind in range(n):
                if (i>>ind)%2==0 and s2[(i+2**ind)]=="1":
                    ok = False
            if len(s)>0:
                ret_gp += make(s)
    ret_path = [(0,0)] + [p for v in ret_gp for p in make_path(v)]
    if 0:
        print(ret_gp)
    if ok:
        print("Possible")
        print(len(ret_path) - 1)
        for x,y in ret_path:
            print(str(x)+" "+str(y))
    else:
        print("Impossible")

#test()
        
s1 = raw_input()
s2 = raw_input()
main(s1,s2)

Submission status: Runtime Error

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:
  raise
  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: Runtime Error

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:
  raise ValueError

Submission status: Runtime Error

Solution code:
N = int(input())
a = [c == "0" for c in input().rstrip()]

xs = [a[2**i] for i in range(N)]
bs = [False]
for x in xs:
    bs_add = [b or x for b in bs]
    bs = bs + bs_add
pos = a == bs

if not pos:
    print("Impossible")
else:
    print("Possible")
    raise
    points = [(0, 0)]
    for i, x in enumerate(xs):
        if x:
            points.append((i, 1))
            points.append((i + 1, 1))
        points.append((i + 1, 0))
    for i in range(N):
        points.append((N - 1 - i, 0))
    print(len(points) - 1)
    for x, y in points:
        print(x, y)