Submission #21850851

---

Source Code Expand

import sys
import numpy as np
import numba
from numba import njit, b1, i1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

H = W = 50
K = 8

def from_read(dtype=np.int64):
    return np.fromstring(read().decode(), dtype=dtype, sep=' ')


def from_readline(dtype=np.int64):
    return np.fromstring(readline().decode(), dtype=dtype, sep=' ')

def gen_polyomino(n):
    if n == 1:
        yield ((0, 0), )
        return
    se = set(gen_polyomino(n - 1))
    dxdy = ((1, 0), (0, 1), (-1, 0), (0, -1))
    for P in se:
        me = set(P)
        for x, y in P:
            for dx, dy in dxdy:
                to = (x + dx, y + dy)
                if to in me:
                    continue
                Q = P + (to, )
                min_x = min(x for x, y in Q)
                min_y = min(y for x, y in Q)
                Q = ((x - min_x, y - min_y) for x, y in Q)
                Q = tuple(sorted(Q))
                yield Q

def output(ans):
    print(len(ans))
    ans = ans.reshape(-1, 2)
    for x, y in ans:
        print(x + 1, y + 1)

@njit((i8[:, :], i4[:, :, :]), cache=True)
def main(S, minos):
    # x, y, mino_type -> value
    T = len(minos)
    value, _n = np.empty((H * W * T, 4), np.int64), 0
    for x in range(H):
        for y in range(W):
            for t in range(T):
                prod = 1
                for k in range(K):
                    dx, dy = minos[t, k]
                    x1, y1 = x + dx, y + dy
                    if (not 0 <= x1 < H) or (not 0 <= y1 < W):
                        prod = 0
                        break
                    prod *= S[x1, y1]
                if prod:
                    value[_n], _n = (x, y, t, prod), _n + 1
    value = value[:_n]
    # print(_n)  2483788
    argsort = np.argsort(-value[:, 3])
    value = value[argsort]
    V = len(value)
    put = np.zeros((H, W), np.bool_)
    ans, _n = np.empty((H * W // K, K, 2), np.int64), 0
    for i in range(V):
        x, y, t, prod = value[i]
        ok = True
        for k in range(K):
            dx, dy = minos[t, k]
            if put[x + dx, y + dy]:
                ok = False
                break
        if ok:
            for k in range(K):
                dx, dy = minos[t, k]
                ans[_n, k] = (x + dx, y + dy)
                put[x + dx, y + dy] = 1
            _n += 1
    return ans[:_n]

from_readline()
S = np.empty((H, W), np.int64)
for h in range(H):
    S[h] = np.array(list(readline().rstrip())) - ord('0')

minos = np.array(list(set(gen_polyomino(K))), np.int32)

ans = main(S, minos)
output(ans)

Submission Info

Judge Result