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: Wrong Answer

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

L = [[min([i, j, N - 1 - i, N - 1 - j]) for j in range(N)] for i in range(N)]
M = N * N
V = [0] * (N * N + 1)
for i in range(1, N * N + 1):
  w = (i - 1) % N
  h = (i - w - 1) // N
  t = 0
  if w != 0:
    t |= 1 << (h * N + w)
  if w != N - 1:
    t |= 1 << (h * N + w + 2)
  if h != 0:
    t |= 1 << ((h - 1) * N + w + 1)
  if h != N - 1:
    t |= 1 << ((h + 1) * N + w + 1)
  V[i] = t

ans = 0
for i in P:
  w = (i - 1) % N
  h = (i - w - 1) // N
  ans += L[h][w]
  for j in range(1, M + 1):
    if V[i] & (1 << j):
      ww = (j - 1) % N
      hh = (j - ww - 1) // N
      if L[hh][ww] > L[h][w]:
        L[hh][ww] = L[h][w]
      V[j] |= V[i]
  L[h][w] = 0

print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    __slots__ = ["_size", "_first_idx", "_parents", "_cost"]

    def __init__(self, size: int, N: int, first_index: int = 0) -> None:
        self._size = size
        self._first_idx = first_index
        self._parents = [-1] * (size + first_index)

        cost = [0] * (N * N)
        for r in range(N):
            dr = min(r, N - 1 - r)
            for c in range(N):
                dc = min(c, N - 1 - c)
                cost[r * N + c] = min(dr, dc)
        self._cost = cost

    def find(self, x: int) -> int:
        """Find the group (root) of vertex x"""
        if self._parents[x] < 0:
            return x
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]

    def is_same(self, x: int, y: int) -> bool:
        """Return whether two vertices x and y are in the same group or not."""
        return self.find(x) == self.find(y)

    def unite(self, x: int, y: int) -> None:
        """Unite two groups of vertices x and y."""
        c = min(self._cost[x], self._cost[y])
        x, y = self.find(x), self.find(y)
        if x == y:
            self._cost[x] = min(self._cost[x], c)
            return

        if self._parents[x] > self._parents[y]:
            x, y = y, x
        self._parents[x] += self._parents[y]
        self._parents[y] = x
        self._cost[x] = min(self._cost[x], self._cost[y], c)

    def get_size(self, x: int) -> int:
        """Get the size of the group vertex x belongs"""
        return -self._parents[self.find(x)]

    def get_cost(self, x: int) -> int:
        x = self.find(x)
        return self._cost[x]

    def set_cost(self, x: int, val: int):
        x = self.find(x)
        self._cost[x] = min(self._cost[x], val)


def main():
    N = int(input())
    *p, = (int(x) - 1 for x in input().split())

    g = [[set() for _ in range(N)] for _ in range(N)]
    for r in range(N):
        for c in range(N):
            if r > 0:
                g[r][c].add((r - 1, c))
            if c > 0:
                g[r][c].add((r, c - 1))
            if r < N - 1:
                g[r][c].add((r + 1, c))
            if c < N - 1:
                g[r][c].add((r, c + 1))

    uf = UnionFind(N * N, N)

    ex = [[0] * N for _ in range(N)]

    ans = 0
    for pi in p:
        r, c = divmod(pi, N)

        t = uf.get_cost(pi)
        for nr, nc in g[r][c]:
            if uf.is_same(nr * N + nc, pi):
                continue
            else:
                t = min(t, uf.get_cost(nr * N + nc) + (0 if ex[nr][nc] else 1))
        ans += t

        uf.set_cost(pi, t)
        ex[r][c] = 1
        for nr, nc in g[r][c]:
            uf.set_cost(nr * N + nc, t)

            if ex[nr][nc]:
                uf.unite(nr * N + nc, pi)

    print(ans)


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
#
# sys.setrecursionlimit(10 ** 7)
#
# (int(x)-1 for x in input().split())
# rstrip()
#
# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok

Submission status: Wrong Answer

Solution code:
import numpy as np

