Problem:


Score : 700 points

Problem Statement

Tonight, in your favourite cinema they are giving the movie Joker and all seats are occupied. In the cinema there are N rows with N seats each, forming an N\times N square. We denote with 1, 2,\dots, N the viewers in the first row (from left to right); with N+1, \dots, 2N the viewers in the second row (from left to right); and so on until the last row, whose viewers are denoted by N^2-N+1,\dots, N^2.

At the end of the movie, the viewers go out of the cinema in a certain order: the i-th viewer leaving her seat is the one denoted by the number P_i. The viewer P_{i+1} waits until viewer P_i has left the cinema before leaving her seat.
To exit from the cinema, a viewer must move from seat to seat until she exits the square of seats (any side of the square is a valid exit). A viewer can move from a seat to one of its 4 adjacent seats (same row or same column).
While leaving the cinema, it might be that a certain viewer x goes through a seat currently occupied by viewer y; in that case viewer y will hate viewer x forever. Each viewer chooses the way that minimizes the number of viewers that will hate her forever.

Compute the number of pairs of viewers (x, y) such that y will hate x forever.

Constraints

2 \le N \le 500

The sequence P_1, P_2, \dots, P_{N^2} is a permutation of \{1, 2, \dots, N^2\}.

Input

The input is given from Standard Input in the format

N
P_1 P_2 \cdots P_{N^2}

Output

If ans is the number of pairs of viewers described in the statement, you should print on Standard Output

ans

Sample Input 1

3
1 3 7 9 5 4 8 6 2

Sample Output 1

1

Before the end of the movie, the viewers are arranged in the cinema as follows:

1 2 3
4 5 6
7 8 9

The first four viewers leaving the cinema (1, 3, 7, 9) can leave the cinema without going through any seat, so they will not be hated by anybody.

Then, viewer 5 must go through one of the seats where viewers 2, 4, 6, 8 are currently seated while leaving the cinema; hence he will be hated by at least one of those viewers.

Finally the remaining viewers can leave the cinema (in the order 4, 8, 6, 2) without going through any occupied seat (actually, they can leave the cinema without going through any seat at all).

Sample Input 2

4
6 7 1 4 13 16 10 9 5 11 12 14 15 2 3 8

Sample Output 2

3

Sample Input 3

6
11 21 35 22 7 36 27 34 8 20 15 13 16 1 24 3 2 17 26 9 18 32 31 23 19 14 4 25 10 29 28 33 12 6 5 30

Sample Output 3

11



Sample input:
3
1 3 7 9 5 4 8 6 2


Sample output:
1

Submission status: Time Limit Exceeded

Solution code:
def main():
  #n = int(input())
  #p = tuple(map(int,input().split()))
  import sys
  n,*p = map(int,sys.stdin.read().split())

  m = [[0 for _ in range(n)] for _ in range(n)]
  for i in range(n):
    for j in range(n):
      m[i][j] = min(i,n-1-i,j,n-1-j)
  #print(m)

  exist = [[1 for _ in range(n)] for _ in range(n)]

  ans = 0
  for pi in p:
    #pi -= 1
    #y = pi//n
    #x = pi%n
    y,x = divmod(pi-1,n)
    ans += m[y][x]
    exist[y][x] = 0
    q = [(y,x)]
    while(len(q)>0):
      qy,qx = q.pop()
      for dy,dx in ((1,0),(-1,0),(0,1),(0,-1)):
        if qy+dy < 0 or qy+dy >= n or qx+dx < 0 or qx+dx >= n:
          continue
        if m[qy+dy][qx+dx] > m[qy][qx]+exist[qy][qx]:
          m[qy+dy][qx+dx] = m[qy][qx]+exist[qy][qx]
          q.append((qy+dy,qx+dx))
  print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from numba import jit

