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: Runtime Error

Solution code:
import sys
#import numpy as np
#import math
#from fractions import Fraction
#import itertools
from collections import deque
#import heapq
from fractions  import gcd

input=sys.stdin.readline

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

inf = 0
num_min =2**(n-1).bit_length()
dat1=[inf]*(2*num_min-1)
dat2=[inf]*(2*num_min-1)

#初期化
for i in range(n):
    dat1[i+num_min-1]=1
    dat2[i+num_min-1]=1
for i in range(num_min-2,-1,-1):
    dat1[i]=dat1[2*i+1]+dat1[2*i+2]
    dat2[i]=dat2[2*i+1]+dat2[2*i+2]

#親のノード(n-1)//2
#子のノード2n+1,2n+2

def segfunc(x,y):
    return x+y

def update1(i,x):
    i+=num_min-1
    dat1[i]=x
    while i>0:
        i=(i-1)//2
        dat1[i]=segfunc(dat1[2*i+1],dat1[2*i+2])

def update2(i,x):
    i+=num_min-1
    dat2[i]=x
    while i>0:
        i=(i-1)//2
        dat2[i]=segfunc(dat2[2*i+1],dat2[2*i+2])

def query1(a,b): #半開区間、[a,b)の最小値
    if b<=a:
        return inf
    res1=inf
    a += num_min-1
    b += num_min-2
    while b-a>1:
        if a&1==0:
            res1 = segfunc(res1,dat1[a])
        if b&1==1:
            res1 = segfunc(res1,dat1[b])
        a=a//2
        b=(b-1)//2
    if a==b:
        res1 = segfunc(res1,dat1[a])
    else:
        res1=segfunc(segfunc(res1,dat1[a]),dat1[b])
    return res1
def query2(a,b): #半開区間、[a,b)の最小値
    if b<=a:
        return inf
    res2=inf
    a += num_min-1
    b += num_min-2
    while b-a>1:
        if a&1==0:
            res2 = segfunc(res2,dat2[a])
        if b&1==1:
            res2 = segfunc(res2,dat2[b])
        a=a//2
        b=(b-1)//2
    if a==b:
        res2 = segfunc(res2,dat2[a])
    else:
        res2=segfunc(segfunc(res2,dat2[a]),dat2[b])
    return res2

ans=0
for k in p:
    i=k//m
    j=k%m
    l=(j-1)*m+i+1
    if j==0:
        j=m
    res1=min(query1(i*m,k-1),query1(k,(i+1)*m))
    update1(k-1,0)
    res2=min(query2((j-1)*m,l-1),query2(l,j*m))
    r=min(res1,res2)
    ans+=r
    update2(l-1,0)
print(ans)

Submission status: Runtime Error

Solution code:
dfgd

Submission status: Runtime Error

Solution code:
from math import ceil

n = int(input())
seats = [[1 for i in range(n)] for j in range(n)]

a = list(map(int, input().split()))

hate = 0

for i in range(n**2):
	num = a[i]
	y = ceil(num/n) - 1
	x = (num-1) % n

	seats[y][x] = 0
	if x == 0 or y == 0 or x == n-1 or y == n-1:
		continue
	#Horizontal - Right
	num1 = sum(seats[y][x:])
	#Horizontal - Left
	num2 = sum(seats[y][:x+1])
	#Vertical - Up
	s = 0
	for i in range(y):
		s += seats[i][x]	
	#Verctial - Down
	num4 = sum(seats[y:][x])
	hate += min(num1, num2, s, num4)


print(hate)

Submission status: Runtime Error

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

def main():
    N=int(input())
    que=list(map(int,input().split()))
    from collections import defaultdict
    dif=[1,-1,N,-N]
    graph={i:defaultdict(int) for i in range(N**2+1)}
    for i in range(N):
        for j in range(N):
            node=N*i+j+1
            for num in dif:
                if 1<=node+num<=N**2:
                    graph[node][node+num]=1
                    graph[node+num][node]=1
    ans=0
    for i in range(N):
        graph[0][i+1]=0
        graph[i+1][0]=0
        graph[0][N*(N-1)+i+1]=0
        graph[N*(N-1)+i+1][0]=0
        
    vanished=[False for i in range(N**2+1)]
    
    for i in range(N):
        graph[0][i*N+1]=0
        graph[i*N+1][0]=0
        graph[0][i*N+N]=0
        graph[i*N+N][0]=0
    for some in que:
        ans+=dijkstra(some,graph,N**2)[0]
        vanished[some]=True
        for num in dif:
            if 1<=num+some<=N**2:
                if vanished[num+some]:
                    graph[some][num+some]=0
                    graph[num+some][some]=0
                else:
                    graph[num+some][some]=0
    print(ans)    