n = int( input() )
p = [ int( px ) for px in input().split() ]
print( p )

ans = int( 0 )
ex  = [ 1 ] * ( n*n )

for i in range( n*n ):
#    print( i )
#    dp = np.zeros( ( n, n ) )
#    for j in range( n ):
#        dp[ : ] = n*n
    dp = [ n*n ] * ( n*n )
    dp[ p[ i ] - 1 ] = 0
#    print( dp )

    for l in range( n*n ):
        for j in range( n*n ):
#            print( j % n )
            if j <= n-1:
                dp[ j ] = min( [ dp[ j ], dp[ j+n ] + ex[ j ] ] )
            if j % n == 0:
                dp[ j ] = min( [ dp[ j ], dp[ j+1 ] + ex[ j ] ] )
            if j % n == n-1:
                dp[ j ] = min( [ dp[ j ], dp[ j-1 ] + ex[ j ] ] )
            if j >= n*n-n:
                dp[ j ] = min( [ dp[ j ], dp[ j-n ] + ex[ j ] ] )
            if j >= n and j < n*n-n and j % n != 0 and j % n != n-1:
                dmin = min( [ dp[j-n], dp[j+n], dp[j-1], dp[j+1] ] )
                dp[ j ] = min( [ dp[ j ], dmin + ex[ j ] ] )

#    print( dp )
    hate = n*n
    for j, dpj in enumerate( dp ):
        if j <= n-1 or j >= n*n-n or j % n == 0 or j % n == n-1:
            hate = min( hate, dpj )

#    print( hate )
    ans = ans + hate

#    print( dp )
    ex[ p[ i ] - 1 ] = 0
#    print( ex )


print( ans )

Submission status: Wrong Answer

Solution code:
import numpy as np


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

end = {0, 1}
se = {1, n}
f_l = {i for i in range(1, n+1)}
e_l = {n * n - i for i in range(0, n)}
ans = 0

s = set()
nd = np.arange(1, (n * n) + 1).reshape((n, n))
nd_t = nd.transpose()
for i in range(len(p)):
    mod = p[i] % n
    s.add(p[i])
    if mod in end or p[i] in f_l or p[i] in e_l:
        continue
    line = p[i] // n
    l1 = nd[line]
    l2 = nd_t[line]

    right = set(l1[:mod])
    left = set(l1[mod:])
    front = set(l2[:mod])
    rear = set(l2[mod:])
    if s >= right or s >= left or s >= front or s >= rear:
        continue

    hate = len(right - s)
    hate = min(hate, len(left - s))
    hate = min(hate, len(front - s))
    hate = min(hate, len(rear - s))
    s.add(p[i])
    ans += hate

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
P = list(map(int,input().split()))
import heapq
def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * (N**2)
    used = [True] * (N**2) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d
edge = [[] for i in range(N**2)]
for i in range(N):
    for j in range(N):
        x = i*N + j
        if (i == 0) or (i == N - 1) or (j == 0) or (j == N-1):
            edge[x].append([0,0])
            edge[0].append([0,x])
            continue
        if j != 0:
            edge[x].append([1,x-1])
            edge[x-1].append([1,x])
        if j != N-1:
            edge[x].append([1,x+1])
            edge[x+1].append([1,x])
        if i != 0:
            edge[x].append([1,x-N])
            edge[x-N].append([1,x])
        if i != N -1:
            edge[x].append([1,x+N])
            edge[x+N].append([1,x])
ans = 0
for p in P:
    x = p-1
    a = x // N
    b = x % N 
    ans += dijkstra_heap(0)[x]
    if b != 0:
        edge[x].append([0,x-1])
        edge[x-1].append([0,x])
    if b != N-1:
        edge[x].append([0,x+1])
        edge[x+1].append([0,x])
    if a != 0:
        edge[x].append([0,x-N])
        edge[x-N].append([0,x])
    if a != N-1:
        edge[x].append([0,x+N])
        edge[x+N].append([0,x])
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque
import sys
import copy
input = sys.stdin.buffer.readline

N = int(input())