@jit
def main():
  n = int(input())
  p = tuple(map(int,input().split()))
  #n,*p = map(int,sys.stdin.read().split())

  m = [[0 for _ in range(n)] for _ in range(n)]
  for i in range(n):
    for j in range(n):
      m[i][j] = min(i,n-1-i,j,n-1-j)
  #print(m)

  exist = [[1 for _ in range(n)] for _ in range(n)]

  ans = 0
  for pi in p:
    #pi -= 1
    #y = pi//n
    #x = pi%n
    y,x = divmod(pi-1,n)
    ans += m[y][x]
    exist[y][x] = 0
    q = [(y,x)]
    while(len(q)>0):
      qy,qx = q.pop()
      for dy,dx in ((1,0),(-1,0),(0,1),(0,-1)):
        if qy+dy < 0 or qy+dy >= n or qx+dx < 0 or qx+dx >= n:
          continue
        if m[qy+dy][qx+dx] > m[qy][qx]+exist[qy][qx]:
          m[qy+dy][qx+dx] = m[qy][qx]+exist[qy][qx]
          q.append((qy+dy,qx+dx))
  print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
n=N()
p=L()
size=(n+1)**2+1
ans=[0]*size
for i in range(1,n+1):
    for j in range(1,n+1):
        k=i*(n+1)+j
        ans[k]=min(i-1,j-1,n-i,n-j)
c=[1]*size
di=[-1,1,n+1,-n-1]
def f(k,i):
    if k+i>=size:
        return
    if ans[k]+c[k]<ans[k+i]:
        ans[k+i]-=1
        q.append(k+i)
t=0
for i in p:
    y=i%n
    if y==0:
        y=n
    x=(i+n-1)//n
    k=x*(n+1)+y
    c[k]=0
    t+=ans[k]
    q=[k]
    while q:
        k=q.pop()
        f(k,1)
        f(k,-1)
        f(k,n+1)
        f(k,-n-1)
print(t)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
from collections import deque
from numba import jit

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

