Problem p02670 (python)

Fixed submission:
import sys
import numpy as np

from numba import njit


@njit('i4(i4,i4[:])', cache=True)
def solve(n, ppp):
    n2 = n + 2
    nsq = n2 * n2
    seats = np.zeros(nsq, dtype=np.int16)
    is_seated = np.zeros(nsq, dtype=np.int8)
    for i in range(n):
        ud = min(i, n - 1 - i)
        ri = (i + 1) * n2
        for j in range(n):
            ij = ri + j + 1
            seats[ij] = min(ud, j, n - 1 - j)
            is_seated[ij] = 1

    MOVES = np.array([-n2, -1, 1, n2], dtype=np.int32)

    ans = 0

    for pi in range(n * n):
        i, j = divmod(ppp[pi], n)
        i = (i + 1) * n2 + j + 1
        res = seats[i]
        ans += res
        is_seated[i] = 0

        q = []
        for mi in range(4):
            ni = i + MOVES[mi]
            if seats[ni] > res:
                seats[ni] = res
                q.append(ni)

        while q:
            j = q.pop()
            # print(val, j, seats[j], l, r)
            val = seats[j]

            if is_seated[j]:
                val += 1
            for mi in range(4):
                nj = j + MOVES[mi]
                if seats[nj] > val:
                    seats[nj] = val
                    q.append(nj)

        # print(ppp[pi] + 1, i, ans)
        # print(seats.reshape((n2, n2)))
        # print(is_seated.reshape((n2, n2)))

    return ans


n = int(sys.stdin.buffer.readline())
ppp = np.array(list(map(int, sys.stdin.buffer.read().split())), dtype=np.int32) - 1

# n = 20
# np.random.seed(seed=32)
# ppp = np.random.permutation(n * n).astype(np.int32)
# print(ppp)

print(solve(n, ppp))

Buggy submission (verdict: Runtime Error):
import sys
import numpy as np

from numba import njit, int64


@njit(int64(int64, int64[:]), cache=True)
def solve(n, ppp):
    n2 = n + 2
    nsq = n2 * n2
    seats = np.zeros(nsq, dtype=np.int64)
    is_seated = np.zeros(nsq, dtype=np.int8)
    for i in range(n):
        ud = min(i, n - 1 - i)
        ri = (i + 1) * n2
        for j in range(n):
            ij = ri + j + 1
            seats[ij] = min(ud, j, n - 1 - j)
            is_seated[ij] = 1

    MOVES = np.array([-n2, -1, 1, n2], dtype=np.int64)

    ans = 0

    for p in ppp:
        i, j = divmod(p - 1, n)
        i = (i + 1) * n2 + j + 1
        res = seats[i]
        ans += res
        is_seated[i] = 0

        deque = [(0, 0)] * nsq
        deque[0] = (res, i)
        l, r = 0, 1

        while l != r:
            val, j = deque[l]
            # print(val, j, deque[l:r] if l >= 0 else deque[l:] + deque[:r])
            l += 1
            seats[j] = val

            if is_seated[j]:
                val += 1
                for dj in MOVES:
                    nj = j + dj
                    if seats[nj] > val:
                        deque[r] = (val, nj)
                        r = (r + 1) % nsq
            else:
                for dj in MOVES:
                    nj = j + dj
                    if seats[nj] > val:
                        l = (l - 1) % nsq
                        deque[l] = (val, nj)

    return ans


n = int(sys.stdin.buffer.readline())
ppp = np.array(list(map(int, sys.stdin.buffer.read().split())), dtype=np.int64)
print(solve(n, ppp))

# solve.inspect_types()
# bfs.inspect_types()

Buggy submission (verdict: Runtime Error):
import sys
import numpy as np

from numba import njit, int64


@njit(int64(int64, int64[:]), cache=True)
def solve(n, ppp):
    n2 = n + 2
    nsq = n2 * n2
    seats = np.zeros(nsq, dtype=np.int64)
    is_seated = np.zeros(nsq, dtype=np.int8)
    for i in range(n):
        ud = min(i, n - 1 - i)
        ri = (i + 1) * n2
        for j in range(n):
            ij = ri + j + 1
            seats[ij] = min(ud, j, n - 1 - j)
            is_seated[ij] = 1

    MOVES = np.array([-n2, -1, 1, n2], dtype=np.int64)

    ans = 0

    for p in ppp:
        i, j = divmod(p - 1, n)
        i = (i + 1) * n2 + j + 1
        res = seats[i]
        ans += res
        is_seated[i] = 0

        deque = [(0, 0)] * nsq
        deque[0] = (res, i)
        l, r = 0, 1

        while l != r:
            val, j = deque[l]
            # print(val, j, deque[l:r] if l >= 0 else deque[l:] + deque[:r])
            l += 1
            seats[j] = val

            if is_seated[j]:
                val += 1
                for dj in MOVES:
                    nj = j + dj
                    if seats[nj] > val:
                        deque[r] = (val, nj)
                        r = (r + 1) % nsq
            else:
                for dj in MOVES:
                    nj = j + dj
                    if seats[nj] > val:
                        l -= 1
                        deque[l] = (val, nj)

    return ans


n = int(sys.stdin.buffer.readline())
ppp = np.array(list(map(int, sys.stdin.buffer.read().split())), dtype=np.int64)
print(solve(n, ppp))

# solve.inspect_types()
# bfs.inspect_types()

Buggy submission (verdict: Runtime Error):
import sys
import numpy as np

from numba import njit, int64


@njit(int64(int64, int64[:]), cache=True)
def solve(n, ppp):
    n2 = n + 2
    nsq = n2 * n2
    seats = np.zeros(nsq, dtype=np.int64)
    is_seated = np.zeros(nsq, dtype=np.int8)
    for i in range(n):
        ud = min(i, n - 1 - i)
        ri = (i + 1) * n2
        for j in range(n):
            ij = ri + j + 1
            seats[ij] = min(ud, j, n - 1 - j)
            is_seated[ij] = 1

    MOVES = np.array([-n2, -1, 1, n2], dtype=np.int64)

    ans = 0

    for p in ppp:
        i, j = divmod(p - 1, n)
        i = (i + 1) * n2 + j + 1
        res = seats[i]
        ans += res
        is_seated[i] = 0

        deque = [(0, 0)] * 500000
        deque[0] = (res, i)
        l, r = 0, 1

        while l < r:
            val, j = deque[l]
            # print(val, j, deque[l:r] if l >= 0 else deque[l:] + deque[:r])
            l += 1
            seats[j] = val

            if is_seated[j]:
                val += 1
                for dj in MOVES:
                    nj = j + dj
                    if seats[nj] > val:
                        deque[r] = (val, nj)
                        r += 1
            else:
                for dj in MOVES:
                    nj = j + dj
                    if seats[nj] > val:
                        l -= 1
                        deque[l] = (val, nj)

    return ans


n = int(sys.stdin.buffer.readline())
ppp = np.array(list(map(int, sys.stdin.buffer.read().split())), dtype=np.int64)
print(solve(n, ppp))

# solve.inspect_types()
# bfs.inspect_types()

Buggy submission (verdict: Runtime Error):
import sys
import numpy as np

from numba import njit, int64


@njit(int64(int64, int64[:]), cache=True)
def solve(n, ppp):
    n2 = n + 2
    seats = [-1] * (n2 * n2)
    is_seated = [False] * (n2 * n2)
    for i in range(n):
        ud = min(i, n - 1 - i)
        ri = (i + 1) * n2
        for j in range(n):
            ij = ri + j + 1
            seats[ij] = min(ud, j, n - 1 - j)
            is_seated[ij] = True

    ans = 0

    for p in ppp:
        i, j = divmod(p - 1, n)
        i = (i + 1) * n2 + j + 1
        res = seats[i]
        ans += res
        is_seated[i] = False

        deque = [(0, 0)] * 500000
        deque[0] = (res, i)
        l, r = 0, 1

        while l < r:
            val, j = deque[l]
            # print(val, j, deque[l:r] if l >= 0 else deque[l:] + deque[:r])
            l += 1
            seats[j] = val

            if is_seated[j]:
                val += 1
                nj = j - n2
                if seats[nj] > val:
                    deque[r] = (val, nj)
                    r += 1
                nj = j - 1
                if seats[nj] > val:
                    deque[r] = (val, nj)
                    r += 1
                nj = j + 1
                if seats[nj] > val:
                    deque[r] = (val, nj)
                    r += 1
                nj = j + n2
                if seats[nj] > val:
                    deque[r] = (val, nj)
                    r += 1
            else:
                nj = j - n2
                if seats[nj] > val:
                    l -= 1
                    deque[l] = (val, nj)
                nj = j - 1
                if seats[nj] > val:
                    l -= 1
                    deque[l] = (val, nj)
                nj = j + 1
                if seats[nj] > val:
                    l -= 1
                    deque[l] = (val, nj)
                nj = j + n2
                if seats[nj] > val:
                    l -= 1
                    deque[l] = (val, nj)

    return ans


n = int(sys.stdin.buffer.readline())
ppp = np.array(list(map(int, sys.stdin.buffer.read().split())), dtype=np.int64)
print(solve(n, ppp))

# solve.inspect_types()
# bfs.inspect_types()