def coordinate(P):
    p, q = divmod(P, N)
    if q == 0:
        return p - 1, N - 1
    else:
        return p, q - 1


def around(i, j):
    ans = []
    if i > 0:
        ans.append((i - 1, j))
    if i < N - 1:
        ans.append((i + 1, j))
    if j > 0:
        ans.append((i, j - 1))
    if j < N - 1:
        ans.append((i, j + 1))
    return ans


def inside(i, j):
    ans = []
    if N % 2 == 1 and i == j == N // 2:
        return ans
    if N // 2 <= i:
        ans.append((i - 1, j))
    else:
        ans.append((i + 1, j))
    if N // 2 <= j:
        ans.append((i, j - 1))
    else:
        ans.append((i, j + 1))
    return ans


def main():
    P_list = list(map(int, input().split()))
    costs = []
    for _ in range(N):
        costs.append([0] * N)
    for i in range(N):
        for j in range(N):
            costs[i][j] = min([i - 0, N - 1 - i, j - 0, N - 1 - j])
    original_costs = copy.deepcopy(costs)
    ans = 0
    got_out = defaultdict(bool)

    for P in P_list:
        i, j = coordinate(P)
        cost = costs[i][j]
        ans += cost
        got_out[(i, j)] = True
        if cost < original_costs[i][j]:
            li = around(i, j)
        else:
            li = inside(i, j)
        s = {(i, j)}
        # 抜けた席の周辺
        d = deque()
        for t in li:
            if not got_out[t]:
                costs[t[0]][t[1]] = min(costs[t[0]][t[1]], cost)
            else:
                d.append(t)
            s.add(t)

        while d:
            e = d.popleft()
            if costs[e[0]][e[1]] == original_costs[e[0]][e[1]]:
                li = inside(e[0], e[1])
            else:
                li = around(e[0], e[1])
            for t in (set(li) - s):
                if not got_out[t]:
                    costs[t[0]][t[1]] = min(costs[t[0]][t[1]], cost)
                else:
                    d.append(t)
                s.add(t)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

cost = [[0]*n for _ in range(n)]
for i in range(n):
    for j in range(n):
        cost[i][j]=min(min(i,n-i-1),min(j,n-j-1))
dx=[1,0,-1,0]
dy=[0,1,0,-1]
ans=0
for i in range(n*n):
    pi = (p[i]-1)%n
    pj = (p[i]-1)//n
    cnt=cost[pi][pj]
    ans+=cost[pi][pj]
    cost[pi][pj]=-(i+1)
    d=deque()
    d.append((pi,pj,cnt))
    while d:
        ni,nj,cnt=d.popleft()
        for j in range(4):
            nwi = ni+dx[j]
            nwj = nj+dy[j]
            if not(0<=nwi<n):
                continue
            if not(0<=nwj<n):
                continue
            if cost[nwi][nwj]>=0 and cnt>=cost[nwi][nwj]:
                continue
            if 0>cost[nwi][nwj]>-(i+1):
                cost[nwi][nwj]=-(i+1)
                d.append((nwi,nwj,cnt))
                continue
            if cost[nwi][nwj]==-(i+1):
                continue
            cost[nwi][nwj]=cnt
            d.append((nwi,nwj,cnt+1))

print(ans)

Submission status: Wrong Answer

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

p2i = {}