@jit
def main():
    N = ir()
    P = lr()
    P = [((p-1)//N, (p-1)%N) for p in P]
    dp = [[min(i, N-1-i, j, N-1-j) for j in range(N)] for i in range(N)]
    people = [[True] * N for i in range(N)]

    answer = 0
    for i, j in P:
        answer += dp[i][j]
        people[i][j] = False
        que = deque([(i, j, dp[i][j])])
        popleft = que.popleft; append = que.append
        while que:
            y, x, cur = popleft()
            cur += people[y][x]
            if x > 0:
                if dp[y][x-1] > cur:
                    dp[y][x-1] = cur
                    append((y, x-1, cur))
            if x < N-1:
                if dp[y][x+1] > cur:
                    dp[y][x+1] = cur
                    append((y, x+1, cur))
            if y > 0:
                if dp[y-1][x] > cur:
                    dp[y-1][x] = cur
                    append((y-1, x, cur))
            if y < N-1:
                if dp[y+1][x] > cur:
                    dp[y+1][x] = cur
                    append((y+1, x, cur))

    print(answer)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  #n = int(input())
  #p = tuple(map(int,input().split()))
  import sys
  n,*p = map(int,sys.stdin.read().split())

  m = [[0 for _ in range(n)] for _ in range(n)]
  for i in range(n):
    for j in range(n):
      m[i][j] = min(i,n-1-i,j,n-1-j)
  #print(m)

  exist = [[1 for _ in range(n)] for _ in range(n)]

  ans = 0
  for pi in p:
    #pi -= 1
    #y = pi//n
    #x = pi%n
    y,x = divmod(pi-1,n)
    ans += m[y][x]
    exist[y][x] = 0
    q = [(y,x)]
    while(len(q)>0):
      qy,qx = q.pop()
      for dy,dx in ((1,0),(-1,0),(0,1),(0,-1)):
        if qy+dy < 0 or qy+dy >= n or qx+dx < 0 or qx+dx >= n:
          continue
        if m[qy+dy][qx+dx] > m[qy][qx]+exist[qy][qx]:
          m[qy+dy][qx+dx] = m[qy][qx]+exist[qy][qx]
          q.append((qy+dy,qx+dx))
  print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  #n = int(input())
  #p = tuple(map(int,input().split()))
  import sys
  n,*p = map(int,sys.stdin.read().split())

  m = [[0 for _ in range(n)] for _ in range(n)]
  for i in range(n):
    for j in range(n):
      m[i][j] = min(i,n-1-i,j,n-1-j)
  #print(m)

  exist = [[1 for _ in range(n)] for _ in range(n)]

  ans = 0
  for pi in p:
    pi -= 1
    y = pi//n
    x = pi%n
    ans += m[y][x]
    exist[y][x] = 0
    q = [(y,x)]
    while(len(q)>0):
      qy,qx = q.pop()
      for dy,dx in [[1,0],[-1,0],[0,1],[0,-1]]:
        if qy+dy < 0 or qy+dy >= n or qx+dx < 0 or qx+dx >= n:
          continue
        if m[qy+dy][qx+dx] > m[qy][qx]+exist[qy][qx]:
          m[qy+dy][qx+dx] = m[qy][qx]+exist[qy][qx]
          q.append((qy+dy,qx+dx))
  print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  #n = int(input())
  #p = tuple(map(int,input().split()))
  import sys
  n,*p = map(int,sys.stdin.read().split())

  m = [[0 for _ in range(n)] for _ in range(n)]
  for i in range(n):
    for j in range(n):
      m[i][j] = min(i,n-1-i,j,n-1-j)
  #print(m)

  exist = [[1 for _ in range(n)] for _ in range(n)]

  ans = 0
  for pi in p:
    pi -= 1
    y = pi//n
    x = pi%n
    ans += m[y][x]
    exist[y][x] = 0
    q = [(y,x)]
    while(len(q)>0):
      qq = []
      for qy,qx in q:
        for dy,dx in [[1,0],[-1,0],[0,1],[0,-1]]:
          if qy+dy < 0 or qy+dy >= n or qx+dx < 0 or qx+dx >= n:
            continue
          if m[qy+dy][qx+dx] > m[qy][qx]+exist[qy][qx]:
            m[qy+dy][qx+dx] = m[qy][qx]+exist[qy][qx]
            qq.append((qy+dy,qx+dx))
      q = qq[:]
  print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
#n = int(input())
#p = tuple(map(int,input().split()))
import sys
n,*p = map(int,sys.stdin.read().split())

m = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
  for j in range(n):
    m[i][j] = min(i,n-1-i,j,n-1-j)
#print(m)

exist = [[1 for _ in range(n)] for _ in range(n)]

ans = 0
for pi in p:
  pi -= 1
  y = pi//n
  x = pi%n
  ans += m[y][x]
  exist[y][x] = 0
  q = [(y,x)]
  while(len(q)>0):
    qq = []
    for qy,qx in q:
      for dy,dx in [[1,0],[-1,0],[0,1],[0,-1]]:
        if qy+dy < 0 or qy+dy >= n or qx+dx < 0 or qx+dx >= n:
          continue
        if m[qy+dy][qx+dx] > m[qy][qx]+exist[qy][qx]:
          m[qy+dy][qx+dx] = m[qy][qx]+exist[qy][qx]
          qq.append((qy+dy,qx+dx))
    q = qq[:]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
p = tuple(map(int,input().split()))

m = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
  for j in range(n):
    m[i][j] = min(i,n-1-i,j,n-1-j)
#print(m)

exist = [[1 for _ in range(n)] for _ in range(n)]

ans = 0
for pi in p:
  pi -= 1
  y = pi//n
  x = pi%n
  ans += m[y][x]
  exist[y][x] = 0
  q = [(y,x)]
  while(len(q)>0):
    qq = []
    for qy,qx in q:
      for dy,dx in [[1,0],[-1,0],[0,1],[0,-1]]:
        if qy+dy < 0 or qy+dy >= n or qx+dx < 0 or qx+dx >= n:
          continue
        if m[qy+dy][qx+dx] > m[qy][qx]+exist[qy][qx]:
          m[qy+dy][qx+dx] = m[qy][qx]+exist[qy][qx]
          qq.append((qy+dy,qx+dx))
    q = qq[:]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np


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


def solve(N, P):
    W = N + 2
    dp = np.zeros((W, W), np.int32)
    for _ in range(4):
        dp = dp.T[::-1]
        for n in range(1, (N + 1) // 2 + 1):
            dp[n, n:-n] = n
    filled = np.zeros_like(dp)
    filled[1:-1, 1:-1] = 1
    dp = dp.ravel()
    filled = filled.ravel()
    stack = np.empty_like(dp)
    ans = 0
    for n in P:
        n -= 1
        h, w = divmod(n, N)
        v = (h + 1) * W + (w + 1)
        ans += dp[v] - 1
        filled[v] = 0
        k = min(dp[v - 1], dp[v + 1], dp[v - W], dp[v + W])
        if dp[v] == k:
            return ans
        p = 0
        stack[0] = v
        dp[v] = k
        while p >= 0:
            v = stack[p]
            p -= 1
            for dx in (-1, 1, -W, W):
                w = v + dx
                k = dp[v] + filled[w]
                if dp[w] > k:
                    dp[w] = k
                    p += 1
                    stack[p] = w
    return ans

N = int(readline())
P = np.array(read().split(), np.int32)

print(solve(N, P))

Submission status: Time Limit Exceeded

Solution code:
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))

Submission status: Time Limit Exceeded

Solution code:
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))

