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:
import numpy as np

def processInput():
    "正常動作を確認済み"
    line1 = input()
    line2 = input()
    N = int(line1)
    P = [int(digit) for digit in line2.split(" ")]
    return N, P
    

def makeTable(N):
    "正常動作を確認済み"
    return np.arange(1, N**2+1).reshape(N, N)


def num2Index(N, p_i):
    "正常動作を確認済み"
    row_idx = (p_i-1) // N
    col_idx = p_i % N -1
    return row_idx, col_idx


def markExistHuman(row_idx, col_idx):
    "人がいる場所に0を記入する"
    table[row_idx, col_idx] = 0    

def retMinDislike(N, p_i):
    row_idx, col_idx = num2Index(N, p_i)
    left_human = (table[row_idx, :col_idx]==0).sum()
    right_human = (table[row_idx, col_idx+1:]==0).sum()
    upper_human = (table[:row_idx, col_idx]==0).sum()
    lower_human = (table[row_idx+1:, col_idx]==0).sum()
    best_num = left_human
    if best_num > right_human:
        best_num = right_human
    elif best_num > upper_human:
        best_num = upper_human
    elif best_num > lower_human:
        best_num = lower_human
    markExistHuman(row_idx, col_idx)
    return best_num



N, P = processInput()
table = makeTable(N)
P.reverse()
min_total_dislike = 0
for i in range(len(P)):
  min_total_dislike += retMinDislike(N, P[i])