for i in range(N*N):
  p2i[i] = [(P[i]-1)//N, (P[i]-1)%N]
print(p2i)

table = [[0 for j in range(N)] for i in range(N)]
for i in range(N*N):
    table[p2i[i][0]][p2i[i][1]] = i
print(table)

S = 0

for n in range(N*N):
  above = 0
  below = 0
  left = 0
  right = 0

  if p2i[n][0] != 0 and p2i[n][0] != 0:
    for i in range(p2i[n][0]):
      above += (table[i][p2i[n][1]] != 0)
    for i in range(p2i[n][0]+1, N):
      below += (table[i][p2i[n][1]] != 0)
  
  if p2i[n][1] != 0 and p2i[n][1] != 0:
    for i in range(p2i[n][1]):
      left += (table[p2i[n][0]][i] != 0)
    for i in range(p2i[n][1]+1, N):
      right += (table[p2i[n][0]][i] != 0)

  S += min(above, below, left, right)
  table[p2i[n][0]][p2i[n][1]] = 0

print(S)

Submission status: Wrong Answer

Solution code:
n = int(input())
N = n
ha = 0
for i in range(1,11):
    if n*2 <= 2**i:
        ha = 2**i
        break
ha -= 1
# print(ha)
def update_yoko(x,y,num):
    x += n-1 # 1番下の層におけるインデックス
    yoko[y][x] = num
    # print("x1",x)
    # 層をのぼりながら値を更新
    while x > 0:
        x = (x-1)// 2 # 1つ上の層のインデックス(完全二分木における親)
        # print("x",x)
        # 下の層2つの和を代入(完全二分木における子同士の和)
        yoko[y][x] = yoko[y][x*2+1] + yoko[y][x*2+2]

def update_tate(x,y,num):
    y += n-1 # 1番下の層におけるインデックス
    tate[y][x] = num
    # 層をのぼりながら値を更新
    while y > 0 :
        y = (y-1)//2 # 1つ上の層のインデックス(完全二分木における親)
        # 下の層2つの和を代入(完全二分木における子同士の和)
        tate[y][x] = tate[y*2+1][x] + tate[y*2+2][x]
def query_yoko(l, r, y,k=0, L=0, R=None):#y固定
    # Rの初期化
    # print(l,r)
    if R is None:
        R = N

    # もし区間[l,r)と区間[L,R)が交差しないならば0を返す
    if R <= l or r <= L:
        return 0

    # 区間[L,R)が区間[l,r)に完全に収まっていればその値を返す
    if l <= L and R <= r:
        return yoko[y][k]

    # それ以外のとき、木を潜って2つの子を見る
    else:
        lres = query_yoko(l, r, y,k*2+1, L, (L+R) >> 1)
        rres = query_yoko(l, r,y, k*2+2, (L+R) >> 1, R)
        return lres + rres

def query_tate(l, r, x,k=0, L=0, R=None):#y固定
    # Rの初期化
    if R is None:
        R = N
    # もし区間[l,r)と区間[L,R)が交差しないならば0を返す
    if R <= l or r <= L:
        return 0

    # 区間[L,R)が区間[l,r)に完全に収まっていればその値を返す
    if l <= L and R <= r:
        return tate[k][x]

    # それ以外のとき、木を潜って2つの子を見る
    else:
        lres = query_tate(l, r,x, k*2+1, L, (L+R) >> 1)
        rres = query_tate(l, r,x, k*2+2, (L+R) >> 1, R)
        return lres + rres
# def show():
#     for i in range(len(tate)):
        # print(tate[i],yoko[i])

tate = [[0 for _ in range(ha)]for _ in range(ha)]
yoko = [[0 for _ in range(ha)]for _ in range(ha)]

for i in range(n*n):#構築
    y ,x = divmod(i,n)
    # print("koutiku",i,x,y)
    update_tate(x,y,1)
    update_yoko(x,y,1)
    # show()
a = list(map(int,input().split()))
ans = 0
# print(a)
for i in range(n*n):
    yy ,xx = divmod(a[i]-1,n)
    y = yy
    x = xx
    update_tate(x,y,0)
    update_yoko(x,y,0)
    q1 = query_yoko(0,x,y)
    q2 = query_yoko(x,n,y)
    q3 = query_tate(0,y,x)
    q4 = query_tate(y,n,x)
    # print("f",x,y)

    # show()
    ans += min([q1,q2,q3,q4])
    # print(x,y,a[i],ans)
    # print(q1,q2,q3,q4)
    # print("------------")
print(ans)

Submission status: Wrong Answer

Solution code:
from random import shuffle
N = int(input())
P = [int(c)-1 for c in input().split()]
#shuffle(P)
import numba
import numpy as np
#N = int(input())
#P = [int(c)-1 for c in input().split()]
# Mat = [[min(y, N-1-y, x, N-1-x) for y in range(N)] for x in range(N)]
# Mat = np.array(Mat)
@numba.njit()
def proc(N, P):
    ans = 0
    Removed = np.zeros((N, N), dtype=np.int32)
    closed = np.zeros((N,N), dtype=np.int32)
    Mat = np.zeros((N, N), dtype=np.int32)
    Dy, Dx = [1,0,-1,0], [0,1,0,-1]

    for y in range(N):
        for x in range(N):
            Mat[y, x] = min(y, N-1-y, x, N-1-x)
    for i in range(N):
        p = P[i]
        y, x = divmod(p, N)
        ans += Mat[y][x]
        #print(p, Mat[y][x])
        Removed[y][x] = True
        #Mat[y][x] -= 1
        st = [(y, x)]
        clsd = [(y, x)]
        closed[y][x] = True
        while st:
            vy, vx = st.pop()
            vr = Removed[vy][vx]
            val = Mat[vy][vx]
            for dy, dx in zip(Dy, Dx):
                uy = vy + dy
                ux = vx + dx
                if not (0<=uy<N and 0<=ux<N):
                    continue
                ur = Removed[uy][ux]
                if vr:
                    if Mat[uy][ux] >= val+1:
                        Mat[uy][ux] = val
                        st.append((uy, ux))
                else:
                    if Mat[uy][ux] >= val+2:
                        Mat[uy][ux] = val+1
                        st.append((uy, ux))
        for y, x in clsd:
            closed[y][x] = False
    # for m in Mat:
    #     print(m)
    print(ans)
proc(N, P)

Submission status: Wrong Answer

Solution code:
n=int(input())
p=list(map(int,input().split()))
for i in range(n*n):p[i]-=1
b=[n*[1]for _ in range(n)]
def solve(p):
  i,j=divmod(p,n)
  ans=[n*[-1]for _ in range(n)]
  ans[i][j]=0
  Q=[[]for _ in range(n*n)]
  Q[0]=[(i,j)]
  dij=((0,1),(0,-1),(1,0),(-1,0))
  for i in range(n*n):
    for i,j in Q[i]:
      for di,dj in dij:
        if i+di in [-1,n] or j+dj in [-1,n]:continue
        if ans[i+di][j+dj]!=-1:continue
        if b[i+di][j+dj]!=0:
          Q[i+1].append((i+di,j+dj))
          ans[i+di][j+dj]=ans[i][j]+1
        else:
          Q[i].append((i+di,j+dj))
          ans[i+di][j+dj]=ans[i][j]
  anss=n*n
  for i in range(n):
    if ans[0][i]!=-1:anss=min(anss,ans[0][i])
    if ans[-1][i]!=-1:anss=min(anss,ans[-1][i])
    if ans[i][0]!=-1:anss=min(anss,ans[i][0])
    if ans[i][-1]!=-1:anss=min(anss,ans[i][-1])
  return anss
ans=0
for i in p:
  ans+=solve(i)
  ii,jj=divmod(i,n)
  b[ii][jj]=0
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
P = np.array(list(map(int, readline().split())))

data = np.ones((N,N))
ans = 0

# 座ってる場所のindex判定
def seat_index(seat_num):
  div,mod = divmod(seat_num, N)
  if mod % N == 0:
    col = div-1
    row = N-1
  else:
    col = div
    row = mod-1
  return [col,row]

# 嫌う人数判定
def check(col, row):
  data[col][row] = 0
  if col == 0 or col == N or row == 0 or row == N or np.sum(data[col,:row]) == 0 or np.sum(data[col,:row]) == 0 or np.sum(data[:col,row]) == 0 or np.sum(data[col+1:,row]) == 0:
    return 0
  else:
    return np.min(np.array([np.sum(data[col,:row]),np.sum(data[col,row:])
                       ,np.sum(data[:col,row]),np.sum(data[col:,row])]))


for i in P:
  seat_num = i
  col,row = seat_index(seat_num)
  ans += int(check(col,row))


print(ans)

Submission status: Wrong Answer

Solution code:
import math,bisect
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
  
n = int(readline())
a = [int(i) for i in readline().split()]
chk_y = [[0] for i in range(n)]
chk_t = [[0] for i in range(n)]
ans = 0
a = a[::-1]
    
for j in range(n*n):
  c = a[j]
  Y = math.ceil(c/n)
  T = c%n
  bisect.insort(chk_y[Y-1],c)
  bisect.insort(chk_t[T-1],c)
  
  if T > 1 and 1 < Y < n:
    if chk_y[Y-1][1] < c < chk_y[Y-1][-1] and chk_t[T-1][1] < c < chk_t[T-1][-1]:
      g = bisect.bisect_left(chk_y[Y-1],c)
      w = bisect.bisect_left(chk_t[T-1],c)
      ans += min(len(chk_y[Y-1])-g-1,g-1,len(chk_t[T-1])-w-1,w-1)
      #print(c,ans)

print(ans)

Submission status: Wrong Answer

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


M = 500

import numpy as np
pot = np.full((N+2, N+2), M)
pot[0,: ] = -1
pot[-1,:] = -1
pot[:, 0] = -1
pot[:, -1]= -1

def rep(X):
    i = 1
    while i <= X:
        yield (X+1)*((i+1)%2) + (i+1)//2 * (-1)**((i+1)%2)
        i += 1

def localmin(a, i, j):
    a[i, j] = min(a[i-1, j], a[i, j-1], a[i, j+1], a[i+1, j]) + 1
    
for i in rep(N):
    for j in rep(N):
        localmin(pot, i, j)

def leave(a, i, j):
    c = a[i, j]
    localmin(a, i, j)
    return c


cost = 0

for p in P:
    i = (p-1)//N + 1
    j = (p-1)%N + 1
    cost += leave(pot, i,j)

print(cost)

Submission status: Wrong Answer

Solution code:
from sys import stdin, stdout
import heapq
import cProfile
from collections import Counter, defaultdict, deque
from functools import reduce
import math

def get_int():
    return int(stdin.readline().strip())


def get_tuple():
    return map(int, stdin.readline().split())


def get_list():
    return list(map(int, stdin.readline().split()))

def bfs(x,y,n,dp):
    queue = [(x,y)]
    while queue:
        i,j = queue.pop(0)
        #print("A",i,j)
        if dp[i][j] == 1 or i==0 or i==n-1 or j==0 or j==n-1:
            dp[x][y] = 1
            return True
        f = 0
        for i,j in [[i-1,j],[i,j-1],[i+1,j],[i,j+1]]:
            if 0<=i<n and 0<=j<n and dp[i][j]==1:
                f = 1
                queue.append((i,j))
        #print(queue)
        if f==0:
            break
    #print(x,y)
    dp[x][y] = 1
    return False


def solve():
    n = int(input())
    people = list(map(int,input().strip().split()))
    hash = dict()
    dp = []
    c = 1
    for i in range(n):
        tmp = []
        for j in range(n):
            hash[c] = [i,j]
            tmp.append(0)
            c += 1
        dp.append(tmp)
    #print(hash)
    #print(dp)
    ans = 0
    for val in people:
        value = hash[val]
        i,j = value[0],value[1]
        #print(val,i,j,dp)
        if not bfs(i,j,n,dp):
            ans += 1
        #print("a is",ans)
    print(ans)



def main():
    solve()


TestCases = False

if TestCases:
    for i in range(get_int()):
        main()
else:
    main()

Submission status: Wrong Answer

Solution code:
INF = float("inf")
n = int(input())
P = list(map(int, input().split()))
T = [[INF] * (n+2) for _ in range(n+2)]
rest = [[1] * (n+2) for _ in range(n+2)]
ans = 0
for i in range(n+2):
    if i == 0 or i == n+1:
        for j in range(n+2):
            rest[i][j] = INF
    else:
        rest[i][0] = INF
        rest[i][n+1] = INF
        T[1][i] = 1
        T[n][i] = 1
        T[i][1] = 1
        T[n][1] = 1
def check(i,j):
    mn = min(T[i-1][j], T[i][j-1], T[i][j+1], T[i+1][j])
    tmp = mn + rest[i][j]
    if tmp < T[i][j]:
        T[i][j] = tmp

for p in P:
    s = (p-1) // n + 1
    t = (p-1) % n + 1
    rest[s][t] = 0
    if s in (1,n) or t in (1,n):
        T[s][t] = 0
        continue

    for i in range(2, n):
        for j in range(2, n):
            check(i, j)
            check(i, n-j+1)
            check(n-i+1, j)
            check(n-i+1, n-j+1)
    for i in range(2, n):
        for j in range(2, n):
            check(i, j)
            check(i, n-j+1)
            check(n-i+1, j)
            check(n-i+1, n-j+1)

    ans += T[s][t]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**5)