Submission status: Time Limit Exceeded

Solution code:
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))

Submission status: Time Limit Exceeded

Solution code:

n=int(input())
A=list(map(int,input().split()))

remain=[[1]*n for i in range(n)]

que1=[]
que2=[]
ans=0
for a in A:
    x,y=(a-1)//n,(a-1)%n
    remain[x][y]=0
    que2.append((x,y))
    check=[[0]*n for i in range(n)]
    check[x][y]=1
    endflag=0
    for i in range(0,501):
        newque=[]
        while que1:
            x,y=que1.pop()
            for nx,ny in ((x-1,y),(x+1,y),(x,y+1),(x,y-1)):
                if nx<0 or ny<0 or nx>=n or ny>=n:
                    endflag=1
                    break
                if check[nx][ny]==0:
                    check[nx][ny]=1
                    if remain[nx][ny]:
                        newque.append((nx,ny))
                    else:
                        que2.append((nx,ny))
        while que2:
            x,y=que2.pop()
            for nx,ny in ((x-1,y),(x+1,y),(x,y+1),(x,y-1)):
                if nx<0 or ny<0 or nx>=n or ny>=n:
                    endflag=1
                    break
                if check[nx][ny]==0:
                    check[nx][ny]=1
                    if remain[nx][ny]:
                        newque.append((nx,ny))
                    else:
                        que2.append((nx,ny))
        if endflag:
            break
        que1=newque
    ans+=i
print(ans)

Submission status: Time Limit Exceeded

Solution code:

n=int(input())
A=list(map(int,input().split()))

remain=[[1]*n for i in range(n)]

from collections import deque
que1=deque()
que2=deque()
ans=0
for a in A:
    x,y=(a-1)//n,(a-1)%n
    remain[x][y]=0
    que2.append((x,y))
    check=[[0]*n for i in range(n)]
    check[x][y]=1
    endflag=0
    for i in range(0,501):
        newque=deque()
        while que1:
            x,y=que1.popleft()
            for nx,ny in ((x-1,y),(x+1,y),(x,y+1),(x,y-1)):
                if nx<0 or ny<0 or nx>=n or ny>=n:
                    endflag=1
                    break
                if check[nx][ny]==0:
                    check[nx][ny]=1
                    if remain[nx][ny]:
                        newque.append((nx,ny))
                    else:
                        que2.append((nx,ny))
        while que2:
            x,y=que2.popleft()
            for nx,ny in ((x-1,y),(x+1,y),(x,y+1),(x,y-1)):
                if nx<0 or ny<0 or nx>=n or ny>=n:
                    endflag=1
                    break
                if check[nx][ny]==0:
                    check[nx][ny]=1
                    if remain[nx][ny]:
                        newque.append((nx,ny))
                    else:
                        que2.append((nx,ny))
        if endflag:
            break
        que1=newque
    ans+=i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
#import sys
# sys.setrecursionlimit(20000)
[n], *e = [[*map(int, t.split())] for t in open(0)]
#n = 20
# np.random.seed(seed=64)
#ppp = [x + 1 for x in np.random.permutation(n * n).astype(np.int32)]
#e = [ppp]
# print(ppp)