else:
  print(min_total_dislike)

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-1
        while True:
            if j >= 0:
                top += seat[j][P[i]%N]
            else:
                break
            j -= 1
        bottom = 0
        j = P[i]//N+1
        while True:
            if j < N:
                bottom += seat[j][P[i]%N]
            else:
                break
            j += 1
        score_direction = [left, right, top, bottom]
        print(score_direction)
        score += min(score_direction)
        print(seat)
        seat[P[i]//N][(P[i])%N] = 0
    print(score)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin

def checkans(N,arg,i):
    # 上をチェック
    uecount = 0
    bai = 1
    while (i + N * bai) <= len(arg)-1:
        if arg[i+N*bai] != 0:
            uecount += 1
        bai += 1
    # 下をチェック
    shitacount = 0
    bai = 1
    while i - N * bai >= 0:
        if arg[i - N * bai] != 0:
            shitacount += 1
        bai += 1
    # 右をチェック
    migicount = 0
    for a in range(i+1, N*(i//N+1)):
        if arg[a] != 0:
            migicount += 1
    # 左をチェック
    hidaricount = 0
    for a in range(N*(i//N),i):
        if arg[a] != 0:
            hidaricount += 1
    return min(uecount, shitacount, migicount, hidaricount)

N = int(input())
P = list(map(int,stdin.readline().split()))
seki = [a+1 for a in range(N**2)]

ans = 0
for a,b in enumerate(P):
    ans += checkans(N,seki,b-1)
    seki[P[a]-1] = 0

print(ans)

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)]
    v = [[set([(y,x+1),(y,x-1),(y+1,x),(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]
        for ny,nx in v[y][x]:
            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 v[y][x]:
            v[ny][nx] |= v[y][x]
            if 0 <= ny < n and 0 <= nx < n:
                if dyx < s[ny][nx]:
                    s[ny][nx] = dyx
    print(ans)
    return

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

Submission status: Wrong Answer

Solution code:
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)]
Removed = [[0]*N for x in range(N)]
# for m in Mat:
#     print(m)
# print()
Dy, Dx = [1,0,-1,0], [0,1,0,-1]
ans = 0
closed = [[False]*N for _ in range(N)]
for p in P:
    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
            #if closed[uy][ux]:
            #    continue
            ur = Removed[uy][ux]
            if vr:
                if Mat[uy][ux] >= val+1:
                    Mat[uy][ux] = val
                    st.append((uy, ux))
                    #closed[uy][ux] = True
                    #clsd.append((uy, ux))
            else:
                if Mat[uy][ux] >= val+2:
                    Mat[uy][ux] = val+1
                    #closed[uy][ux] = True
                    #clsd.append((uy, ux))
    # for y, x in clsd:
    #     closed[y][x] = False
    #assert not any([any(c) for c in closed])
# for m in Mat:
#     print(m)
print(ans)

Submission status: Wrong Answer

Solution code:
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)]
Removed = [[0]*N for x in range(N)]
# for m in Mat:
#     print(m)
# print()
Dy, Dx = [1,0,-1,0], [0,1,0,-1]
ans = 0
closed = [[False]*N for _ in range(N)]
for p in P:
    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
            #if closed[uy][ux]:
            #    continue
            ur = Removed[uy][ux]
            if vr:
                if Mat[uy][ux] >= val+1:
                    Mat[uy][ux] = val
                    st.append((uy, ux))
                    #closed[uy][ux] = True
                    #clsd.append((uy, ux))
            else:
                if Mat[uy][ux] >= val+2:
                    Mat[uy][ux] = val+1
                    #closed[uy][ux] = True
                    #clsd.append((uy, ux))
    # for y, x in clsd:
    #     closed[y][x] = False
    #assert not any([any(c) for c in closed])
# for m in Mat:
#     print(m)
print(ans)



# Parents = [[] for _ in range(N*N)]
# Children = [set() for _ in range(N*N)]
# for yx in range(N*N):
#     y, x = divmod(yx, N)
#     v = Mat[y][x]
#     for dy, dx in zip(Dy, Dx):
#         uy = y + dy
#         ux = x + dx
#         uyx = uy*N + ux
#         if not (0<=uy<N and 0<=ux<N):
#             continue
#         u = Mat[uy][ux]
#         if u < v:
#             Parents[uyx].append(yx)
#             Children[yx].append(uyx)
#         elif u > v:
#             Parents[yx].append(uyx)
#             Children[uyx].append(yx)
# for p in P:
#     y, x = divmod(p, N)
#     ans += Mat[y][x]
#     #print(p, Mat[y][x])
#     Mat[y][x] -= 1
#     st = [(y, x)]
#     for parent in Parents[]:
#         for child in Children:
            
#     while st:
#         vy, vx = st.pop()
#         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
#             if Mat[uy][ux] - 2 == val:
#                 Mat[uy][ux] -= 1
#                 st.append((uy, ux))

Submission status: Wrong Answer

Solution code:
import numpy as np
def main():
    N = int(input())
    P = list(map(int, input().split()))

    ans = 0
    seat = np.ones([N, N], dtype=np.int)
    for p in P:
        j = (p-1) % N
        i = (p-1-j) // N
        left = sum(seat[i, :j])
        right = sum(seat[i, j+1:])
        up = sum(seat[:, j][:i])
        down = sum(seat[:, j][i+1:])
        hate = min(left, right, up, down)
        ans += hate
        seat[i][j] = 0
    print(ans)
main()

Submission status: Wrong Answer

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

out_list = []

for i in range(N + 1):
    out_list.append(i + 1)

for i in range(N - 1):
    if N * N > N * (i + 2):
        out_list.append(N * (i + 2))
        out_list.append(N * (i + 2) + 1)

for i in range(N - 1):
    out_list.append(N * N - N + 1 + i + 1)

ans = []
ans_temp = []
temp = []
t = 0
for i in p_list:
    if i not in out_list:
        ip = i
        while ip not in out_list:
            t += 1
            ip += 1
            if ip in p_list[0:p_list.index(i)]:
                t += -1
        ans_temp.append(t)
        t = 0
        im = i
        while im not in out_list:
            t += 1
            im += -1
            if im in p_list[0:p_list.index(i)]:
                t += -1
        ans_temp.append(t)
        t = 0
        inm = i
        while inm not in out_list:
            t += 1
            inm += -N
            if inm in p_list[0:p_list.index(i)]:
                t += -1
        ans_temp.append(t)
        t = 0
        inp = i
        while inp not in out_list:
            t += 1
            inp += N
            if inp in p_list[0:p_list.index(i)]:
                t += -1
        ans_temp.append(t)
        t = 0
        ans.append(min(ans_temp))
        ans_temp.clear()
print(sum(ans))

Submission status: Wrong Answer

Solution code:
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)]
Removed = [[0]*N for x in range(N)]
# for m in Mat:
#     print(m)
# print()
Dy, Dx = [1,0,-1,0], [0,1,0,-1]
ans = 0
closed = [[False]*N for _ in range(N)]
for p in P:
    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
            if closed[uy][ux]:
                continue
            ur = Removed[uy][ux]
            if vr:
                if Mat[uy][ux] >= val+1:
                    Mat[uy][ux] = val
                    st.append((uy, ux))
                    closed[uy][ux] = True
                    clsd.append((uy, ux))
            else:
                if Mat[uy][ux] >= val+2:
                    Mat[uy][ux] = val+1
                    closed[uy][ux] = True
                    clsd.append((uy, ux))
    for y, x in clsd:
        closed[y][x] = False
    assert not any([any(c) for c in closed])
# for m in Mat:
#     print(m)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
from math import floor, sqrt, factorial, hypot, log  # log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter, defaultdict, deque
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint


def ceil(a, b): return (a + b - 1) // b


inf = float('inf')
mod = 10 ** 9 + 7


def pprint(*A):
    for a in A:     print(*a, sep='\n')


def INT_(n): return int(n) - 1


def MI(): return map(int, input().split())


def MF(): return map(float, input().split())


def MI_(): return map(INT_, input().split())


def LI(): return list(MI())


def LI_(): return [int(x) - 1 for x in input().split()]


def LF(): return list(MF())


def LIN(n: int): return [I() for _ in range(n)]


def LLIN(n: int): return [LI() for _ in range(n)]


def LLIN_(n: int): return [LI_() for _ in range(n)]


def LLI(): return [list(map(int, l.split())) for l in input()]


def I(): return int(input())


def F(): return float(input())


def ST(): return input().replace('\n', '')


def main():
    N = I()
    P = MI()
    emp = [[1] * (N + 1) for _ in range(N + 1)]
    dp = [[inf] * (N + 1) for _ in range(N + 1)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    for x in range(1, N + 1):
        for y in range(1, N + 1):
            ax = min(x - 1, N - x)
            ay = min(y - 1, N - y)
            dp[x][y] = min(ax, ay)
    ans = 0
    for i in P:
        y = (i % N)
        x = (i // N) + 1
        if y == 0:
            y += N
            x -= 1
        ans += dp[x][y]
        emp[x][y] = 0
        q = deque([(x, y, -1)])
        while q:
            now = q.popleft()
            for j in range(len(dx)):
                if j == now[2]:
                    continue
                nx = now[0] + dx[j]
                ny = now[1] + dy[j]
                if 1 <= nx <= N and 1 <= ny <= N and dp[nx][ny] == dp[now[0]][now[1]] + 1 + emp[now[0]][now[1]]:
                    dp[nx][ny] -= 1
                    q.append((nx, ny, j))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
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)]
Removed = [[0]*N for x in range(N)]
# for m in Mat:
#     print(m)
# print()
Dy, Dx = [1,0,-1,0], [0,1,0,-1]
ans = 0
closed = [[False]*N for _ in range(N)]
for p in P:
    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
            if closed[uy][ux]:
                continue
            ur = Removed[uy][ux]
            if vr:
                if Mat[uy][ux] >= val+1:
                    Mat[uy][ux] = val
                    st.append((uy, ux))
                    closed[uy][ux] = True
                    clsd.append((uy, ux))
            else:
                if Mat[uy][ux] >= val+2:
                    Mat[uy][ux] = val+1
                    closed[uy][ux] = True
                    clsd.append((uy, ux))
    for y, x in clsd:
        closed[y][x] = False
# for m in Mat:
#     print(m)
print(ans)

Submission status: Wrong Answer

Solution code:
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()
for i in range(len(p)):
    mod = p[i] % n
    if mod in end or p[i] in f_l or p[i] in e_l:
        s.add(p[i])
        continue
    hate = 0
    line = p[i] // n + 1
    right = {p[i] - k for k in range(1, mod)}
    left = {p[i] + k for k in range(1, n-mod+1)}
    front = {p[i] - k * n for k in range(1, line)}
    rear = {p[i] + k * n for k in range(1, abs(line - n) + 1)}
    if s >= right or s >= left or s >= front or s >= rear:
        s.add(p[i])
        continue
    else:
        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:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

from pprint import pprint

N = ri()
P = rl()

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

def init(xflip, yflip):
    for i in range(1, math.ceil(N/2)):
        for j in range(1, math.ceil(N/2)):
            ni, nj = i, j
            di, dj = -1, -1
            if xflip:
                nj = N-1-j
                dj = 1
            if yflip:
                ni = N-1-i
                di = 1
            dp[ni][nj] = min(dp[ni+di][nj],dp[ni][nj+dj])+1

for xflip, yflip in [(0,0),(1,0),(0,1),(1,1)]:
    init(xflip, yflip)

def get_ij(p):
    n = p-1
    i = n // N
    j = n % N
    return i, j

import collections
outs = {}
def update(i, j):
    outs[(i,j)] = 1
    queue = collections.deque()
    queue.append((i,j))
    while queue:
        i, j = queue.pop()
        for di, dj in [(1,0),(-1,0),(0,1),(0,-1)]:
            ni, nj = i+di, j+dj
            if not (0 <= ni < N and 0 <= nj < N):
                continue
            if dp[ni][nj] > dp[i][j]:
                dp[ni][nj] = dp[i][j]
                if (ni,nj) in outs:
                    queue.append((ni,nj))

ans = 0
for p in P:
    n = p-1
    i, j = get_ij(p)
    ans += dp[i][j]
    update(i,j)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

N = int(input())
p = list(map(int, input().strip().split()))
num = N**2
P = np.ones(num)
ans = 0

for i in range(num):
    a = p[i]
    P[a-1] = i
P = P.reshape([N,N])
# print(P)
for i in range(N-2):
    for j in range(N-2):
        status = False
        status2 = False
        status3 = False
        status4 = False
        st = False
        st2 = False
        for k in range(i+1):
            if P[i+1][j+1] < P[k][j+1]:
                status = True
            if P[i+1][j+1] < P[i+1][k]:
                status2 = True
        for k in range(N-i-2):
            if P[i+1][j+1] < P[k+i+2][j+1]:
                status3 = True
            if P[i+1][j+1] < P[i+1][k+i+2]:
                status4 = True
        if status and status2:
            st = True
        if status3 and status4:
            st2 = True
        if st and st2:
            # print(P[i+1][j+1])
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
def resolve():
    import numpy as np
    N = int(input())
    P = [int(i) for i in input().split()]
    tab = np.ones((N, N), dtype=np.int)
    ans = 0
    for p in P:
        x, y = divmod(p - 1, N)
        tab[x][y] = 0
        if min(x, y) == 0 or max(x, y) == N - 1:
            continue
        l_sum = sum(tab[x, :y])
        r_sum = sum(tab[x, y + 1:])
        u_sum = sum(tab[:y, x])
        d_sum = sum(tab[y + 1:, x])
        ans += min(l_sum, r_sum, u_sum, d_sum)
    print(ans)


resolve()

Submission status: Wrong Answer

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

grid = [[i for i in range(1+j,n+j+1)]for j in range(0,n**2,n)]
end = []
madlist = []
ans = 0
for i in range(len(p)):
    x = p[i]//n if p[i]%n != 0 else p[i]//n-1
    y = (p[i]-1)%n
    mad1 = 0
    mad2 = 0
    mad3 = 0
    mad4 = 0
    dx = 1
    while x+dx <= n-1:
        if grid[x+dx][y] not in end:
            mad1 += 1
        dx += 1

    dx = -1
    while x + dx >= 0:
        if grid[x + dx][y] not in end:
            mad2 += 1
        dx -= 1
    dy = 1
    while y + dy <= n-1:
        if grid[x][y+dy] not in end:
            mad3 += 1
        dy += 1
            
    dy = -1
    while y + dy >= 0:
        if grid[x][y+dy] not in end:
            mad4 += 1
        dy -= 1
    if min(mad1,mad2,mad3,mad4) != 0:
        ans += min(mad1,mad2,mad3,mad4)
        #madlist.append(p[i])
    end.append(p[i])
print(ans)
#print(madlist)

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 = [[max(0,min(y,x,n-y-1,n-x-1)+1) for x in range(n+2)] for y in range(n+2)]
    r = [[(y,x+1) for x in range(n+2)] for y in range(n+2)]
    l = [[(y,x-1) for x in range(n+2)] for y in range(n+2)]
    d = [[(y+1,x) for x in range(n+2)] for y in range(n+2)]
    u = [[(y-1,x) for x in range(n+2)] for y in range(n+2)]
    f = [[1]*(n+2) for i in range(n+2)]
    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):
            nd = s[ny][nx]+f[ny][nx]
            if nd < dyx:
                dyx = nd
        f[y][x] = 0
        s[y][x] = dyx
        ans += dyx
        for ny,nx in (ri,le,do,up):
            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-n**2)
    return

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque
import sys
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 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])

    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)
        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()
            for t in (set(around(e[0], e[1])) - 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:
#!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 = [[max(0,min(y,x,n-y-1,n-x-1)+1) for x in range(n+2)] for y in range(n+2)]
    r = [[(y,x+1) for x in range(n+2)] for y in range(n+2)]
    l = [[(y,x-1) for x in range(n+2)] for y in range(n+2)]
    d = [[(y+1,x) for x in range(n+2)] for y in range(n+2)]
    u = [[(y-1,x) for x in range(n+2)] for y in range(n+2)]

    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):
            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 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-n**2)
    return

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

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 = [[max(0,min(y,x,n-y-1,n-x-1)+1) for x in range(n+2)] for y in range(n+2)]
    r = [[(y,x+1) for x in range(n+2)] for y in range(n+2)]
    l = [[(y,x-1) for x in range(n+2)] for y in range(n+2)]
    d = [[(y+1,x) for x in range(n+2)] for y in range(n+2)]
    u = [[(y-1,x) for x in range(n+2)] for y in range(n+2)]

    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-n**2)
    return

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