N = int(input())
P = list(map(int, input().split()))

cost = [[N]*N for i in range(N)]

for i in range(N):
    cost[i][0] = 0
    cost[i][-1] = 0
    cost[0][i] = 0
    cost[-1][i] = 0

for i in range(1, N-1):
    for j in range(1, N-1):
        cost[i][j] = min(cost[i+1][j], cost[i-1][j],
                         cost[i][j+1], cost[i][j-1]) + 1

s = set()
def update(i, j):
    if i > 0:
        if cost[i][j]+1 == cost[i-1][j]:
            if (i-1, j) in s:
                cost[i-1][j] -= 1
                update(i-1, j)

            else:
                update(i-1, j)
                cost[i-1][j] -= 1
    if i < N-1:
        if cost[i][j]+1 == cost[i+1][j]:
            if (i+1, j) in s:
                cost[i+1][j] -= 1
                update(i+1, j)
            else:
                update(i+1, j)
                cost[i+1][j] -= 1
    if j > 0:
        if cost[i][j]+1 == cost[i][j-1]:
            if (i, j-1) in s:
                cost[i][j-1] -= 1
                update(i, j-1)
            else:
                update(i, j-1)
                cost[i][j-1] -= 1
    if j < N-1:
        if cost[i][j]+1 == cost[i][j+1]:
            if (i, j+1) in s:
                cost[i][j+1] -= 1
                update(i, j+1)
            else:
                update(i, j+1)
                cost[i][j+1] -= 1


