Submission #21852280

---

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
def trial(minos, data, unique_vals, LID, RID):
    put = np.zeros((H, W), np.bool_)
    ans, _n = np.empty((H * W // K, K, 2), np.int64), 0
    score = 0
    for i in range(len(unique_vals) - 1, -1, -1):
        x = unique_vals[i]
        IDS = np.arange(LID[i], RID[i])
        np.random.shuffle(IDS)
        for j in IDS:
            x, y, t, prod = data[j]
            ok = True
            for k in range(K):
                dx, dy = minos[t, k]
                if put[x + dx, y + dy]:
                    ok = False
                    break
            if ok:
                score += prod
                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 score, ans[:_n]

@njit
def calc_patterns(S, minos):
    T = len(minos)
    data, _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:
                    data[_n], _n = (x, y, t, prod), _n + 1
    data = data[:_n]
    argsort = np.argsort(data[:, 3])
    data = data[argsort]
    return data

@njit((i8[:, :], i4[:, :, :]), cache=True)
def main(S, minos):
    data = calc_patterns(S, minos)
    unique_vals = np.unique(data[:,3])
    LID = np.searchsorted(data[:,3], unique_vals)
    RID = np.searchsorted(data[:,3], unique_vals + 1)
    best_score = 0
    best_ans = None
    for _ in range(50):
        score, ans = trial(minos, data, unique_vals, LID, RID)
        if best_score < score:
            best_score = score
            best_ans = ans
    return best_ans

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