viewers = set(range(1, n**2 + 1))
mem = {x: min((x - 1) % n, (n - x) % n, (x - 1)//n, n - 1 - (x - 1)//n)
       for x in range(1, n**2 + 1)}

ans = 0


def directions(x):
    tmp = []
    if x % n != 1:
        tmp.append(x - 1)
    if x % n > 0:
        tmp.append(x + 1)
    if (x - 1)//n > 0:
        tmp.append(x - n)
    if (x - 1)//n < n - 1:
        tmp.append(x + n)
    return tmp


for x in e[0]:

    def bfs(x):
        queue = [x]
        while queue:
            tmp = queue.pop(0)
            z = mem[tmp] + (tmp in viewers)
            for k in directions(tmp):
                if mem[k] > z:
                    mem[k] = z
                    queue.append(k)

    ans += mem[x]
    viewers.remove(x)
    bfs(x)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
[n], *e = [[*map(int, t.split())] for t in open(0)]

viewers = set(range(1, n**2 + 1))
mem = {x: min((x - 1) % n, (n - x) % n, (x - 1)//n, n - 1 - (x - 1)//n)
       for x in range(1, n**2 + 1)}

ans = 0


def directions(x):
    tmp = []
    if x % n != 1:
        tmp.append(x - 1)
    if x % n > 0:
        tmp.append(x + 1)
    if (x - 1)//n > 0:
        tmp.append(x - n)
    if (x - 1)//n < n - 1:
        tmp.append(x + n)
    return tmp


for x in e[0]:

    def bfs(x):
        visited = {x}
        queue = [x]
        while queue:
            tmp = queue.pop(0)
            z = mem[tmp] + (tmp in viewers)
            for k in directions(tmp):
                if k not in visited and mem[k] > z:
                    mem[k] = z
                    queue.append(k)

    ans += mem[x]
    viewers.remove(x)
    bfs(x)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
import sys
sys.setrecursionlimit(10**6)
n=N()
p=L()
size=(n+1)**2+1
ans=[0]*size
for i in range(1,n+1):
    for j in range(1,n+1):
        k=i*(n+1)+j
        ans[k]=min(i-1,j-1,n-i,n-j)
c=[1]*size
di=[-1,1,n+1,-n-1]
def f(k):
    for i in di:
        if k+i>=size:
            continue
        if ans[k]+c[k]<ans[k+i]:
            ans[k+i]-=1
            q.append(k+i)
t=0
for i in p:
    y=i%n
    if y==0:
        y=n
    x=(i+n-1)//n
    k=x*(n+1)+y
    c[k]=0
    t+=ans[k]
    q=[k]
    while q:
        k=q.pop()
        f(k)
print(t)

Submission status: Time Limit Exceeded

Solution code:
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
import sys
sys.setrecursionlimit(10**6)
n=N()
p=L()
size=(n+1)**2+1
ans=[0]*size
for i in range(1,n+1):
    for j in range(1,n+1):
        k=i*(n+1)+j
        ans[k]=min(i-1,j-1,n-i,n-j)
c=[1]*size
di=[-1,1,n+1,-n-1]
def f(k):
    for i in di:
        if k+i>=size:
            continue
        if ans[k]+c[k]<ans[k+i]:
            ans[k+i]-=1
            q.add(k+i)
t=0
for i in p:
    y=i%n
    if y==0:
        y=n
    x=(i+n-1)//n
    k=x*(n+1)+y
    c[k]=0
    t+=ans[k]
    q=set([k])
    while q:
        k=q.pop()
        f(k)
print(t)

Submission status: Time Limit Exceeded

Solution code:
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
import sys
sys.setrecursionlimit(10**6)
n=N()
p=L()
size=(n+1)**2+1
ans=[0]*size
for i in range(1,n+1):
    for j in range(1,n+1):
        k=i*(n+1)+j
        ans[k]=min(i-1,j-1,n-i,n-j)
c=[1]*size
di=[-1,1,n+1,-n-1]
def f(k):
    for i in di:
        if k+i>=size:
            continue
        if ans[k]+c[k]<ans[k+i]:
            ans[k+i]-=1
            f(k+i)
t=0
for i in p:
    y=i%n
    if y==0:
        y=n
    x=(i+n-1)//n
    k=x*(n+1)+y
    c[k]=0
    t+=ans[k]
    f(k)
print(t)

Submission status: Time Limit Exceeded

Solution code:
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
import sys
sys.setrecursionlimit(10**6)
n=N()
p=L()
ans=[[0]*(n+1) for i in range(n+1)]
for i in range(1,n+1):
    for j in range(1,n+1):
        ans[i][j]=min(i-1,j-1,n-i,n-j)
c=[[1]*(n+1) for i in range(n+1)]
def f(x,y):
    for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
        if 1<=x+i<=n and 1<=y+j<=n:
            if ans[x][y]+c[x][y]<ans[x+i][y+j]:
                ans[x+i][y+j]-=1
                f(x+i,y+j)
t=0
for i in p:
    y=i%n
    if y==0:
        y=n
    x=(i+n-1)//n
    c[x][y]=0
    t+=ans[x][y]
    f(x,y)
print(t)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
P = map(int, input().split())

Kcost = [min(row, N - 1 - row, clm, N - 1 - clm) for row in range(N) for clm in range(N)]

Sitting = [1] * (N * N)
Kcount = 0


def Kcheck(qsn, cdsn):
    if Kcost[cdsn] > Kcost[qsn] + Sitting[qsn]:
        Kcost[cdsn] = Kcost[qsn] + Sitting[qsn]
        queue.append(cdsn)


for sn in P:
    csn = sn - 1
    Kcount += Kcost[csn]
    Sitting[csn] = 0
    queue = [csn]

    while queue:
        qsn = queue.pop()
        div, mod = divmod(qsn, N)
        if mod: Kcheck(qsn, qsn - 1)
        if mod != N - 1: Kcheck(qsn, qsn + 1)
        if div: Kcheck(qsn, qsn - N)
        if div != N - 1: Kcheck(qsn, qsn + N)

print(Kcount)

Submission status: Time Limit Exceeded

Solution code:
import sys
from numba import njit


@njit
def main():
    Kcost = [min(row, N - 1 - row, clm, N - 1 - clm) for row in range(N) for clm in range(N)]

    Sitting = [1] * (N * N)
    Kcount = 0
    q = []


    def Kcheck(qsn, cdsn):
        if Kcost[cdsn] > Kcost[qsn] + Sitting[qsn]:
            Kcost[cdsn] = Kcost[qsn] + Sitting[qsn]
            q.append(cdsn)


    for sn in P:
        csn = sn - 1
        Kcount += Kcost[csn]
        Sitting[csn] = 0
        q = [csn]

        while q:
            qsn = q.pop()
            div, mod = divmod(qsn, N)
            if mod: Kcheck(qsn, qsn - 1)
            if mod != N - 1: Kcheck(qsn, qsn + 1)
            if div: Kcheck(qsn, qsn - N)
            if div != N - 1: Kcheck(qsn, qsn + N)

    print(Kcount)


N = int(input())
P = tuple(map(int, input().split()))

if __name__ == '__main__':
    main()

sys.exit()

Submission status: Time Limit Exceeded

Solution code:
import sys

N = int(input())
P = map(int, input().split())

Kcost = [min(row, N - 1 - row, clm, N - 1 - clm) for row in range(N) for clm in range(N)]

Sitting = [1] * (N * N)
Kcount = 0


def Kcheck(qsn, cdsn):
    if Kcost[cdsn] > Kcost[qsn] + Sitting[qsn]:
        Kcost[cdsn] = Kcost[qsn] + Sitting[qsn]
        queue.append(cdsn)


for sn in P:
    csn = sn - 1
    Kcount += Kcost[csn]
    Sitting[csn] = 0
    queue = [csn]

    while queue:
        qsn = queue.pop()
        div, mod = divmod(qsn, N)
        if mod: Kcheck(qsn, qsn - 1)
        if mod != N - 1: Kcheck(qsn, qsn + 1)
        if div: Kcheck(qsn, qsn - N)
        if div != N - 1: Kcheck(qsn, qsn + N)

print(Kcount)

sys.exit()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

N = int(input())
P = map(int, input().split())

Kcost = [min(row, N - 1 - row, clm, N - 1 - clm) for row in range(N) for clm in range(N)]

Sitting = [1] * (N * N)
Kcount = 0


def Kcheck(qsn, cdsn):
    if Kcost[cdsn] > Kcost[qsn] + Sitting[qsn]:
        Kcost[cdsn] = Kcost[qsn] + Sitting[qsn]
        queue.append(cdsn)


for sn in P:
    csn = sn - 1
    Kcount += Kcost[csn]
    Sitting[csn] = 0
    queue = [csn]
    checked = defaultdict(lambda: 0)

    while queue:
        qsn = queue.pop()

        if checked[qsn]: continue

        checked[qsn] = 1
        div, mod = divmod(qsn, N)
        if mod: Kcheck(qsn, qsn - 1)
        if mod != N - 1: Kcheck(qsn, qsn + 1)
        if div: Kcheck(qsn, qsn - N)
        if div != N - 1: Kcheck(qsn, qsn + N)

print(Kcount)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n = int(input())
Ps = list(map(lambda x: int(x)-1, input().split()))
cost = [min(i, n-1-i, j, n-1-j) for i in range(n) for j in range(n)]
exist = [1]*(n**2)


def to_idx(p):
    return divmod(p, n)


def generate_dv(i, j):
    if 0 < i:
        yield -n
    if i < n-1:
        yield n
    if 0 < j:
        yield -1
    if j < n-1:
        yield 1


def bfs(init_v):
    next_v = deque([init_v])
    exist[init_v] = 0
    while next_v:
        v = next_v.popleft()
        i, j = to_idx(v)
        for dv in generate_dv(i, j):
            if cost[v+dv] <= cost[v]+exist[v]:
                continue
            cost[v+dv] = cost[v]+exist[v]
            next_v.append(v+dv)


ans = 0
for p in Ps:
    ans += cost[p]
    bfs(p)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict


N = int(input())
P = tuple(map(int, input().split()))

Kcost = [min(row, N - 1 - row, clm, N - 1 - clm) for row in range(N) for clm in range(N)]

Sitting = [1] * (N * N)
Kcount = 0


def Kcheck(qsn, cdsn):
    if Kcost[cdsn] > Kcost[qsn] + Sitting[qsn]:
        Kcost[cdsn] = Kcost[qsn] + Sitting[qsn]
        queue.append(cdsn)


for sn in P:
    csn = sn - 1
    Kcount += Kcost[csn]
    Sitting[csn] = 0
    queue = [csn]
    checked = defaultdict(lambda: 0)

    while queue:
        qsn = queue.pop()

        if checked[qsn]: continue

        checked[qsn] = 1
        div, mod = divmod(qsn, N)
        if mod: Kcheck(qsn, qsn - 1)
        if mod != N - 1: Kcheck(qsn, qsn + 1)
        if div: Kcheck(qsn, qsn - N)
        if div != N - 1: Kcheck(qsn, qsn + N)

print(Kcount)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n = int(input())
Ps = list(map(lambda x: int(x)-1, input().split()))
cost = [min(i, n-1-i, j, n-1-j) for i in range(n) for j in range(n)]
exist = [1]*(n**2)


def to_idx(p):
    return divmod(p, n)


def to_v(i, j):
    return i*n+j


def generate_v2(v, i, j):
    if 0 < i:
        yield v-n
    if i < n-1:
        yield v+n
    if 0 < j:
        yield v-1
    if j < n-1:
        yield v+1


def bfs(init_v):
    next_v = deque([init_v])
    exist[init_v] = 0
    while next_v:
        v = next_v.popleft()
        i, j = to_idx(v)
        for v2 in generate_v2(v, i, j):
            if cost[v2] <= cost[v]+exist[v]:
                continue
            cost[v2] = cost[v]+exist[v]
            next_v.append(v2)

ans = 0
for p in Ps:
    ans += cost[p]
    bfs(p)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict


def main():
    N = int(input())
    P = tuple(map(int, input().split()))

    Kcost = [min(row, N - 1 - row, clm, N - 1 - clm) for row in range(N) for clm in range(N)]

    Sitting = [1] * (N * N)
    Kcount = 0


    def Kcheck(qsn, cdsn):
        if Kcost[cdsn] > Kcost[qsn] + Sitting[qsn]:
            Kcost[cdsn] = Kcost[qsn] + Sitting[qsn]
            queue.append(cdsn)


    for sn in P:
        csn = sn - 1
        Kcount += Kcost[csn]
        Sitting[csn] = 0
        queue = [csn]
        checked = defaultdict(lambda: 0)

        while queue:
            qsn = queue.pop()

            if checked[qsn]: continue

            checked[qsn] = 1
            div, mod = divmod(qsn, N)
            if mod: Kcheck(qsn, qsn - 1)
            if mod != N - 1: Kcheck(qsn, qsn + 1)
            if div: Kcheck(qsn, qsn - N)
            if div != N - 1: Kcheck(qsn, qsn + N)

    print(Kcount)


if __name__ == '__main__':
    main()

sys.exit()