ans = 0

for x in P:
    i = (x - 1) // N
    j = (x-1) % N
    ans += cost[i][j]
    # if cost[i][j]:
    #     print(x)
    #     print(*cost, sep='\n')
    #     print(ans)
    update(i, j)
    s.add((i, j))

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
class UnionFind:
    def __init__(self, n):
        class KeyDict(dict):
            # 辞書にないときの対応
            def __missing__(self,key):
                self[key] = key
                return key
        self.parent = KeyDict()
        self.rank = defaultdict(int)
        self.weight = defaultdict(int)

    # 根を探す
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            # 経路圧縮
            # 自分自身じゃない場合は、上にさかのぼって検索(再帰的に)
            y = self.find(self.parent[x])           
            self.weight[x] += self.weight[self.parent[x]]   #圧縮時にweightを更新(和)
            self.parent[x] = y      #親の置き換え(圧縮)
            return self.parent[x]

    # 結合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        # 低い方を高い方につなげる(親のランクによる)
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
        
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

    ### 重み付き
    def weighted_union(self, x, y, w):
        # print("unite",x,y,w,self.weight)
        px = self.find(x)
        py = self.find(y)
        # 低い方を高い方につなげる(親のランクによる)
        # if px == py: return 0
        if self.rank[px] < self.rank[py]:
            self.parent[px] = py
            self.weight[px] = - w - self.weight[x] + self.weight[y]
        else:
            self.parent[py] = px
            self.weight[py] =  w + self.weight[x] - self.weight[y]
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return 0

    # 判定
    def judge(self, x, y):
        return self.find(x) == self.find(y)
