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:
from numba import jit
from collections import deque
import numpy as np

def main():
  N=int(input())
  S=list(map(int,input().split()))
  count=0
  P=np.ones((N*N+1))
  d=np.zeros((N*N+1))
  que=deque()
  for i in range(N*N):
    player=S[i]
    P[player]=0
    que.clear()
    que.append((player,0))
    d[player]=i+1

    while que:
      kouho,j=que.popleft()
      if kouho%N==0:
        break
      if kouho%N==1:
        break
      if kouho+N>N*N:
        break
      if kouho<N:
        break

      if d[kouho+N]<i+1:
        if P[kouho+N]==1:
          que.append((kouho+N,j+1))
          d[kouho+N]=i+1
        else:
          que.appendleft((kouho+N,j))
          d[kouho+N]=i+1

      if d[kouho-N]<i+1:
        if P[kouho-N]==1:
          que.append((kouho-N,j+1))
          d[kouho-N]=i+1
        else:
          que.appendleft((kouho-N,j))
          d[kouho-N]=i+1

      if d[kouho+1]<i+1:
        if P[kouho+1]==1:
          que.append((kouho+1,j+1))
          d[kouho+1]=i+1
        else:
          que.appendleft((kouho+1,j))
          d[kouho+1]=i+1

      if d[kouho-1]<i+1:
        if P[kouho-1]==1:
          que.append((kouho-1,j+1))
          d[kouho-1]=i+1
        else:
          que.appendleft((kouho-1,j))
          d[kouho-1]=i+1
    count+=j

  print(count)

def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', '(i8[:],)')(main)
    cc.compile()

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np

def main():
  N=int(input())
  S=list(map(int,input().split()))
  count=0
  P=np.ones((N*N+1))
  d=np.zeros((N*N+1))
  que=deque()
  for i in range(N*N):
    player=S[i]
    P[player]=0
    que.clear()
    que.append((player,0))
    d[player]=i+1

    while que:
      kouho,j=que.popleft()
      if kouho%N==0:
        break
      if kouho%N==1:
        break
      if kouho+N>N*N:
        break
      if kouho<N:
        break

      if d[kouho+N]<i+1:
        if P[kouho+N]==1:
          que.append((kouho+N,j+1))
          d[kouho+N]=i+1
        else:
          que.appendleft((kouho+N,j))
          d[kouho+N]=i+1

      if d[kouho-N]<i+1:
        if P[kouho-N]==1:
          que.append((kouho-N,j+1))
          d[kouho-N]=i+1
        else:
          que.appendleft((kouho-N,j))
          d[kouho-N]=i+1

      if d[kouho+1]<i+1:
        if P[kouho+1]==1:
          que.append((kouho+1,j+1))
          d[kouho+1]=i+1
        else:
          que.appendleft((kouho+1,j))
          d[kouho+1]=i+1

      if d[kouho-1]<i+1:
        if P[kouho-1]==1:
          que.append((kouho-1,j+1))
          d[kouho-1]=i+1
        else:
          que.appendleft((kouho-1,j))
          d[kouho-1]=i+1
    count+=j

  print(count)

main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    M=N**2
    P=tuple(map(int1,input().split()))
    d=[0]*M
    for i in range(N):
        for j in range(N):
            d[i*N+j]=min(min(i,N-1-i),min(j,N-1-j))
    used=[1]*M
    ans=0
    que=[]
    for p in P:
        ans+=d[p]
        used[p]=0
        que.append(p)
        while que:
            x=que.pop()
            for ddx in (-1,1,-N,N):
                nx=x+ddx
                if 0<=nx<M:
                    if used[x]==0 and d[nx]-d[x]>=1:
                        d[nx]-=1
                        que.append(nx)
                    elif used[x]==1 and d[nx]-d[x]>=2:
                        d[nx]-=1
                        que.append(nx)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
M=N**2
P=tuple(map(int1,input().split()))
d=[0]*M
for i in range(N):
    for j in range(N):
        d[i*N+j]=min(min(i,N-1-i),min(j,N-1-j))
used=[1]*M
ans=0
que=deque()
for p in P:
    ans+=d[p]
    used[p]=0
    que.append(p)
    while que:
        x=que.popleft()
        for ddx in (-1,1,-N,N):
            nx=x+ddx
            if 0<=nx<M:
                if used[x]==0 and d[nx]-d[x]>=1:
                    d[nx]-=1
                    que.append(nx)
                elif used[x]==1 and d[nx]-d[x]>=2:
                    d[nx]-=1
                    que.append(nx)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush
import sys
input = sys.stdin.readline
n = int(input())
P = list(map(int, input().split()))
inf = 10 ** 9
away = [[False] * n for _ in range(n)]

def dijkstra(sx, sy, d):
    que = []
    d[sx][sy] = 0
    heappush(que, (0, sx, sy))

    while len(que):
        dist, cx, cy = heappop(que)

        if d[cx][cy] < dist:
            continue
        for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            tx, ty = cx + dx, cy + dy
            if 0 <= tx < n and 0 <= ty < n:
                if away[tx][ty]:
                    cost = 0
                else:
                    cost = 1
                if d[tx][ty] > dist + cost:
                    d[tx][ty] = dist + cost
                    heappush(que, (d[tx][ty], tx, ty))
            else:
                return d[cx][cy]

ans = 0
for p in P:
    row, line = (p-1) // n, (p-1) % n
    d = [[inf] * n for _ in range(n)]
    ans += dijkstra(row, line, d)
    away[row][line] = True

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    M=N**2
    P=tuple(map(int1,input().split()))
    d=[0]*M
    for i in range(N):
        for j in range(N):
            d[i*N+j]=min(min(i,N-1-i),min(j,N-1-j))
    used=[1]*M
    ans=0
    que=deque()
    for p in P:
        ans+=d[p]
        used[p]=0
        que.append(p)
        while que:
            x=que.popleft()
            for ddx in (-1,1,-N,N):
                nx=x+ddx
                if 0<=nx<M:
                    if used[x]==0 and d[nx]-d[x]>=1:
                        d[nx]-=1
                        que.append(nx)
                    elif used[x]==1 and d[nx]-d[x]>=2:
                        d[nx]-=1
                        que.append(nx)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush
n = int(input())
P = list(map(int, input().split()))
inf = 10 ** 9
away = [[False] * n for _ in range(n)]

def dijkstra(sx, sy, d):
    que = []
    d[sx][sy] = 0
    heappush(que, (0, sx, sy))

    while len(que):
        dist, cx, cy = heappop(que)

        if d[cx][cy] < dist:
            continue
        for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            tx, ty = cx + dx, cy + dy
            if 0 <= tx < n and 0 <= ty < n:
                if away[tx][ty]:
                    cost = 0
                else:
                    cost = 1
                if d[tx][ty] > dist + cost:
                    d[tx][ty] = dist + cost
                    heappush(que, (d[tx][ty], tx, ty))
            else:
                return d[cx][cy]

ans = 0
for p in P:
    row, line = (p-1) // n, (p-1) % n
    d = [[inf] * n for _ in range(n)]
    ans += dijkstra(row, line, d)
    away[row][line] = True

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

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

def dim1(x,y):
    return x*N+y

DP=[0]*(N*N)
for i in range(N):
    for j in range(N):
        DP[dim1(i,j)]=min(i,j,N-1-i,N-1-j)

USED=[0]*(N*N)
ANS=0

def dir4(x):
    if x-N>=0:
        yield x-N
    if x+N<N*N:
        yield x+N
    if x%N!=0:
        yield x-1
    if x%N!=N-1:
        yield x+1

for p in P:
    p-=1
    #q,r=divmod(p-1,N)
    ANS+=DP[p]
    DP[p]-=1
    USED[p]=1

    Q=deque([p])

    while Q:
        x=Q.popleft()

        for z in dir4(x):
            if USED[z]==1 and DP[z]>DP[x]:
                DP[z]=DP[x]
                Q.append(z)
                    
            elif DP[z]>DP[x]+1:
                DP[z]=DP[x]+1
                Q.append(z)
    
    #for d in DP:
    #    print(*d)
    #print(ANS)
    #print()
print(ANS)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    M=N**2
    P=tuple(map(int1,input().split()))
    d=[0]*M
    for i in range(N):
        for j in range(N):
            d[i*N+j]=min(min(i,N-1-i),min(j,N-1-j))
    used=[1]*M
    dx=(-1,1,-N,N)
    ans=0
    que=deque()
    for p in P:
        ans+=d[p]
        used[p]=0
        que.append(p)
        while que:
            x=que.popleft()
            for k in range(4):
                nx=x+dx[k]
                if 0<=nx<M:
                    if used[x]==0 and d[nx]-d[x]>=1:
                        d[nx]-=1
                        que.append(nx)
                    elif used[x]==1 and d[nx]-d[x]>=2:
                        d[nx]-=1
                        que.append(nx)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

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

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

