Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
from numba import njit
import numpy


def read():
    N = int(input().strip())
    line = input().strip()
    P = numpy.fromstring(line, dtype=numpy.int32, sep=" ")
    return N, P


@njit
def dfs(N, Q, stay, p, q):
    y, x = divmod(p, N)
    for dy, dx in ((0, 1), (1, 0), (-1, 0), (0, -1)):
        ny, nx = y + dy, x + dx
        if 0 <= ny < N and 0 <= nx < N:
            if Q[ny, nx] > q:
                Q[ny, nx] = q
                dfs(N, Q, stay, ny * N + nx, q + stay[ny, nx])


@njit
def np_solve(N, P, INF=10**9):
    P -= 1
    Q = numpy.empty((N, N), dtype=numpy.int32)
    stay = numpy.ones((N, N), dtype=numpy.bool_)
    
    for r in range(N//2+1):
        Q[r:N-r, r:N-r] = r

    ans = 0
    for p in P:
        y, x = divmod(p, N)
        stay[y, x] = 0
        q = Q[y, x]
        ans += q
        dfs(N, Q, stay, p, q)
    return ans


if __name__ == '__main__':
    outputs = np_solve(*read())
    if outputs is not None:
        print("{}".format(outputs))


Fixed submission:
import sys
input = sys.stdin.readline
from numba import njit
import numpy


def read():
    N = int(input().strip())
    line = input().strip()
    P = numpy.fromstring(line, dtype=numpy.int32, sep=" ")
    return N, P


@njit
def dfs(N, Q, stay, p, q):
    y, x = divmod(p, N)
    for dy, dx in ((0, 1), (1, 0), (-1, 0), (0, -1)):
        ny, nx = y + dy, x + dx
        if 0 <= ny < N and 0 <= nx < N:
            np = ny * N + nx
            if Q[np] > q:
                Q[np] = q
                dfs(N, Q, stay, np, q + stay[np])


@njit
def np_solve(N, P, INF=10**9):
    P -= 1
    Q = numpy.empty(N*N, dtype=numpy.int32)
    stay = numpy.ones(N*N, dtype=numpy.bool_)
    
    for i in range(N):
        for j in range(N):
            Q[i*N+j] = min([i, j, N-i-1, N-j-1])

    ans = 0
    for p in P:
        stay[p] = 0
        q = Q[p]
        ans += q
        dfs(N, Q, stay, p, q)
    return ans


if __name__ == '__main__':
    outputs = np_solve(*read())
    if outputs is not None:
        print("{}".format(outputs))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
from numba import njit
import numpy


def read():
    N = int(input().strip())
    line = input().strip()
    P = numpy.fromstring(line, dtype=numpy.int32, sep=" ")
    return N, P


@njit
def dfs(N, Q, stay, y, x, q):
    for dy, dx in ((0, 1), (1, 0), (-1, 0), (0, -1)):
        ny, nx = y + dy, x + dx
        if 0 <= ny < N and 0 <= nx < N:
            if Q[ny, nx] > q:
                Q[ny, nx] = q
                dfs(N, Q, stay, ny, nx, q + stay[ny, nx])


@njit
def np_solve(N, P, INF=10**9):
    P -= 1
    Q = numpy.empty((N, N), dtype=numpy.int32)
    stay = numpy.ones((N, N), dtype=numpy.bool_)
    
    for r in range(N//2+1):
        Q[r:N-r, r:N-r] = r

    ans = 0
    for p in P:
        y, x = divmod(p, N)
        stay[y, x] = 0
        q = Q[y, x]
        ans += q
        dfs(N, Q, stay, y, x, q)
    return ans


if __name__ == '__main__':
    outputs = np_solve(*read())
    if outputs is not None:
        print("{}".format(outputs))


Fixed submission:
import sys
input = sys.stdin.readline
from numba import njit
import numpy


def read():
    N = int(input().strip())
    line = input().strip()
    P = numpy.fromstring(line, dtype=numpy.int32, sep=" ")
    return N, P


@njit
def dfs(N, Q, stay, p, q):
    y, x = divmod(p, N)
    for dy, dx in ((0, 1), (1, 0), (-1, 0), (0, -1)):
        ny, nx = y + dy, x + dx
        if 0 <= ny < N and 0 <= nx < N:
            np = ny * N + nx
            if Q[np] > q:
                Q[np] = q
                dfs(N, Q, stay, np, q + stay[np])


@njit
def np_solve(N, P, INF=10**9):
    P -= 1
    Q = numpy.empty(N*N, dtype=numpy.int32)
    stay = numpy.ones(N*N, dtype=numpy.bool_)
    
    for i in range(N):
        for j in range(N):
            Q[i*N+j] = min([i, j, N-i-1, N-j-1])

    ans = 0
    for p in P:
        stay[p] = 0
        q = Q[p]
        ans += q
        dfs(N, Q, stay, p, q)
    return ans


if __name__ == '__main__':
    outputs = np_solve(*read())
    if outputs is not None:
        print("{}".format(outputs))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
from numba import njit
import numpy


def read():
    N = int(input().strip())
    line = input().strip()
    P = numpy.fromstring(line, dtype=numpy.int32, sep=" ")
    return N, P


@njit
def dfs(N, Q, stay, y, x, q):
    for dy, dx in ((0, 1), (1, 0), (-1, 0), (0, -1)):
        ny, nx = y + dy, x + dx
        if 0 <= ny < N and 0 <= nx < N:
            if Q[ny, nx] > q:
                Q[ny, nx] = q
                dfs(N, Q, stay, ny, nx, q + stay[ny, nx])


@njit
def np_solve(N, P, INF=10**9):
    P -= 1
    Q = numpy.empty((N, N), dtype=numpy.int32)
    stay = numpy.ones((N, N), dtype=numpy.bool_)
    
    for i in range(N):
        for j in range(N):
            Q[i, j] = min([i, j, N-1-i, N-1-j])

    ans = 0
    for p in P:
        y, x = divmod(p, N)
        q = Q[y, x]
        stay[y, x] = 0
        ans += q
        dfs(N, Q, stay, y, x, q)
    return ans


if __name__ == '__main__':
    outputs = np_solve(*read())
    if outputs is not None:
        print("{}".format(outputs))


Fixed submission:
import sys
input = sys.stdin.readline
from numba import njit
import numpy


def read():
    N = int(input().strip())
    line = input().strip()
    P = numpy.fromstring(line, dtype=numpy.int32, sep=" ")
    return N, P


@njit
def dfs(N, Q, stay, p, q):
    y, x = divmod(p, N)
    for dy, dx in ((0, 1), (1, 0), (-1, 0), (0, -1)):
        ny, nx = y + dy, x + dx
        if 0 <= ny < N and 0 <= nx < N:
            np = ny * N + nx
            if Q[np] > q:
                Q[np] = q
                dfs(N, Q, stay, np, q + stay[np])


@njit
def np_solve(N, P, INF=10**9):
    P -= 1
    Q = numpy.empty(N*N, dtype=numpy.int32)
    stay = numpy.ones(N*N, dtype=numpy.bool_)
    
    for i in range(N):
        for j in range(N):
            Q[i*N+j] = min([i, j, N-i-1, N-j-1])

    ans = 0
    for p in P:
        stay[p] = 0
        q = Q[p]
        ans += q
        dfs(N, Q, stay, p, q)
    return ans


if __name__ == '__main__':
    outputs = np_solve(*read())
    if outputs is not None:
        print("{}".format(outputs))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
from numba import njit
import numpy


def read():
    N = int(input().strip())
    line = input().strip()
    P = numpy.fromstring(line, dtype=numpy.int32, sep=" ")
    return N, P


@njit
def dfs(N, Q, stay, y, x, q):
    s = stay[y, x]
    for dy, dx in ((0, 1), (1, 0), (-1, 0), (0, -1)):
        ny, nx = y + dy, x + dx
        if 0 <= ny < N and 0 <= nx < N:
            if Q[ny, nx] > q + s:
                Q[ny, nx] = q + s
                dfs(N, Q, stay, ny, nx, q + s)


@njit
def np_solve(N, P, INF=10**9):
    P -= 1
    Q = numpy.empty((N, N), dtype=numpy.int32)
    stay = numpy.ones((N, N), dtype=numpy.int32)
    
    for i in range(N):
        for j in range(N):
            Q[i, j] = min([i, j, N-1-i, N-1-j])

    ans = 0
    for p in P:
        y, x = divmod(p, N)
        q = Q[y, x]
        stay[y, x] = 0
        ans += q
        dfs(N, Q, stay, y, x, q)
    return ans


if __name__ == '__main__':
    inputs = read()
    outputs = np_solve(*inputs)
    if outputs is not None:
        print("{}".format(outputs))


Fixed submission:
import sys
input = sys.stdin.readline
from numba import njit
import numpy


def read():
    N = int(input().strip())
    line = input().strip()
    P = numpy.fromstring(line, dtype=numpy.int32, sep=" ")
    return N, P


@njit
def dfs(N, Q, stay, p, q):
    y, x = divmod(p, N)
    for dy, dx in ((0, 1), (1, 0), (-1, 0), (0, -1)):
        ny, nx = y + dy, x + dx
        if 0 <= ny < N and 0 <= nx < N:
            np = ny * N + nx
            if Q[np] > q:
                Q[np] = q
                dfs(N, Q, stay, np, q + stay[np])


@njit
def np_solve(N, P, INF=10**9):
    P -= 1
    Q = numpy.empty(N*N, dtype=numpy.int32)
    stay = numpy.ones(N*N, dtype=numpy.bool_)
    
    for i in range(N):
        for j in range(N):
            Q[i*N+j] = min([i, j, N-i-1, N-j-1])

    ans = 0
    for p in P:
        stay[p] = 0
        q = Q[p]
        ans += q
        dfs(N, Q, stay, p, q)
    return ans


if __name__ == '__main__':
    outputs = np_solve(*read())
    if outputs is not None:
        print("{}".format(outputs))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
from numba import njit
import numpy


def read():
    N = int(input().strip())
    line = input().strip()
    P = numpy.fromstring(line, dtype=numpy.int32, sep=" ")
    P -= 1
    P.reshape((N, N))
    return N, P


@njit
def dfs(N, Q, visited, y, x, D):
    for dy, dx in D:
        ny, nx = y + dy, x + dx
        if 0 <= ny < N and 0 <= nx < N:
            # 4隣接が除去済みマスなら、コストなしで到達可能
            if not visited[ny, nx] and Q[ny, nx, 0] > Q[y, x, 0] + Q[ny, nx, 1]:
                Q[ny, nx, 0] = Q[y, x, 0] + Q[ny, nx, 1]
                visited[ny, nx] = True
                dfs(N, Q, visited, ny, nx, D)


@njit
def np_solve(N, P, INF=10**9):
    Q = numpy.empty((N, N, 2), dtype=numpy.int32)
    
    for i in range(N):
        for j in range(N):
            Q[i, j, :] = min([i, j, N-i-1, N-j-1]) + 1, 1

    D = ((0, 1), (1, 0), (-1, 0), (0, -1))
    visited = numpy.zeros((N, N), dtype=numpy.bool_)
    ans = 0

    for p in P:
        y, x = p//N, p%N
        r = INF
        for dy, dx in D:
            ny, nx = y + dy, x + dx
            if 0 <= ny < N and 0 <= nx < N:
                r = min(r, Q[ny, nx, 0])
            else:
                r = 0
        ans += r
        Q[y, x, :] = r, 0
        visited.fill(False)
        visited[y, x] = True
        dfs(N, Q, visited, y, x, D)
    return ans


if __name__ == '__main__':
    inputs = read()
    outputs = np_solve(*inputs)
    if outputs is not None:
        print("{}".format(outputs))


Fixed submission:
import sys
input = sys.stdin.readline
from numba import njit
import numpy


def read():
    N = int(input().strip())
    line = input().strip()
    P = numpy.fromstring(line, dtype=numpy.int32, sep=" ")
    return N, P


@njit
def dfs(N, Q, stay, p, q):
    y, x = divmod(p, N)
    for dy, dx in ((0, 1), (1, 0), (-1, 0), (0, -1)):
        ny, nx = y + dy, x + dx
        if 0 <= ny < N and 0 <= nx < N:
            np = ny * N + nx
            if Q[np] > q:
                Q[np] = q
                dfs(N, Q, stay, np, q + stay[np])


@njit
def np_solve(N, P, INF=10**9):
    P -= 1
    Q = numpy.empty(N*N, dtype=numpy.int32)
    stay = numpy.ones(N*N, dtype=numpy.bool_)
    
    for i in range(N):
        for j in range(N):
            Q[i*N+j] = min([i, j, N-i-1, N-j-1])

    ans = 0
    for p in P:
        stay[p] = 0
        q = Q[p]
        ans += q
        dfs(N, Q, stay, p, q)
    return ans


if __name__ == '__main__':
    outputs = np_solve(*read())
    if outputs is not None:
        print("{}".format(outputs))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
import bisect
from collections import deque


def read():
    N = int(input().strip())
    P = map(int, input().strip().split())
    return N, P


def sign(x):
    return (x > 0) - (x < 0)



def solve(N, P, INF=10**9):
    P = [p-1 for p in P]
    D = [N, -N, 1, -1]
    # Q[p]: 行動の最初にそのマスを踏んだ場合の、脱出までの最短コスト
    # 取り除いたマスは符号を反転する
    Q = [0 for _ in P]
    q = deque()
    cache = set()
    NN = N * N
    ans = 0

    for i in range(N):
        for j in range(N):
            k = i * N + j
            Q[k] = min(i, j, N-i-1, N-j-1) + 1
    
    x = 0
    for p in P:
        q.clear()
        cache.clear()
        r = INF
        for dp in D:
            np = p + dp
            if 0 <= np < NN and abs(np%N - p%N) < N-1:
                r = min(r, abs(Q[np]))
            else:
                r = 0
        
        ans += r
        Q[p] = -r
        q.append(p)
        while q:
            pp = q.popleft()
            for dp in D:
                np = pp + dp
                if 0 <= np < NN and abs(np%N - pp%N) < N-1 and np not in cache:
                    qnp, qpp = Q[np], Q[pp]
                    # 4隣接が除去済みマスなら、コストなしで到達可能
                    if qnp < 0 and abs(qnp) > abs(qpp):
                        Q[np] = abs(qpp) * sign(qnp)
                        q.append(np)
                        cache.add(np)
                    elif qnp > 0 and abs(qnp) > abs(qpp) + 1:
                        Q[np] = (abs(qpp) + 1) * sign(qnp)
                        q.append(np)
                        cache.add(np)
    return ans


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("{}".format(outputs))


Fixed submission:
import sys
input = sys.stdin.readline
from numba import njit
import numpy


def read():
    N = int(input().strip())
    line = input().strip()
    P = numpy.fromstring(line, dtype=numpy.int32, sep=" ")
    return N, P


@njit
def dfs(N, Q, stay, p, q):
    y, x = divmod(p, N)
    for dy, dx in ((0, 1), (1, 0), (-1, 0), (0, -1)):
        ny, nx = y + dy, x + dx
        if 0 <= ny < N and 0 <= nx < N:
            np = ny * N + nx
            if Q[np] > q:
                Q[np] = q
                dfs(N, Q, stay, np, q + stay[np])


@njit
def np_solve(N, P, INF=10**9):
    P -= 1
    Q = numpy.empty(N*N, dtype=numpy.int32)
    stay = numpy.ones(N*N, dtype=numpy.bool_)
    
    for i in range(N):
        for j in range(N):
            Q[i*N+j] = min([i, j, N-i-1, N-j-1])

    ans = 0
    for p in P:
        stay[p] = 0
        q = Q[p]
        ans += q
        dfs(N, Q, stay, p, q)
    return ans


if __name__ == '__main__':
    outputs = np_solve(*read())
    if outputs is not None:
        print("{}".format(outputs))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
import bisect
from collections import deque


def read():
    N = int(input().strip())
    P = list(map(int, input().strip().split()))
    return N, P


def print_map(N, Q):
    for i in range(N):
        print(Q[i*N:(i+1)*N])


def solve(N, P, INF=10**9):
    P = [p-1 for p in P]
    D = [N, -N, 1, -1]
    # Q[p]: 行動の最初にそのマスを踏んだ場合の、脱出までの最短コスト
    Q = [0 for _ in P]
    # LEFT[p]: 取り除いたらTrue
    LEFT = [False for _ in P]
    NN = N * N
    ans = 0

    for i in range(N):
        for j in range(N):
            k = i * N + j
            Q[k] = min(i, j, N-i-1, N-j-1) + 1
    
    for p in P:
        q = deque()
        r = INF
        for dp in D:
            np = p + dp
            if 0 <= np < NN and abs(np%N - p%N) < N-1:
                r = min(r, Q[np])
            else:
                r = 0
        
        ans += r

        LEFT[p] = True
        Q[p] = r
        q.append(p)
        while q:
            pp = q.popleft()
            for dp in D:
                np = pp + dp
                if 0 <= np < NN and abs(np%N - pp%N) < N-1:
                    # 4隣接が除去済みマスなら、コストなしで到達可能
                    if LEFT[np] and Q[np] > Q[pp]:
                        Q[np] = Q[pp]
                        q.append(np)
                    elif not LEFT[np] and Q[np] > Q[pp] + 1:
                        Q[np] = Q[pp] + 1
                        q.append(np)
    return ans


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("{}".format(outputs))


Fixed submission:
import sys
input = sys.stdin.readline
from numba import njit
import numpy


def read():
    N = int(input().strip())
    line = input().strip()
    P = numpy.fromstring(line, dtype=numpy.int32, sep=" ")
    return N, P


@njit
def dfs(N, Q, stay, p, q):
    y, x = divmod(p, N)
    for dy, dx in ((0, 1), (1, 0), (-1, 0), (0, -1)):
        ny, nx = y + dy, x + dx
        if 0 <= ny < N and 0 <= nx < N:
            np = ny * N + nx
            if Q[np] > q:
                Q[np] = q
                dfs(N, Q, stay, np, q + stay[np])


@njit
def np_solve(N, P, INF=10**9):
    P -= 1
    Q = numpy.empty(N*N, dtype=numpy.int32)
    stay = numpy.ones(N*N, dtype=numpy.bool_)
    
    for i in range(N):
        for j in range(N):
            Q[i*N+j] = min([i, j, N-i-1, N-j-1])

    ans = 0
    for p in P:
        stay[p] = 0
        q = Q[p]
        ans += q
        dfs(N, Q, stay, p, q)
    return ans


if __name__ == '__main__':
    outputs = np_solve(*read())
    if outputs is not None:
        print("{}".format(outputs))