n = int(input())
Ps = list(map(int, input().split()))
def hw(p):
    h = (p-1)//n
    w = (p-1)%n
    return h,w

def toP(h,w):
    return h * n + w + 1

fs = [[0]*n for i in range(n)]
for i in range(n):
    x = min(i,n-1-i)
    for j in range(n):
        y = min(j,n-1-j)
        fs[i][j] = min(x,y)

ans = 0
mvs = [(1,0),(-1,0),(0,1),(0,-1)]

uf = UnionFind(n**2)

dists = [0] * (n**2+1)
for i in range(1,n**2+1):
    h,w = hw(i)
    dists[i] = fs[h][w]
visited = [False] * (n**2+1)

for p in Ps:
    h,w = hw(p) 
    # a = dists[uf.find(p)]
    a = dists[p]
    for dh,dw in mvs:   
        if 0<=h+dh<n and 0<=w+dw<n:
            p1 = uf.find(p)
            p2 = uf.find(toP(h+dh,w+dw))
            if not visited[toP(h+dh, w+dw)]:
                x = dists[p2] + 1
            a = min(x, a)
            if p1 != p2:
                if dists[p1] <= dists[p2]:
                    dists[p2] = dists[p1]
                else:
                    dists[p1] = dists[p2]
                uf.union(p1,p2)
    ans += a