Submission status: Wrong Answer

Solution code:
N=int(input())
list = list(map(int, input().split()))
blist=[]
z=1
while(z<=N**2):
  blist.append(int(z))
  z+=1

def check(num):
  if(num<=N):
    return 0
  elif(N**2-N+1 <= num <= N**2):
    return 0
  elif(num % N==0):
    return 0
  elif(num % N==1):
    return 0
  else:
    i=1
    tmp1=0
    while(i<=N):
      if(blist.count(num-N*i)!=0):
        tmp1+=1
      i+=1
    j=1
    tmp2=0
    while(j<=N):
      if(blist.count(num+N*j)!=0):
        tmp2+=1
      j+=1
    tmp3=0
    p=num
    while(p % N !=0):
      p=p+1
      if(blist.count(p)!=0):
        tmp3+=1
    tmp4=0
    q=num
    while(q % N !=1):
      q=q-1
      if(blist.count(q)!=0):
        tmp4+=1
    if(tmp1==0 or tmp2==0 or tmp3==0 or tmp4==0):
      return 0
    else:
      tmplist=[]
      tmplist.append(tmp1)
      tmplist.append(tmp2)
      tmplist.append(tmp3)
      tmplist.append(tmp4)
      at=min(tmplist)
#      return tmplist.count(at)
      return(at)
k=0
res=0
l=len(list)

while(k<l):
  a=list[k]
  blist.remove(a)
  if(check(a)!=0):
    res+=check(a)
  k+=1

print(res)