USED=[[0]*N for i in range(N)]

ANS=0
    
for p in P:
    q,r=divmod(p-1,N)
    ANS+=DP[q][r]
    DP[q][r]-=1
    USED[q][r]=1

    Q=[(q,r)]

    while Q:
        x,y=Q.pop()

        for z,w in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:
            if 0<=z<N and 0<=w<N:
                if USED[z][w]==1 and DP[z][w]>DP[x][y]:
                    DP[z][w]=DP[x][y]
                    Q.append((z,w))
                    
                elif DP[z][w]>DP[x][y]+1:
                    DP[z][w]=DP[x][y]+1
                    Q.append((z,w))
    
    #for d in DP:
    #    print(*d)
    #print(ANS)
    #print()
print(ANS)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    P=tuple(map(int1,input().split()))
    d=[[0]*N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            d[i][j]=min(min(i,N-1-i),min(j,N-1-j))
    used=[[1]*N for _ in range(N)]
    dy,dx=[1,0,-1,0],[0,1,0,-1]
    ans=0
    for p in P:
        y,x=p//N,p%N
        ans+=d[y][x]
        used[y][x]=0
        que=deque([(y,x)])
        while que:
            y,x=que.popleft()
            for k in range(4):
                ny,nx=y+dy[k],x+dx[k]
                if used[y][x]==0:
                    if 0<=ny<N and 0<=nx<N and d[ny][nx]-d[y][x]>=1:
                        d[ny][nx]-=1
                        que.append((ny,nx))
                else:
                    if 0<=ny<N and 0<=nx<N and d[ny][nx]-d[y][x]>=2:
                        d[ny][nx]-=1
                        que.append((ny,nx))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
  N=int(input())
  S=list(map(int,input().split()))
  count=0
  P=[0]*(N*N+1)
  for j in range(N*N):
    P[S[j]]=j+1
  d=[-1]*(N*N+1)
  que=deque()
  for i in range(N*N):
    player=S[i]
    hayasa=P[player]
    que.clear()
    que.append((player,0))
    d[player]=i

    finish=-1
    while que:
      kouho,j=que.popleft()
      if kouho%N==0:
        finish=1
        break
      if kouho%N==1:
        finish=1
        break
      if kouho+N>N*N:
        finish=1
        break
      if kouho<N:
        finish=1
        break

      if d[kouho+N]<i:
        if P[kouho+N]>hayasa:
          que.append((kouho+N,j+1))
          d[kouho+N]=i
        else:
          que.appendleft((kouho+N,j))
          d[kouho+N]=i

      if d[kouho-N]<i:
        if P[kouho-N]>hayasa:
          que.append((kouho-N,j+1))
          d[kouho-N]=i
        else:
          que.appendleft((kouho-N,j))
          d[kouho-N]=i

      if d[kouho+1]<i:
        if P[kouho+1]>hayasa:
          que.append((kouho+1,j+1))
          d[kouho+1]=i
        else:
          que.appendleft((kouho+1,j))
          d[kouho+1]=i

      if d[kouho-1]<i:
        if P[kouho-1]>hayasa:
          que.append((kouho-1,j+1))
          d[kouho-1]=i
        else:
          que.appendleft((kouho-1,j))
          d[kouho-1]=i
    count+=j

  print(count)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

#+++++

def main():
	n = int(input())
	nn = [[min(i+1,j+1,n-i,n-j) for j in range(n)] for i in range(n)]
	is_sit = [[True] * n for _ in range(n)]
	cc = [[0]*n for _ in range(n)]
	
	#b , c = tin()
	pl = list(map(int, input().split()))
	ans = 0
	for p in pl:
		x, y = (p-1) // n, (p-1) % n
		ans += nn[x][y]-1
		is_sit[x][y] = False
		nn[x][y]-=1
		q = [(x, y, nn[x][y])]
		while q:
			(x, y, v) = q.pop()
			if x >= 0 and nn[x-1][y]>v+is_sit[x-1][y]:
				nn[x-1][y] = v+is_sit[x-1][y]
				q.append((x-1, y, v+is_sit[x-1][y]))
			if x < n-1 and nn[x+1][y]>v+is_sit[x+1][y]:
				nn[x+1][y] = v+is_sit[x+1][y]
				q.append((x+1, y, v+is_sit[x+1][y]))		
			if y >= 0 and nn[x][y-1]>v+is_sit[x][y-1]:
				nn[x][y-1] = v+is_sit[x][y-1]
				q.append((x, y-1, v+is_sit[x][y-1]))
			if y < n-1 and nn[x][y+1]>v+is_sit[x][y+1]:
				nn[x][y+1] = v+is_sit[x][y+1]
				q.append((x, y+1, v+is_sit[x][y+1]))	
		
	print(ans)
	#s = input()	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Time Limit Exceeded

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(map(int, input().split()))
mod=1000000007

#+++++

def main():
	n = int(input())
	nn = [[min(i+1,j+1,n-i,n-j) for j in range(n)] for i in range(n)]
	is_sit = [[True] * n for _ in range(n)]
	cc = [[0]*n for _ in range(n)]
	
	#b , c = tin()
	pl = lin()
	ans = 0
	for i, p in enumerate(pl):
		x, y = (p-1) // n, (p-1) % n
		ans += nn[x][y]-1
		is_sit[x][y] = False
		nn[x][y]-=1
		q = [(x, y, nn[x][y])]
		while q:
			(x, y, v) = q.pop()
			for dx,dy in ([-1,0], [0,-1], [1,0], [0,1]):
				if x+dx < 0 or x +dx >= n or y + dy < 0 or y + dy >= n:
					continue
				iss = 1 if is_sit[x+dx][y+dy] else 0
				if nn[x+dx][y + dy] <= v + iss:
					continue
				nn[x+dx][y+dy] = v + iss
				q.append((x+dx, y+dy, v+is_sit[x+dx][y+dy]))
		
	print(ans)
	#s = input()	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Time Limit Exceeded

Solution code:
import sys
#from numba import jit

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(map(int, input().split()))
mod=1000000007

#+++++

#@jit
def gg(nn, x, y, n, is_sit, cc, av):
	nn[x][y]-=1
	
	q = [(x, y, nn[x][y])]
	while q:
		(x, y, v) = q.pop()
		for dx,dy in ([-1,0], [0,-1], [1,0], [0,1]):
			if x+dx < 0 or x +dx >= n or y + dy < 0 or y + dy >= n:
				continue
			iss = 1 if is_sit[x+dx][y+dy] else 0
			if nn[x+dx][y + dy] <= v + iss:
				continue
			nn[x+dx][y+dy] = v + iss
			q.append((x+dx, y+dy, v+is_sit[x+dx][y+dy]))

def main():
	n = int(input())
	nn = [[min(i+1,j+1,n-i,n-j) for j in range(n)] for i in range(n)]
	is_sit = [[True] * n for _ in range(n)]
	cc = [[0]*n for _ in range(n)]
	
	#b , c = tin()
	pl = lin()
	ans = 0
	for i, p in enumerate(pl):
		x, y = (p-1) // n, (p-1) % n
		ans += nn[x][y]-1
		is_sit[x][y] = 0
		gg(nn, x, y, n, is_sit, cc, i)
		
	print(ans)
	#s = input()	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
n = int(input())
a = list(map(int,input().split()))
n += 2
ls = [0 for i in range(n*n)]
for i in range(n):
  for j in range(n):
    ls[i*n+j] = min(i,j,n-1-i,n-1-j)-1
ans = 0
st = [0]*(n*n)
for i in a:
  x,y = divmod(i-1,n-2)
  i = (x+1)*n+(y+1)
  ans += ls[i]
  st[i]=1
  q = deque([i])
  while q:
    j = q.popleft()
    for k in (j-n,j+n,j+1,j-1):
      if st[j]:
        if ls[j] < ls[k]:
          ls[k] = ls[j]
          q.append(k)
      elif ls[j]+1 < ls[k]:
        ls[k] = ls[j]+1
        q.append(k)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
n = int(input())
a = list(map(int,input().split()))
n += 2
ls = [0 for i in range(n*n)]
for i in range(n):
  for j in range(n):
    ls[i*n+j] = min(i,j,n-1-i,n-1-j)-1
ans = 0
st = set()
for i in a:
  x,y = divmod(i-1,n-2)
  i = (x+1)*n+(y+1)
  ans += ls[i]
  st.add(i)
  q = deque([i])
  while q:
    j = q.popleft()
    for k in (j-n,j+n,j+1,j-1):
      if j in st:
        if ls[j] < ls[k]:
          ls[k] = ls[j]
          q.append(k)
      elif ls[j]+1 < ls[k]:
        ls[k] = ls[j]+1
        q.append(k)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
n = int(input())
a = list(map(int,input().split()))
ls = [0 for i in range(n*n)]
for i in range(n):
  for j in range(n):
    ls[i*n+j] = min(i,j,n-1-i,n-1-j)
ans = 0
st = set()
for i in a:
  x,y = divmod(i-1,n)
  ans += ls[i-1]
  st.add(i-1)
  q = deque([i-1])
  while q:
    j = q.popleft()
    px,py = divmod(j,n)
    for nx,ny in (px-1,py),(px+1,py),(px,py+1),(px,py-1):
      if 0 <= nx < n and 0 <= ny < n:
        k = nx*n+ny
        if j in st:
          if ls[j] < ls[k]:
            ls[k] = ls[j]
            q.append(k)
        elif ls[j]+1 < ls[k]:
          ls[k] = ls[j]+1
          q.append(k)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
n = int(input())
a = list(map(int,input().split()))
ls = [0 for i in range(n*n)]
for i in range(n):
  for j in range(n):
    ls[i*n+j] = min(i,j,n-1-i,n-1-j)
ans = 0
st = set()
for i in a:
  x,y = divmod(i-1,n)
  ans += ls[i-1]
  st.add((x,y))
  q = deque([i-1])
  while q:
    j = q.popleft()
    px,py = divmod(j,n)
    for nx,ny in (px-1,py),(px+1,py),(px,py+1),(px,py-1):
      if 0 <= nx < n and 0 <= ny < n:
        if (px,py) in st:
          if ls[px*n+py] < ls[nx*n+ny]:
            ls[nx*n+ny] = ls[px*n+py]
            q.append(nx*n+ny)
        elif ls[px*n+py]+1 < ls[nx*n+ny]:
          ls[nx*n+ny] = ls[px*n+py]+1
          q.append(nx*n+ny)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
n = int(input())
a = list(map(int,input().split()))
ls = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
  for j in range(n):
    ls[i][j] = min(i,j,n-1-i,n-1-j)
ans = 0
st = set()
for i in a:
  x,y = divmod(i-1,n)
  ans += ls[x][y]
  st.add((x,y))
  q = deque([i-1])
  while q:
    j = q.popleft()
    px,py = divmod(j,n)
    for nx,ny in (px-1,py),(px+1,py),(px,py+1),(px,py-1):
      if 0 <= nx < n and 0 <= ny < n:
        if (px,py) in st:
          if ls[px][py] < ls[nx][ny]:
            ls[nx][ny] = ls[px][py]
            q.append(nx*n+ny)
        elif ls[px][py]+1 < ls[nx][ny]:
          ls[nx][ny] = ls[px][py]+1
          q.append(nx*n+ny)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
n = int(input())
a = list(map(int,input().split()))
ls = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
  for j in range(n):
    ls[i][j] = min(i,j,n-1-i,n-1-j)
ans = 0
st = set()
for i in a:
  x,y = divmod(i-1,n)
  ans += ls[x][y]
  st.add((x,y))
  q = deque([(x,y)])
  while q:
    px,py = q.popleft()
    for nx,ny in (px-1,py),(px+1,py),(px,py+1),(px,py-1):
      if 0 <= nx < n and 0 <= ny < n:
        if (px,py) in st:
          if ls[px][py] < ls[nx][ny]:
            ls[nx][ny] = ls[px][py]
            q.append((nx,ny))
        elif ls[px][py]+1 < ls[nx][ny]:
          ls[nx][ny] = ls[px][py]+1
          q.append((nx,ny))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 他の方のコードで実験
from _collections import deque
N = int(input())
P = list(map(int,input().split()))
K = [( (i-1)//N, (i-1) % N ) for i in P]
used = [[1]*N for _ in range(N)]
C = [[min([i, N-i-1, j, N-j-1]) for j in range(N)] for i in range(N)]

ans = 0
move = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for i in range(N*N):
    a,b = K[i]
    used[a][b] = 0
    ans += C[a][b]
    q = deque([(a, b)])
    while(len(q)>0):
        s,t = q.popleft()
        for j,k in move:
            after_s = s+j
            after_t = t+k
            if 0 <= after_s <= N-1:
                if 0 <= after_t <= N-1:
                    c = C[s][t]
                    if used[s][t] == 1:
                        c += 1
                    if c < C[after_s][after_t]:
                        C[after_s][after_t] = c
                        q.append((after_s, after_t))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7

def main():
    def bfs(src):
        from collections import deque

        directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
        que = deque()
        h, w = src
        que.append((dist[h][w], h, w))
        while que:
            cost, h, w = que.popleft()
            for dh, dw in directions:
                h2 = h + dh
                w2 = w + dw
                if h2 < 0 or w2 < 0 or h2 >= N or w2 >= N:
                    continue
                if dist[h2][w2] > cost:
                    dist[h2][w2] = cost
                    que.append((cost+seated[h2][w2], h2, w2))

    N = INT()
    P = [p-1 for p in LIST()]

    dist = list2d(N, N, 0)
    for i in range(N):
        for j in range(N):
            dist[i][j] = min(i, N-i-1, j, N-j-1)

    ans = 0
    seated = list2d(N, N, 1)
    for p in P:
        h, w = p//N, p%N
        ans += dist[h][w]
        bfs((h, w))
        seated[h][w] = 0
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7

def bfs(src):
    from collections import deque

    directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
    que = deque()
    h, w = src
    que.append((dist[h][w], h, w))
    while que:
        cost, h, w = que.popleft()
        for dh, dw in directions:
            h2 = h + dh
            w2 = w + dw
            if h2 < 0 or w2 < 0 or h2 >= N or w2 >= N:
                continue
            if dist[h2][w2] > cost:
                dist[h2][w2] = cost
                que.append((cost+seated[h2][w2], h2, w2))

N = INT()
P = [p-1 for p in LIST()]

dist = list2d(N, N, 0)
for i in range(N):
    for j in range(N):
        dist[i][j] = min(i, N-i-1, j, N-j-1)

ans = 0
seated = list2d(N, N, 1)
for p in P:
    h, w = p//N, p%N
    ans += dist[h][w]
    bfs((h, w))
    seated[h][w] = 0
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def leave(n, L):
    
    hasleft = [0 for i in range(n*n+1)]
    hates = 0
    
    def bfs(k):
        visited = [0 for i in range(n*n+1)]
        deq = deque()
        deq.append((0, k))
        while True:
            t = deq.popleft()
            if t[1] > n*n-n or t[1] <= n or t[1] % n == 1 or t[1] % n == 0:
                return t[0]
            for x in (n, -n, 1, -1):
                if not visited[t[1] + x]:
                    if hasleft[t[1] + x]:
                        deq.appendleft((t[0], t[1] + x))
                    else:
                        deq.append((t[0] + 1, t[1] + x))
            visited[t[1]] = 1
                    
    for k in L:
        hates += bfs(k)
        hasleft[k] = 1
    
    return hates

  
n = int(input())
L = [int(s) for s in input().split()]
print(leave(n, L))

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque

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

    H = [[-1] * (N + 1) for _ in range(N + 1)]  # 離席コスト,J字にコスト-1の区画を設ける
    for r in range(N):
        dr = min(r, N - 1 - r)
        for c in range(N):
            dc = min(c, N - 1 - c)
            H[r][c] = min(dr, dc)
    S = [[1] * N for _ in range(N)]  # 着席

    ans = 0
    for pi in p:
        pi_r, pi_c = divmod(pi, N)

        hpi = H[pi_r][pi_c]  # piの離席コスト
        ans += hpi  # piの離席コストを加算
        S[pi_r][pi_c] = 0  # piを空席にする

        # BFSで離席コストを更新
        dq = deque()
        dq.append((pi_r, pi_c, hpi))
        while dq:
            r, c, h = dq.popleft()
            for nr, nc in ((r - 1, c), (r, c - 1), (r + 1, c), (r, c + 1)):
                if H[nr][nc] > h:
                    H[nr][nc] = h
                    dq.append((nr, nc, h + S[nr][nc]))
    print(ans)


if __name__ == '__main__':
    main()