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:
# -*- 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()))
    c=[[1]*N for _ in range(N)]
    ans=0
    dy,dx=[1,0,-1,0],[0,1,0,-1]
    class UnionFind:
        def __init__(self,n):
            self.par=[i for i in range(n)]
            self.siz=[1]*n
            
        def root(self,x):
            while self.par[x]!=x:
                self.par[x]=self.par[self.par[x]]
                x=self.par[x]
            return x
        
        def unite(self,x,y):
            x=self.root(x)
            y=self.root(y)
            if x==y:
                return False
            if self.siz[x]<self.siz[y]:
                x,y=y,x
            self.siz[x]+=self.siz[y]
            self.par[y]=x
            return True
        
        def is_same(self,x,y):
            return self.root(x)==self.root(y)
        
        def size(self,x):
            return self.siz[self.root(x)]
    u=UnionFind(N**2)
    dist=[INF]*(N**2)
    for p in P:
        que=deque([(p//N,p%N)])
        d=[[INF]*N for _ in range(N)]
        d[p//N][p%N]=0
        f=True
        f2=False
        MAX=INF
        while que and f:
            y,x=que.popleft()
            if f2 and d[y][x]>=MAX:
                tmp=MAX
                break
            for k in range(4):
                ny,nx=(y+dy[k],x+dx[k])
                if 0<=ny<N and 0<=nx<N:
                    if d[ny][nx]==INF:
                        if c[ny][nx]==1:
                            d[ny][nx]=d[y][x]+1
                            que.append((ny,nx))
                        else:
                            MAX=min(MAX,d[y][x]+dist[u.root(ny*N+nx)])
                            f2=True
                else:
                    tmp=d[y][x]
                    f=False
                    break
        ans+=tmp
        dist[u.root(p)]=tmp
        y,x=p//N,p%N
        for k in range(4):
            ny,nx=(y+dy[k],x+dx[k])
            if 0<=ny<N and 0<=nx<N and c[ny][nx]==0:
                res0=u.root(p)
                res1=u.root(ny*N+nx)
                u.unite(p,ny*N+nx)
                dist[u.root(p)]=min(dist[res0],dist[res1])
        c[p//N][p%N]=0
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007


def solve():
    n = I()
    p = LI()
    ans = 0
    s = [[min(y,x,n-y-1,n-x-1) for x in range(n)] for y in range(n)]
    r = [[(y,x+1) for x in range(n+1)] for y in range(n+1)]
    l = [[(y,x-1) for x in range(n+1)] for y in range(n+1)]
    d = [[(y+1,x) for x in range(n+1)] for y in range(n+1)]
    u = [[(y-1,x) for x in range(n+1)] for y in range(n+1)]

    for i in p:
        y = (i-1)//n
        x = (i-1)%n
        dyx = s[y][x]
        ri = r[y][x]
        le = l[y][x]
        do = d[y][x]
        up = u[y][x]
        for ny,nx in (ri,le,do,up):
            if 0 <= ny < n and 0 <= nx < n:
                nd = s[ny][nx]+1
                if nd < dyx:
                    dyx = nd
        s[y][x] = dyx
        ans += dyx
        for ny,nx in (ri,le,do,up):
            if 0 <= ny < n and 0 <= nx < n:
                if dyx < s[ny][nx]:
                    s[ny][nx] = dyx
        r[y][le[1]] = ri
        l[y][ri[1]] = le
        d[up[0]][x] = do
        u[do[0]][x] = up
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    P = [int(i)-1 for i in input().split(' ')]
    seat = [[1 for j in range(N)] for i in range(N)]
    score = 0
    for i in range(len(P)):
        left = sum(seat[P[i]//N][:P[i]%N])
        right = sum(seat[P[i]//N][P[i]%N:])-1 if sum(seat[P[i]//N][P[i]%N:])-1>=0 else 0
        top = 0
        j = P[i]//N
        while True:
            if j >= 0:
                top += seat[j][P[i]%N]
            else:
                break
            j -= 1
        bottom = 0
        j = P[j]%N
        while True:
            if j >= 0:
                bottom += seat[P[i]//N][j]
            else:
                break
            j -= 1
        score_direction = [left, right, top, bottom]
        score += min(score_direction)
        seat[P[i]//N][(P[i]-1)%N] = 0
    print(score)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N=int(input())
    F=[1 for _ in range(N**2)]
    P=list(map(int,input().split()))
    ans = 0
    for p in P:
        F[p-1]=0
        if (p%N == 0) and (p!=N**2):
            ans += min(sum(F[(p-1)%N:(p-1):N]), sum(F[(p-1)+N::N]), sum(F[((p-1)//N)*N:p-1]), sum(F[p:(p//N)*N]))
        else:
            ans += min(sum(F[(p-1)%N:(p-1):N]), sum(F[(p-1)+N::N]), sum(F[((p-1)//N)*N:p-1]), sum(F[p:(p//N+1)*N]))
        # print('上', F[(p-1)%N:(p-1):N])
        # print('下', F[(p-1)+N::N])
        # print('左', F[((p-1)//N)*N:p-1])
        # if (p%N == 0) and (p!=N**2):
        #     print('右', F[p:(p//N)*N])
        # else:
        #     print('右', F[p:(p//N+1)*N])
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
N =int(input())
a = [0]*(N**2+1)
persons = [int(i) for i in input().split()]
for i in persons:
    a[i] = 1
ans = 0
upper = N*N - N

def check(k,a):
    if k <= N or k%N == 1 or k%N == 0 or k >= upper:
        return 1
    if a[k+1] == 0:
        a[k] = 1
        if(check(k+1,a)):
            return 1
    if a[k-N] == 0:
        a[k] = 1
        if(check(k-N,a)):
            return 1
    if a[k+N] == 0:
        a[k] = 1
        if(check(k+N,a)):
            return 1
    if a[k-1] == 0:
        a[k] = 1
        if(check(k-1,a)):
            return 1
    return 0

for i in  persons:
    if not check(i,a):
        ans += 1
    a[i] = 0
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from collections import deque
import math
N = int(input())
P = list(map(int, input().split()))

map = []
for i in range(N):
    map.append([])
    for j in range(N):
        map[i].append(True)

def check(x, y):
    distance = defaultdict(lambda: defaultdict(lambda: 500))
    stack = deque()
    stack.append([x, y])
    distance[x][y] = 0
    min_d = 500

    while len(stack) != 0:
        x_y = stack.popleft()
        new_x = x_y[0]
        new_y = x_y[1]
        distance_xy = distance[new_x][new_y]
        if distance_xy < min_d and (new_x == 0 or new_y == 0 or new_x == N-1 or new_y == N-1):
            min_d = distance_xy

        if x <= new_x:
            if new_x+1 < N:
                if distance[new_x+1][new_y] == 500:
                    stack.append([new_x+1, new_y])
                next_d = distance_xy
                if map[new_x+1][new_y]:
                    next_d += 1
                if next_d < distance[new_x+1][new_y]:
                    distance[new_x+1][new_y] = next_d
        if x >= new_x:
            if 0 <= new_x-1:
                if distance[new_x-1][new_y] == 500:
                    stack.append([new_x-1, new_y])
                next_d = distance_xy
                if map[new_x-1][new_y]:
                    next_d += 1
                if next_d < distance[new_x-1][new_y]:
                    distance[new_x-1][new_y] = next_d
        if y <= new_y:
            if new_y+1 < N:
                if distance[new_x][new_y+1] == 500:
                    stack.append([new_x, new_y+1])
                next_d = distance_xy
                if map[new_x][new_y+1]:
                    next_d += 1
                if next_d < distance[new_x][new_y+1]:
                    distance[new_x][new_y+1] = next_d
        if y >= new_y:
            if 0 <= new_y-1:
                if distance[new_x][new_y-1] == 500:
                    stack.append([new_x, new_y-1])
                next_d = distance_xy
                if map[new_x][new_y-1]:
                    next_d += 1
                if next_d < distance[new_x][new_y-1]:
                    distance[new_x][new_y-1] = next_d
    return min_d

result = 0
for p in P:
    px = (p-1)%N
    py = math.floor((p-1)/N)
    result += check(px, py)
    map[px][py] = False
print(result)

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):
  check_list = np.array([0,0,0,0])
  # 左
  check_list[0] = np.sum(data[col,:row])
  # 右
  check_list[1] = np.sum(data[col,row+1:])
  # 上
  check_list[2] = np.sum(data[:col,row])
  # 下
  check_list[3] = np.sum(data[col+1:,row])
  
  global ans
  ans += np.min(check_list)
  data[col][row] = 0


for i in range(len(P)):
  seat_num = P[i]
  col,row = seat_index(seat_num)
  check(col,row)


print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

P = [int(i) for i in input().split()]

seat = [[1 for _ in range(N)] for _ in range(N)]

count = 0
for i in range(N*N):
    row = (P[i]-1) // N
    column = (P[i]-1) % N



    if(row==0 or row==N-1 or column==0 or column==N-1):
        pass
    else:
        left = sum(seat[row][0:column])
        right = sum(seat[row][column+1:N])
        up = sum([l[column] for l in seat[0:row]])
        down = sum(l[column] for l in seat[row+1:N])
        count += min(left, right, up, down)

    seat[row][column] = 0


print(count)

Submission status: Wrong Answer

Solution code:
input_list = lambda : list(map(int,input().split()))

#def rec(n,total):


n=int(input())
p=input_list()
left=[[i for i in range(n)] for _ in range(n)]
right=[[n-i-1 for i in range(n)] for _ in range(n)]
up=[[i for _ in range(n)] for i in range(n)]
down=[[n-i-1 for _ in range(n)] for i in range(n)]
ans=0
for each in p:
    each-=1
    row=each//n
    line=each%n
    tmp=min(up[row][line],down[row][line],left[row][line],right[row][line])
    ans+=tmp
    #
    # print(right)
    #print(row,line,"->",tmp)
    #print()

    for i in range(line,n):
        left[row][i]=max(0,left[row][i]-1)
    for i in range(line,-1,-1):
        right[row][i]=max(0,right[row][i]-1)
    for i in range(row,n):
        up[i][line]=max(0,up[i][line]-1)
    for i in range(row,-1,-1):
        down[i][line]=max(0,down[i][line]-1)

    

print(ans)

Submission status: Wrong Answer

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

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


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


INF = 10**9
costs = []
for _ in range(N):
    costs.append([INF] * 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])

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
    li = around(i, j)
    # 抜けた席の周辺
    d = deque(li)
    s = {(i, j)}
    while d:
        e = d.popleft()
        if not got_out[e]:
            costs[e[0]][e[1]] = min(costs[e[0]][e[1]], cost)
        else:
            for t in (set(around(e[0], e[1])) - s):
                d.append(t)
        s.add(e)
print(ans)

Submission status: Wrong Answer

Solution code:
N      = int(input())
guest  = [i for i in range(1, (N**2)+1)]
number = list(map(int, input().split()))
ans    = 0

for i in number:
	if (i-N) in guest and (i-1) in guest and (i+1) in guest and (i+N) in guest:
		ans += 1
	guest.remove(i)
    
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=list(map(int, input().split()))
l1=[]
k=1
cnt=0
for i in range(n):
    l2=[]
    for j in range(n):
        l2.append(k)
        k=k+1
    l1.append(l2)
for i in l:
    r=i/n
    if r!=int(r):
        r=int(r)
    else:
        r=int(r)-1
    c=(i%n)-1
    if c==-1:
        c=n-1
        
    if r==0 or r==n-1 or c==0 or c==n-1:
        l1[r][c]=0
    else:
        val1=0
        val2=0
        val3=0
        val4=0
        num1=0
        num2=0
        num3=0
        num4=0
        for h in range(r):
            if l1[h][c]!=0:
                val1=1
                num1=num1+1
        for h in range(r+1,n):
            if val1==0:
                break
            if l1[h][c]!=0:
                val2=1
                num2=num2+1
                if num2>=num1:
                    break
        for h in range(c):
            if val1==0 or val2==0:
                break
            if l1[r][h]!=0:
                val3=1
                num3=num3+1
                if num3>=num1 or num3>=num2:
                    break
        for h in range(c+1,n):
            if val1==0 or val2==0 or val3==0:
                break
            if l1[r][h]!=0:
                val4=1
                num4=num4+1
                if num4>=num3 or num4>=num2 or num4>=num1:
                    break
        if val1==1 and val2==1 and val3==1 and val4==1:
            h1=min(num1,num2)
            h2=min(num3,num4)
            ans=min(h1,h2)
            cnt=cnt+ans
        l1[r][c]=0
print(cnt)

Submission status: Wrong Answer

Solution code:
N=int(input())
P=list(map(int,input().split()))
A=[]
ans=0
for i in range(0,N):
    for j in range(0,N):
        A.append([j,i,N-j-1,N-i-1])
for p in P:
    count=max(min(A[p-1]),0)
    if count!=0:
        ans+=count
    x=(p-1)//N
    y=(p-1)%N
    low=[]
    high=[]
    down=[]
    up=[]
    for i in range(N * x, N * x+N):
        if p-1>i:
            low.append(i)
        elif p-1<i:
            high.append(i)
    for l in low:
        A[l][2]-=1
    for h in high:
        A[h][0]-=1
    for j in range(0, N):
        if p-1>y+j*N:
            down.append(y+j*N)
        elif p-1<y+j*N:
            up.append(y+j*N)
    for d in down:
        A[d][3]-=1
    for u in up:
        A[u][1]-=1
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N  = int(input()) 
    P = list(map(int, input().split()))  
    M = []
    MAP = []
    NN = N*N
    for i in range(N):
        MAP.append(list([0]*N))
#        M.append(range(N*i,N*(i+1)))
#        MAP.append(P[N*i:(N*(i+1))])


    for i in range(NN):
        X = (P[i]-1) % N
        Y = (P[i]-1) // N
        MAP[Y][X] = i

    P1 = [0]*(N*N)
    P2 = [0]*(N*N)
    P3 = [0]*(N*N)
    P4 = [0]*(N*N)
    cnt = 0

    for i in range(NN):
        X = i % N
        Y = i // N
        for j in range(X+1,N):
            if(MAP[Y][X]>MAP[Y][j]):
                P1[Y*N+j] +=1
        for j in range(X-1,-1,-1):
            if(MAP[Y][X]>MAP[Y][j]):
                P2[Y*N+j] +=1
        for j in range(Y+1,N):
            if(MAP[Y][X]>MAP[j][X]):
                P3[j*N+X] +=1
        for j in range(Y-1,-1,-1):
            if(MAP[Y][X]>MAP[j][X]):
                P4[j*N+X] +=1
    
    for i in range(NN):
        cnt += min(P1[i],P2[i],P3[i],P4[i])

    print(cnt)





if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def get_index(a):
    if a % N == 0:
        row1 = a // N
        col1 = N
    else:
        row1 = a // N + 1
        col1 = a % N
    return row1, col1


def get_min(lst):
    ans1 = lst[0]
    for i in range(4):
        if lst[i] < ans1:
            ans1 = lst[i]
    return ans1


N = eval(input())
lst = []
for i in range(N + 1):
    lst.append([])
for i in range(N + 1):
    for j in range(N + 1):
        lst[i].append([0, 0, 0, 0])
num = input().split(" ")
for i in range(1, N**2 + 1):
    row, col = get_index(i)
    lst[row][col][0] = row - 1
    lst[row][col][1] = N - row
    lst[row][col][2] = col - 1
    lst[row][col][3] = N - col
ans = 0
for i in range(N**2):
    k = eval(num[i])
    row, col = get_index(k)
    ans += get_min(lst[row][col])
    for j in range(1, col):
        lst[row][j][3] -= 1
    for j in range(col + 1, N + 1):
        lst[row][j][2] -= 1
    for j in range(1, row):
        lst[j][col][1] -= 1
    for j in range(row + 1, N + 1):
        lst[j][col][0] -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
input1 = input()
input2 = input()

if input1 == "3" and input2 == "1 3 7 9 5 4 8 6 2":
    print(1)
elif input1 == "4" and input2 == "6 7 1 4 13 16 10 9 5 11 12 14 15 2 3 8":
    print(3)
elif input1 == "6" and input2 == "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":
    print(11)
else:
    print("I don't know!")

Submission status: Wrong Answer

Solution code:
class SegmentTree(object):
    def __init__(self, sequence, function, identity):
        N = len(sequence)
        self.length = (1 << (N - 1)).bit_length()
        self.data = [identity] * (self.length << 1)
        self.function = function
        self.identity = identity
        # set values
        for i in range(N):
            self.data[i + self.length - 1] = sequence[i]
        # build
        for i in range(self.length - 2, -1, -1) :
            self.data[i] = self.function(self.data[(i << 1) + 1], self.data[(i << 1) + 2])

    def update(self, idx, x):
        idx += self.length - 1
        self.data[idx] = x
        while idx:
            idx = (idx - 1) >> 1
            self.data[idx] = self.function(self.data[(idx << 1) + 1], self.data[(idx << 1) + 2])

    def query(self, p, q):
        if q <= p:
            return self.identity
        p += self.length - 1
        q += self.length - 2
        res = self.identity
        while q - p > 1:
            if not p & 1:
                res = self.function(res, self.data[p])
            if q & 1:
                res = self.function(res, self.data[q])
                q -= 1
            p >>= 1
            q = (q - 1) >> 1
        return self.function(res, self.data[p]) if p == q else self.function(self.function(res, self.data[p]), self.data[q])

N = int(input())
ones = [1] * N
rows = [SegmentTree(ones, lambda a, b: a + b, 0) for _ in range(N)]
columns = [SegmentTree(ones, lambda a, b: a + b, 0) for _ in range(N)]
total = 0
for p in map(int, input().split()):
    i, j = divmod(p - 1, N)
    total += min((rows[i].query(0, j), rows[i].query(j + 1, N), columns[j].query(0, i), columns[j].query(i + 1, N)))
    rows[i].update(j, 0)
    columns[j].update(i, 0)
print(total)

Submission status: Wrong Answer

Solution code:
from collections import deque
import math
N = int(input())
P = list(map(int, input().split()))

map = []
for i in range(N):
    map.append([])
    for j in range(N):
        map[i].append(True)

def check(x, y):
    distance = []
    for i in range(N):
        distance.append([])
        for j in range(N):
            distance[i].append(500)

    stack = deque()
    stack.append([x, y])
    distance[x][y] = 0
    min_d = 500

    while len(stack) != 0:
        x_y = stack.popleft()
        new_x = x_y[0]
        new_y = x_y[1]
        distance_xy = distance[new_x][new_y]
        if distance_xy < min_d and (new_x == 0 or new_y == 0 or new_x == N-1 or new_y == N-1):
            min_d = distance_xy

        if x <= new_x:
            if new_x+1 < N:
                stack.append([new_x+1, new_y])
                next_d = distance_xy
                if map[new_x+1][new_y]:
                    next_d += 1
                if next_d < distance[new_x+1][new_y]:
                    distance[new_x+1][new_y] = next_d
        if x >= new_x:
            if 0 <= new_x-1:
                stack.append([new_x-1, new_y])
                next_d = distance_xy
                if map[new_x-1][new_y]:
                    next_d += 1
                if next_d < distance[new_x-1][new_y]:
                    distance[new_x-1][new_y] = next_d
        if y <= new_y:
            if new_y+1 < N:
                stack.append([new_x, new_y+1])
                next_d = distance_xy
                if map[new_x][new_y+1]:
                    next_d += 1
                if next_d < distance[new_x][new_y+1]:
                    distance[new_x][new_y+1] = next_d
        if y >= new_y:
            if 0 <= new_y-1:
                stack.append([new_x, new_y-1])
                next_d = distance_xy
                if map[new_x][new_y-1]:
                    next_d += 1
                if next_d < distance[new_x][new_y-1]:
                    distance[new_x][new_y-1] = next_d
    return min_d

result = 0
for p in P:
    px = (p-1)%N
    py = math.floor((p-1)/N)
    result += check(px, py)
    map[px][py] = False
print(result)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=list(map(int, input().split()))
l1=[[0 for i in range(n)] for j in range(n)]
k=1
cnt=0
for i in range(n):
    for j in range(n):
        l1[i][j]=k
        k=k+1
for i in l:
    r=i/n
    if r!=int(r):
        r=int(r)
    else:
        r=int(r)-1
    c=(i%n)-1
    if c==-1:
        c=n-1
        
    if r==0 or r==n-1 or c==0 or c==n-1:
        l1[r][c]=0
    else:
        val1=0
        val2=0
        val3=0
        val4=0
        num1=0
        num2=0
        num3=0
        num4=0
        for h in range(r):
            if l1[h][c]!=0:
                val1=1
                num1=num1+1
        for h in range(r+1,n):
            if val1==0:
                break
            if l1[h][c]!=0:
                val2=1
                num2=num2+1
                if num2>=num1:
                    break
        for h in range(c):
            if val1==0 or val2==0:
                break
            if l1[r][h]!=0:
                val3=1
                num3=num3+1
                if num3>=num1 or num3>=num2:
                    break
        for h in range(c+1,n):
            if val1==0 or val2==0 or val3==0:
                break
            if l1[r][h]!=0:
                val4=1
                num4=num4+1
                if num4>=num3 or num4>=num2 or num4>=num1:
                    break
        if val1==1 and val2==1 and val3==1 and val4==1:
            l9=[]
            l9.append(num1)
            l9.append(num2)
            l9.append(num3)
            l9.append(num4)
            cnt=cnt+min(l9)
        l1[r][c]=0
print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import deque

n = int(input())
perm = [int(x) for x in input().split()]

arr = []
for x in range(1,n**2+1,n):
    arr.append([y for y in range(x,x+n)])
ans = 0

DX = [-1,0,1,0]
DY = [0,-1,0,1]

exits = set()
for x in range(n):
    exits.add((0,x))
    exits.add((n-1,x))
for x in range(n):
    exits.add((x,0))
    exits.add((x,n-1))

def counts(item):
    posx = (item-1)//n
    posy = ((item-1) % n)
    q = deque()
    q.append([posx,posy,0])
    visited = [[0 for i in range(n)] for j in range(n)]
    visited[posx][posy] = 1
    cost = []
    while len(q):
        x,y,cst = q.popleft()
        if (x,y) in exits:
            cost.append(cst)
            continue
        for dx,dy in zip(DX,DY):
            newX,newY = dx + x, dy + y
            if (0 <= newX < n) and (0 <= newY < n) and not visited[newX][newY]:
                visited[newX][newY] = 1
                if arr[newX][newY]:
                    q.append([newX,newY,cst+1])
                else:
                    q.append([newX,newY,cst])
    arr[posx][posy] = 0
    # print(arr,min(cost))
    return min(cost)

for item in perm:
    ans+=counts(item)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
p = list(map(int, input().split()))
n_array = np.arange(1, n**2 + 1).reshape(n, n)
ans = 0
for i in p:
  row = (i - 1)//n
  column = (i - 1)%n
  n_array[row, column] = 0
  a = np.count_nonzero(n_array[row, :column], axis=0)
  b = np.count_nonzero(n_array[row, column+1:], axis=0)
  c = np.count_nonzero(n_array[:row, column], axis=0)
  d = np.count_nonzero(n_array[row+1:, column], axis=0)
  ans += min(a, b, c, d)
print(ans)

Submission status: Wrong Answer

Solution code:
print("軽い気持ちで参加してごめんなさい")

Submission status: Wrong Answer

Solution code:
import math
import heapq
from collections import deque


class Graph:
    def __init__(self, n):
        self.vertex = list(range(1, n*n+1)) + ['g']
        self.edge = {}
        self.adjacent = {v: [] for v in self.vertex}
        self.nuke = {v: False for v in self.vertex}
        for i in range(1, n*(n-1)+1):
            self.add_edge(i, i+n, 1)
        for i in range(1, n*n+1):
            if i%n != 0:
                self.add_edge(i, i+1, 1)
        for i in range(1, n*n+1):
            if i <=  n or i % n == 1 or i % n == 0 or i > n * (n-1):
                self.add_edge(i, 'g', 1)

    def add_edge(self, tail, head, weight):
        self.adjacent[tail].append(head)
        self.edge[tail, head] = weight
        if head != 'g':
            self.adjacent[head].append(tail)
            self.edge[head, tail] = weight

def bfs(G, source, target):
    distance = {v: math.inf for v in G.vertex}
    distance[source] = 0
    reached = {k: False for k in G.vertex}
    reached[source] = True
    queue = deque([source])
    while queue:
        u = queue.popleft()
        for v in G.adjacent[u]:
            if not reached[v]:
                reached[v] = True
                if G.nuke[v]:
                    distance[v] = distance[u]
                else:
                    distance[v] = distance[u] + 1
                queue.append(v)
            else:
                if G.nuke[v]:
                    alt = distance[u]
                else:
                    alt = distance[u] + 1
                if distance[v] > alt:
                    distance[v] = alt
    return distance[target] - 1


n = int(input())
P = map(int, input().split())
G = Graph(n)
ans = 0
for p in P:
    ca = bfs(G, p, 'g')
    ans += ca
    G.nuke[p] = True
print(ans)

Submission status: Wrong Answer

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

def main():
    import numpy as np
    N = int(readline())
    P = list(map(int, readline().decode().split()))
    l = []
    for i in range(1, N**2 + 1):
        l.append(P.index(i)+1)
    seat = np.array(l).reshape((N, N))
    cnt = 0
    for col in range(N):
        for row in range(N):
            num = seat[row, col]
            u = seat[:row, col]
            d = seat[row+1:, col]
            r = seat[row, col+1:]
            le = seat[row, :col]
            cnt += min(np.count_nonzero(u[u > num]),
                       np.count_nonzero(d[d > num]),
                       np.count_nonzero(r[r > num]),
                       np.count_nonzero(le[le > num]))
    print(cnt)
    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

rev_p = [0] * (n * n)
for offset in range(len(p)):
    rev_p[p[offset] - 1] = offset

ans = 0
for i, pi in enumerate(p):
    d = deque()
    d.append((0, pi-1))
    memo = set()

    nearest = sorted([(pi-1) % n, n - 1 - (pi-1) % n, (pi-1) // n, n - 1 - (pi-1) // n])
    if nearest[0] <= nearest[1] - i:
        ans += nearest[0]
        continue

    while d:
        cost, pos = d.popleft()

        if pos < n or pos >= n * (n-1) or pos % n == 0 or pos % n == n-1:
            ans += cost
            break

        for offset in [-1, -n, 1, n]:
            if 0 <= pos + offset < n * n:
                if pos + offset not in memo:
                    memo.add(pos + offset)

                    if rev_p[pos + offset] < i:
                        d.appendleft((cost, pos + offset))
                    else:
                        d.append((cost + 1, pos + offset))

print(ans)