if __name__=="__main__":
    main()

Submission status: Runtime Error

Solution code:

import numpy as np
import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline


def ij_to_n(i,j,W):
    return i*W+j

def n_to_ij(n,W):
    return (n//W,n%W)


def n_to_ij_oneoffset(n,W):
    #n+=1
    return (1+(n-1)//W,1+(n-1)%W)


def acinput():
    return list(map(int, input().split(" ")))
       

directions=np.array([[1,0],[0,1],[-1,0],[0,-1]])
directions = list(map(np.array, directions))


N=int(input())
H,W=N,N


""" field = [[-1]*(N+2)]

for i in range(N):
    tmp=[-1]
    
    inputv=[]
    tmp.extend([0]*N)
    tmp.append(-1)           
    field.append(tmp)
    
for i in range(1,N+1):
    for j in range(1,N+1):
        field[i][j]=N*(i-1)+j
        
field.append([-1]*(N+2)) """

dp=np.full([H+2,W+2],300)
state=np.full([H+2,W+2],1)

def propagete(x):
    global directions,state
    v=dp[x[0],x[1]]+state[x[0],x[1]]
    #print(x,v)
    for sd in directions:
        nd=x+sd
        if dp[nd[0],nd[1]]>v:
            dp[nd[0],nd[1]]=v
            propagete(nd)
            

for i in range(1,N+1):
    for j in range(1,N+1):
        dp[i,j]=min(i-1,H-i,j-1,W-j)
        
P=acinput()  

dp[1,:]=0
dp[H,:]=0
dp[:,1]=0
dp[:,W]=0

dp[0,:]=0
dp[H+1,:]=0
dp[:,0]=0
dp[:,W+1]=0

#print(dp)
res=0
for p in P:
    r=n_to_ij_oneoffset(p,N)
    #print(p,r)
    #print(dp[r[0],r[1]])
    res+=dp[r[0],r[1]]
    state[r[0],r[1]]=0
    propagete(r)
    
print(res)

#print(dp)

Submission status: Runtime Error

Solution code:
def view(klist):
    for kl in klist:
        print(kl)

def kousin(klist, koho):
    koho2=[]
    for kh in koho:
        tate=kh[0][0]
        yoko=kh[0][1]
        tesu=kh[1]
        if clist[tate][yoko]==0:
            if tate<=1:
                koho2.append([[tate+1, yoko], tesu])
                if yoko<=1:
                    koho2.append([[tate, yoko+1], tesu])
                elif yoko>=n-2:
                    koho2.append([[tate, yoko-1], tesu])
                else:
                    koho2.append([[tate, yoko+1], tesu])
                    koho2.append([[tate, yoko-1], tesu])
            elif tate>=n-2:
                koho2.append([[tate-1, yoko], tesu])
                if yoko<=1:
                    koho2.append([[tate, yoko+1], tesu])
                elif yoko>=n-2:
                    koho2.append([[tate, yoko-1], tesu])
                else:
                    koho2.append([[tate, yoko+1], tesu])
                    koho2.append([[tate, yoko-1], tesu])
            else:
                koho2.append([[tate-1, yoko], tesu])
                koho2.append([[tate+1, yoko], tesu])
                if yoko<=1:
                    koho2.append([[tate, yoko+1], tesu])
                elif yoko>=n-2:
                    koho2.append([[tate, yoko-1], tesu])
                else:
                    koho2.append([[tate, yoko+1], tesu])
                    koho2.append([[tate, yoko-1], tesu])
        
        else:
            if tate<=1:
                koho2.append([[tate+1, yoko], tesu+1])
                if yoko<=1:
                    koho2.append([[tate, yoko+1], tesu+1])
                elif yoko>=n-2:
                    koho2.append([[tate, yoko-1], tesu+1])
                else:
                    koho2.append([[tate, yoko+1], tesu+1])
                    koho2.append([[tate, yoko-1], tesu+1])
            elif tate>=n-2:
                koho2.append([[tate-1, yoko], tesu+1])
                if yoko<=1:
                    koho2.append([[tate, yoko+1], tesu+1])
                elif yoko>=n-2:
                    koho2.append([[tate, yoko-1], tesu+1])
                else:
                    koho2.append([[tate, yoko+1], tesu+1])
                    koho2.append([[tate, yoko-1], tesu+1])
            else:
                koho2.append([[tate-1, yoko], tesu+1])
                koho2.append([[tate+1, yoko], tesu+1])
                if yoko<=1:
                    koho2.append([[tate, yoko+1], tesu+1])
                elif yoko>=n-2:
                    koho2.append([[tate, yoko-1], tesu+1])
                else:
                    koho2.append([[tate, yoko+1], tesu+1])
                    koho2.append([[tate, yoko-1], tesu+1])
    koho3=[]
    for kh2 in koho2:
        tate=kh2[0][0]
        yoko=kh2[0][1]
        tesu=kh2[1]
        if klist[tate][yoko]==tesu+1:
            klist[tate][yoko]=tesu
            koho3.append([[tate, yoko], tesu])
        
    koho=koho3
    
    if koho!=[]:
        kousin(klist, koho)
    

n=int(input())
klist=[]
clist=[]

for i in range(n):
    now=[]
    if i<(n+1)//2:
        for j in range(i):
            now.append(j)
        now+=[i]*(n-i*2)
        #print("!")
        for j in range(i):
            now.append(i-j-1)
    else:
        for j in range(n-i):
            now.append(j)
        now+=[n-i-1]*(i*2-n)
        for j in range(n-i):
            now.append(n-i-j-1)
    klist.append(now)
    clist.append([1]*n)

answer=0

plist = list(map(int, input().split()))
for pl in plist:
    now1=(pl-1)//n
    now2=(pl-1)%n
    answer+=klist[now1][now2]
    clist[now1][now2]=0
    kousin(klist, [ [[now1, now2], klist[now1][now2]] ])
    
    #print(pl, answer)
    #view(clist)
    #print(",")
    #view(klist)
    #print(".")
    

print(answer)

Submission status: Runtime Error

Solution code:
import sys
from math import floor

sys.setrecursionlimit(31765)


def dfs(i, j, count):
    global min_count
    if seat[i][j] == 1:
        count += 1
    if i == 0 or i == n - 1 or j == 0 or j == n - 1:
        min_count = min(min_count, count)
        return
    else:
        if count < min_count:
            if i < n / 2:
                dfs(i - 1, j, count)
                if j < n / 2:
                    dfs(i, j - 1, count)
                else:
                    dfs(i, j + 1, count)
                dfs(i + 1, j, count)
            else:
                dfs(i + 1, j, count)
                if j < n / 2:
                    dfs(i, j - 1, count)
                else:
                    dfs(i, j + 1, count)
                dfs(i - 1, j, count)


n = int(input())

p = list(map(int, input().split()))
# print(p)

seat = [[1] * n for _ in range(n)]

count = 0

for i in range(n**2):
    min_count = float('inf')
    j = floor((p[i] - 1) / n)
    k = p[i] % n - 1
    seat[j][k] = 0
    # print(seat)
    dfs(j, k, 0)
    if min_count > 0:
        count += 1

print(count)

Submission status: Runtime Error

Solution code:
from math import ceil

n = int(input())
seats = [[1 for i in range(n)] for j in range(n)]

a = list(map(int, input().split()))

hate = 0

for i in range(n**2):
	num = a[i]
	y = ceil(num/n) - 1
	x = (num-1) % n

	seats[y][x] = 0
	if x == 0 or y == 0 or x == n-1 or y == n-1:
		continue
	#Horizontal - Right
	num1 = sum(seats[y][x:])
	#Horizontal - Left
	num2 = sum(seats[y][:x+1])
	#Vertical - Up
	num3 = sum(seats[:y+1][x])	
	#Verctial - Down
	num4 = sum(seats[y:][x])
	hate += min(num1, num2, num3, num4)


print(hate)

Submission status: Runtime Error

Solution code:
import sys
from math import floor

sys.setrecursionlimit(10946)

def dfs(i, j, count):
    global min_count
    if seat[i][j] == 1:
        count += 1
    if i == 0 or i == n - 1 or j == 0 or j == n - 1:
        min_count = min(min_count, count)
        return
    else:
        if count < min_count:
            dfs(i - 1, j, count)
            dfs(i + 1, j, count)
            dfs(i, j - 1, count)
            dfs(i, j + 1, count)


n = int(input())

p = list(map(int, input().split()))
# print(p)

seat = [[1] * n for _ in range(n)]

count = 0

for i in range(n**2):
    min_count = float('inf')
    j = floor((p[i] - 1) / n)
    k = p[i] % n - 1
    seat[j][k] = 0
    # print(seat)
    dfs(j, k, 0)
    if min_count > 0:
        count += 1

print(count)

Submission status: Runtime Error

Solution code:
n = int(input())
orderstring = input()
ordercopy = orderstring.split(" ")
order = [0]*n
index = 0
while index < n:
    order[index] = int(ordercopy[index])
    index+= 1
seat = [["occupied" for i in range(n)] for j in range(n)]
hated = 0
i = 0
while i < len(order):
    col = order[i] % n
    row = int((order[i] - col) / n)
    col -= 1
    area = [["no" for i in range(n)] for j in range(n)]
    area[row][col] = "yes"
    times = 0
    judge = 0
    while times < 500:
        r = 0
        c = 0
        while 0 < r and r < n - 1:
            while 0 < c and c < n - 1:
                if area[r][c] == "yes" and seat[r-1][c]=="empty":
                    area[r-1][c] = "yes"
                if area[r][c] == "yes" and seat[r][c-1]=="empty":
                    area[r][c-1] = "yes"
                if area[r][c] == "yes" and seat[r+1][c]=="empty":
                    area[r+1][c] = "yes"
                if area[r][c] == "yes" and seat[r][c+1]=="empty":
                    area[r][c+1] = "yes"
                c+= 1
            r+=1
        times+=1
    test = 0
    while test < n:
        if area[0][test] == "yes":
            judge = 1
        test+=1
    test = 0
    while test < n:
        if area[n-1][test] == "yes":
            judge = 1
        test+=1
    test = 0
    while test < n:
        if area[test][0] == "yes":
            judge = 1
        test+=1
    while test < n:
        if area[test][n-1] == "yes":
            judge = 1
        test+=1
    if judge == 0:
        hated+=1
    i+=1
print(hated)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define VAR(v, i) __typeof(i) v=(i)
#define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define all(v) (v).begin(),(v).end()

#define PII pair<int,int>
#define st first
#define nd second
#define pb push_back
#define lint long long int
#define VI vector<int>

#define debug(x) {cout <<#x <<" = " <<x <<endl; }
#define debug2(x,y) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y <<endl; } 
#define debug3(x,y,z) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y << ", " << #z << " = " << z <<endl; } 
#define debugv(x) {{cout <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<endl; }}
#define debugt(t,n) {{cerr <<#t <<" = "; FOR(it,0,(n)) cerr <<t[it] <<", "; cerr <<endl; }}

#define make( x) int (x); scanf("%d",&(x));
#define make2( x, y) int (x), (y); scanf("%d%d",&(x),&(y));
#define make3(x, y, z) int (x), (y), (z); scanf("%d%d%d",&(x),&(y),&(z));
#define make4(x, y, z, t) int (x), (y), (z), (t); scanf("%d%d%d%d",&(x),&(y),&(z),&(t));
#define makev(v,n) VI (v); FOR(i,0,(n)) { make(a); (v).pb(a);} 
#define IOS ios_base::sync_with_stdio(0)
#define HEAP priority_queue

#define read( x) scanf("%d",&(x));
#define read2( x, y) scanf("%d%d",&(x),&(y));
#define read3(x, y, z) scanf("%d%d%d",&(x),&(y),&(z));
#define read4(x, y, z, t) scanf("%d%d%d%d",&(x),&(y),&(z),&(t));
#define readv(v,n) FOR(i,0,(n)) { make(a); (v).pb(a);}
#define jeb() fflush(stdout);

using namespace std;

int n;
int dist[505][505];
int jest[505][505];

void fill() {
	FOR(i,0,n) FOR(j,0,n) dist[i][j] = min(min(i,j), min(n-1-i,n-1-j));
	FOR(i,0,n) FOR(j,0,n) jest[i][j] = 1;
}

VI dx = {1,-1,0,0};
VI dy = {0,0,1,-1};

bool inside(int a, int b) {
	return (a>=0 && b>=0 && a<n && b<n);
}

int compute(int x, int y) {
	int ans = dist[x][y];
	FOR(i,0,4) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (!inside(nx, ny)) return 0;
			ans = min(ans, dist[nx][ny] + jest[nx][ny]);
	}
	return ans;
}
void update(int x, int y) {
	vector<PII> que;
	que.pb({x,y});
	int pos = 0;
	while (pos < que.size()) {
		int x = que[pos].st;
		int y = que[pos].nd;
		pos++;
		FOR(i,0,4) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (!inside(nx, ny)) continue;
			int ndist = compute(nx, ny);
			if (ndist != dist[nx][ny]) {
				dist[nx][ny] = ndist;
				que.pb({nx, ny});
			}
		}
	}
}


int main() {
	read(n);
	fill();
	int ans = 0;
	makev(v, n*n);
	FOR(i,0,v.size()) {
		int a = v[i]-1;
		ans += dist[a%n][a/n];
		jest[a%n][a/n] = 0;
		update(a%n, a/n);
	}
	printf("%d\n", ans);
}

Submission status: Runtime Error

Solution code:
test