print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    __slots__ = ["_size", "_first_idx", "_parents", "_cost"]

    def __init__(self, size: int, N: int, first_index: int = 0) -> None:
        self._size = size
        self._first_idx = first_index
        self._parents = [-1] * (size + first_index)

        cost = [0] * (N * N)
        for r in range(N):
            dr = min(r, N - 1 - r)
            for c in range(N):
                dc = min(c, N - 1 - c)
                cost[r * N + c] = min(dr, dc)
        self._cost = cost

    def find(self, x: int) -> int:
        """Find the group (root) of vertex x"""
        if self._parents[x] < 0:
            return x
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]

    def is_same(self, x: int, y: int) -> bool:
        """Return whether two vertices x and y are in the same group or not."""
        return self.find(x) == self.find(y)

    def unite(self, x: int, y: int) -> None:
        """Unite two groups of vertices x and y."""
        c = min(self._cost[x], self._cost[y])
        x, y = self.find(x), self.find(y)
        if x == y:
            self._cost[x] = min(self._cost[x], c)
            return

        if self._parents[x] > self._parents[y]:
            x, y = y, x
        self._parents[x] += self._parents[y]
        self._parents[y] = x
        self._cost[x] = min(self._cost[x], self._cost[y], c)

    def get_size(self, x: int) -> int:
        """Get the size of the group vertex x belongs"""
        return -self._parents[self.find(x)]

    def get_cost(self, x: int) -> int:
        x = self.find(x)
        return self._cost[x]

    def set_cost(self, x: int, val: int):
        x = self.find(x)
        self._cost[x] = min(self._cost[x], val)


def main():
    N = int(input())
    *p, = (int(x) - 1 for x in input().split())

    g = [[set() for _ in range(N)] for _ in range(N)]
    for r in range(N):
        for c in range(N):
            if r > 0:
                g[r][c].add((r - 1, c))
            if c > 0:
                g[r][c].add((r, c - 1))
            if r < N - 1:
                g[r][c].add((r + 1, c))
            if c < N - 1:
                g[r][c].add((r, c + 1))

    uf = UnionFind(N * N, N)

    ex = [[0] * N for _ in range(N)]

    ans = 0
    for pi in p:
        r, c = divmod(pi, N)

        t = uf.get_cost(pi)
        for nr, nc in g[r][c]:
            if uf.is_same(nr * N + nc, pi):
                continue
            else:
                t = min(t, uf.get_cost(nr * N + nc) + (0 if ex[nr][nc] else 1))
        ans += t

        uf.set_cost(pi, t)
        ex[r][c] = 1
        for nr, nc in g[r][c]:
            if ex[nr][nc]:
                uf.unite(nr * N + nc, pi)

    print(ans)


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
#
# sys.setrecursionlimit(10 ** 7)
#
# (int(x)-1 for x in input().split())
# rstrip()
#
# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok