Problem p02670 (python)

Fixed submission:
import sys
import numpy as np
from numba import njit

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

@njit('(i4,i4[:])',cache=True)
def main(n,p):
    ans = 0
    w = n+2
    grid = np.ones((w,w),np.int32)
    dis = np.zeros((w,w),np.int32)
    for i in range(1,n+1):
        for j in range(1,n+1):
            dis[i][j] = min(i,n-i+1,j,n-j+1)-1
    grid = grid.ravel()
    dis = dis.ravel()
    stack = np.empty_like(grid)
    for pos in p:
        pos -= 1
        x = pos % n + 1
        y = pos // n + 1
        v = y*w+x
        ans += dis[v]
        grid[v] = 0
        k = min(dis[v-1],dis[v+1],dis[v+w],dis[v-w])
        cur = 0
        stack[0] = v
        while cur >= 0:
            v = stack[cur]
            cur -= 1
            for dx in (-1,1,w,-w):
                next_v = v + dx
                k = dis[v]+grid[v]
                if dis[next_v] > k:
                    dis[next_v] = k
                    cur += 1
                    stack[cur] = next_v
    return ans

n = int(readline())
p = np.array(readline().split(),np.int32)
print(main(n,p))

Buggy submission (verdict: Runtime Error):
from collections import deque
def dfs(x,y):
    z = h[y][x] + grid[y][x]
    for i in range(4):
        next_x = x+dx[i]
        next_y = y+dy[i]
        if h[next_y][next_x] > z:
            h[next_y][next_x] = z
            dfs(next_x,next_y)
n = int(input())
h = [[0]*(n+2) for _ in range(n+2)]
for i in range(1,n+1):
    for j in range(1,n+1):
        h[i][j] = min(i,n-i+1,j,n-j+1)-1
grid = [[1]*(n+1) for _ in range(n+1)]
dx = [0,1,0,-1]
dy = [1,0,-1,0]
ans = 0
p = list(map(int,input().split()))
for i in range(n**2):
    pos = p[i]
    x = (pos-1)%n+1
    y = (pos-1)//n+1
    ans += h[y][x]
    grid[y][x] = 0
    dfs(x,y)
print(ans)

Buggy submission (verdict: Runtime Error):
import numpy as np
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(100000)

from numba import njit

@njit('(i4,i4[:],i4[:],i4[:])',cache=True)
def main(n,p,dx,dy):
    ans = 0
    def dfs(x,y,dx,dy,grid,dis):
        z = dis[y][x] + grid[y][x]
        for i in range(4):
            next_x = x+dx[i]
            next_y = y+dy[i]
            if dis[next_y][next_x] > z:
                dis[next_y][next_x] = z
                dfs(next_x,next_y,dx,dy,grid,dis)
    grid = np.ones((n+1,n+1),np.int32)
    dis = np.zeros((n+2,n+2),np.int32)
    for i in range(1,n+1):
        for j in range(1,n+1):
            dis[i][j] = min(i,n-i+1,j,n-j+1)-1
    for i in range(n**2):
        pos = p[i]
        x = (pos-1)%n+1
        y = (pos-1)//n+1
        ans += dis[y][x]
        grid[y][x] = 0
        dfs(x,y,dx,dy,grid,dis)
    return ans

n = int(readline())
p = np.array(readline().split(),np.int32)
dx = np.array([0,1,0,-1])
dy = np.array([1,0,-1,0])
print(main(n,p,dx,dy))

Buggy submission (verdict: Runtime Error):
import numpy as np
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(100000)

from numba import njit

@njit('(i4,i4[:])',cache=True)
def main(n,p):
    dx = np.array([0,1,0,-1])
    dy = np.array([1,0,-1,0])
    ans = 0
    def dfs(x,y,dx,dy,grid,dis):
        z = dis[y][x] + grid[y][x]
        for i in range(4):
            next_x = x+dx[i]
            next_y = y+dy[i]
            if dis[next_y][next_x] > z:
                dis[next_y][next_x] = z
                dfs(next_x,next_y,dx,dy,grid,dis)
    grid = np.ones((n+1,n+1),np.int32)
    dis = np.zeros((n+2,n+2),np.int32)
    for i in range(1,n+1):
        for j in range(1,n+1):
            dis[i][j] = min(i,n-i+1,j,n-j+1)-1
    for i in range(n**2):
        pos = p[i]
        x = (pos-1)%n+1
        y = (pos-1)//n+1
        ans += dis[y][x]
        grid[y][x] = 0
        dfs(x,y,dx,dy,grid,dis)
    return ans

n = int(readline())
p = np.array(readline().split(),np.int32)
print(main(n,p))

Buggy submission (verdict: Runtime Error):
import numpy as np
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(100000)

from numba import njit

@njit('i4,i4[:]',cache=True)
def main(n,p):
    dx = np.array([0,1,0,-1])
    dy = np.array([1,0,-1,0])
    ans = 0
    def dfs(x,y,dx,dy,grid,dis):
        z = dis[y][x] + grid[y][x]
        for i in range(4):
            next_x = x+dx[i]
            next_y = y+dy[i]
            if dis[next_y][next_x] > z:
                dis[next_y][next_x] = z
                dfs(next_x,next_y,dx,dy,grid,dis)
    grid = np.ones((n+1,n+1),np.int32)
    dis = np.zeros((n+2,n+2),np.int32)
    for i in range(1,n+1):
        for j in range(1,n+1):
            dis[i][j] = min(i,n-i+1,j,n-j+1)-1
    for i in range(n**2):
        pos = p[i]
        x = (pos-1)%n+1
        y = (pos-1)//n+1
        ans += dis[y][x]
        grid[y][x] = 0
        dfs(x,y,dx,dy,grid,dis)
    return ans

n = int(readline())
p = np.array(readline().split(),np.int32)
print(main(n,p))

Buggy submission (verdict: Runtime Error):
import numpy as np
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def main(n,p):
    dx = np.array([0,1,0,-1])
    dy = np.array([1,0,-1,0])
    ans = 0
    def dfs(x,y,dx,dy,grid,dis):
        z = dis[y][x] + grid[y][x]
        for i in range(4):
            next_x = x+dx[i]
            next_y = y+dy[i]
            if dis[next_y][next_x] > z:
                dis[next_y][next_x] = z
                dfs(next_x,next_y,dx,dy,grid,dis)
    grid = np.ones((n+1,n+1),np.int32)
    dis = np.zeros((n+2,n+2),np.int32)
    for i in range(1,n+1):
        for j in range(1,n+1):
            dis[i][j] = min(i,n-i+1,j,n-j+1)-1
    for i in range(n**2):
        pos = p[i]
        x = (pos-1)%n+1
        y = (pos-1)//n+1
        ans += dis[y][x]
        grid[y][x] = 0
        dfs(x,y,dx,dy,grid,dis)
    return ans

n = int(readline())
p = np.array(readline().split(),np.int32)
print(main(n,p))

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

def dfs(x,y):
    z = h[y][x] + grid[y][x]
    for i in range(4):
        next_x = x+dx[i]
        next_y = y+dy[i]
        if h[next_y][next_x] > z:
            h[next_y][next_x] = z
            dfs(next_x,next_y)
n = int(input())
h = np.array([[0]*(n+2) for _ in range(n+2)])
for i in range(1,n+1):
    for j in range(1,n+1):
        h[i][j] = min(i,n-i+1,j,n-j+1)-1
grid = np.array([[1]*(n+1) for _ in range(n+1)])
dx = np.array([0,1,0,-1])
dy = np.array([1,0,-1,0])
ans = 0
p = list(map(int,input().split()))
for i in range(n**2):
    pos = p[i]
    x = (pos-1)%n+1
    y = (pos-1)//n+1
    ans += h[y][x]
    grid[y][x] = 0
    dfs(x,y)
print(ans)

Buggy submission (verdict: Runtime Error):
from collections import deque
def dfs(x,y):
    z = h[y][x] + grid[y][x]
    for i in range(4):
        next_x = x+dx[i]
        next_y = y+dy[i]
        if h[next_y][next_x] > z:
            h[next_y][next_x] = z
            dfs(next_x,next_y)
n = int(input())
h = [[0]*(n+2) for _ in range(n+2)]
for i in range(1,n+1):
    for j in range(1,n+1):
        h[i][j] = min(i,n-i+1,j,n-j+1)-1
grid = [[1]*(n+1) for _ in range(n+1)]
dx = [0,1,0,-1]
dy = [1,0,-1,0]
ans = 0
p = list(map(int,input().split()))
for i in range(n**2):
    pos = p[i]
    x = (pos-1)%n+1
    y = (pos-1)//n+1
    ans += h[y][x]
    grid[y][x] = 0
    dfs(x,y)
print(ans)

Buggy submission (verdict: Runtime Error):
from collections import deque
def hate(x,y):
    cur_hate = 0
    cur_q = set()
    next_q = set()
    cur_q.add((x,y))
    already = set()
    flag = False
    while True:
        while cur_q:
            x,y = cur_q.pop()
            for i in range(4):
                next_x = x+dx[i]
                next_y = y+dy[i]
                if not (next_x,next_y) in already:
                    if grid[next_y][next_x] == "o":
                        if cur_hate != 0:
                            return cur_hate
                        flag = True
                    if grid[next_y][next_x] == "#":
                        next_q.add((next_x,next_y))
                    else:
                        cur_q.add((next_x,next_y))
                    if grid[y][x] != "o":
                        already.add((x,y))
        if flag:
            for x,y in already:
                grid[y][x] ="o"
            return 0
        cur_hate += 1
        cur_q = next_q
        next_q = set()
n = int(input())
grid = []
grid.append(["o"]*(n+2))
for i in range(n):
    grid.append(["o"]+["#"]*n+["o"])
grid.append(["o"]*(n+2))
dx = [0,1,0,-1]
dy = [1,0,-1,0]
ans = 0
p = list(map(int,input().split()))
for i in range(n**2):
    pos = p[i]
    x = (pos-1)%n+1
    y = (pos-1)//n+1
    h = hate(x,y)
    ans += h
    if h == 0:
        grid[y][x] = "o"
    else:
        grid[y][x] = "."
print(ans)