• + 0 comments

    Really don't know, why this problem is listed under 'Number Theory'.
    To me it is plain linear algebra (e.g. Gauss elimination), in the boolean Field aka , $\mathbb{Z}_2 , wtf ...

    from itertools import chain
    from operator import xor
    
    def main():
        n, d = map(int, input().split())
        flatn = n*n
        inrange = lambda p1, p2: d >= sum(abs(a-b) 
    		            for a,b in zip(p1,p2) )
        to2d = lambda i: divmod(i, n) 
        board = [list(map(int,input().split())) for _ in range(n)]
        oparray = [ [inrange(base, pnt) 
                        for base in map(to2d, range(flatn))]
                    for pnt in map(to2d, range(flatn))]
        flatboard = list(chain(*(map(bool, row) for row in board)))
        result = gauss(oparray, flatboard)
        if result is None or len(result) == n:
            print('Impossible')
        else:
            print('Possible')
            print(len(result))
            for r in result: print(*to2d(r))
    
    def gauss(m, v):
        n = len(m)
        row = col = 0
        rank = []
        while row < n and col < n:
            for pivr in range(row, n):
                if m[pivr][col]:
                    break
            else:
                col += 1
                continue
            rank.append(col)
            if row != pivr: 
                m[row], m[pivr] = m[pivr], m[row]
                v[row], v[pivr] = v[pivr], v[row]
            for r in range(n):
                if r != row and m[r][col]:
                    m[r][col:] = map(xor, m[r][col:], m[row][col:])
                    v[r] ^= v[row]
            row += 1
            col += 1
        if sum(v[len(rank):]): return None
        return [r for r,vv in zip(rank, v) if vv]
             
    if __name__ == '__main__': 
        main()