Submission #13539757


Source Code Expand

Copy
import sys
import numpy as np
from numba import njit

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit('(i4,i4[::1])', cache=True)
def solve(N, P):
    W = N + 2
    dp = np.zeros((W, W), np.int32)
    for _ in range(4):
        dp = dp.T[::-1]
        for n in range(1, (N + 1) // 2 + 1):
            dp[n, n:-n] = n
    filled = np.zeros_like(dp)
    filled[1:-1, 1:-1] = 1
    dp = dp.ravel()
    filled = filled.ravel()
    stack = np.empty_like(dp)
    ans = 0
    for n in P:
        n -= 1
        h, w = divmod(n, N)
        v = (h + 1) * W + (w + 1)
        ans += dp[v] - 1
        filled[v] = 0
        k = min(dp[v - 1], dp[v + 1], dp[v - W], dp[v + W])
        if dp[v] == k:
            return ans
        p = 0
        stack[0] = v
        dp[v] = k
        while p >= 0:
            v = stack[p]
            p -= 1
            for dx in (-1, 1, -W, W):
                w = v + dx
                k = dp[v] + filled[w]
                if dp[w] > k:
                    dp[w] = k
                    p += 1
                    stack[p] = w
    return ans

N = int(readline())
P = np.array(read().split(), np.int32)

print(solve(N, P))

Submission Info

Submission Time
Task B - Joker
User maspy
Language Python (3.8.2)
Score 700
Code Size 1260 Byte
Status
Exec Time 782 ms
Memory 123544 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 example0.txt, example1.txt, example2.txt
All 700 / 700 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, example0.txt, example1.txt, example2.txt
Case Name Status Exec Time Memory
000.txt 506 ms 107276 KB
001.txt 514 ms 109232 KB
002.txt 715 ms 122812 KB
003.txt 489 ms 106080 KB
004.txt 475 ms 106056 KB
005.txt 472 ms 105684 KB
006.txt 472 ms 106360 KB
007.txt 501 ms 106052 KB
008.txt 487 ms 106152 KB
009.txt 488 ms 106796 KB
010.txt 482 ms 106300 KB
011.txt 489 ms 106760 KB
012.txt 480 ms 106088 KB
013.txt 489 ms 106940 KB
014.txt 490 ms 107000 KB
015.txt 514 ms 109832 KB
016.txt 757 ms 121708 KB
017.txt 755 ms 121360 KB
018.txt 774 ms 123544 KB
019.txt 768 ms 121592 KB
020.txt 782 ms 121600 KB
example0.txt 470 ms 106932 KB
example1.txt 482 ms 106900 KB
example2.txt 466 ms 106080 KB