Submission #15437687


Source Code Expand

Copy
import sys
import numpy as np
import numba
from numba import njit
i8 = numba.int64

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

@njit((i8[:], i8[:], i8[:], i8[:]), cache=True)
def f(X1, Y1, X2, Y2):
    # x1,y1 から y が増える側に移動 vs x2,y2 から y が減る側に移動
    ret = 10**18
    key1 = (X1 << 32) + Y1
    key2 = (X2 << 32) + Y2
    ind = key1.argsort()
    X1, Y1, key1 = X1[ind], Y1[ind], key1[ind]
    ind = key2.argsort()
    X2, Y2, key2 = X2[ind], Y2[ind], key2[ind]
    js = np.searchsorted(key2, key1)
    for i in range(len(key1)):
        j = js[i]
        if j == len(key2):
            continue
        if X1[i] != X2[j]:
            continue
        ret = min(ret, Y2[j] - Y1[i])
    return ret

N = int(readline())
X = []
Y = []
U = []
for _ in range(N):
    x, y, u = readline().split()
    X.append(int(x))
    Y.append(int(y))
    U.append(u)

X = np.array(X, np.int64)
Y = np.array(Y, np.int64)
U = np.array(U, 'S1')

i_u = U == b'U'
i_r = U == b'R'
i_d = U == b'D'
i_l = U == b'L'

Xu, Yu = X[i_u], Y[i_u]
Xr, Yr = X[i_r], Y[i_r]
Xd, Yd = X[i_d], Y[i_d]
Xl, Yl = X[i_l], Y[i_l]

INF = 10**18
ans = INF
ans = min(ans, f(Xu, Yu, Xd, Yd))  # 上、下
ans = min(ans, f(Yr, Xr, Yl, Xl))  # 右、左
ans = min(ans, f(Xr + Yr, Xr - Yr, Xu + Yu, Xu - Yu))  # 右、上
ans = min(ans, f(Xu - Yu, Xu + Yu, Xl - Yl, Xl + Yl))  # 上、左
ans = min(ans, f(Xr - Yr, Xr + Yr, Xd - Yd, Xd + Yd))  # 右、下
ans = min(ans, f(Xd + Yd, Xd - Yd, Xl + Yl, Xl - Yl))  # 下、左
print('SAFE' if ans == INF else 5 * ans)

Submission Info

Submission Time
Task F - Air Safety
User maspy
Language Python (3.8.2)
Score 600
Code Size 1674 Byte
Status
Exec Time 801 ms
Memory 125584 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt
All 600 / 600 in01.txt, in02.txt, in03.txt, in04.txt, in05.txt, in06.txt, in07.txt, in08.txt, in09.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, in28.txt, in29.txt, in30.txt, in31.txt, in32.txt, in33.txt, in34.txt, in35.txt, in36.txt, in37.txt, in38.txt, in39.txt, in40.txt, in41.txt, in42.txt, in43.txt, in44.txt, in45.txt, in46.txt, in47.txt, in48.txt, in49.txt, in50.txt, in51.txt, in52.txt, in53.txt, in54.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
in01.txt 531 ms 106764 KB
in02.txt 521 ms 106728 KB
in03.txt 519 ms 106940 KB
in04.txt 519 ms 106800 KB
in05.txt 527 ms 107124 KB
in06.txt 543 ms 109128 KB
in07.txt 564 ms 110568 KB
in08.txt 632 ms 116124 KB
in09.txt 796 ms 125512 KB
in10.txt 785 ms 119596 KB
in11.txt 509 ms 106736 KB
in12.txt 525 ms 106468 KB
in13.txt 547 ms 109400 KB
in14.txt 704 ms 120916 KB
in15.txt 511 ms 106732 KB
in16.txt 718 ms 120656 KB
in17.txt 509 ms 106280 KB
in18.txt 523 ms 107544 KB
in19.txt 538 ms 108752 KB
in20.txt 724 ms 121912 KB
in21.txt 510 ms 106776 KB
in22.txt 508 ms 107036 KB
in23.txt 533 ms 108912 KB
in24.txt 730 ms 120368 KB
in25.txt 509 ms 106812 KB
in26.txt 782 ms 123944 KB
in27.txt 519 ms 106724 KB
in28.txt 763 ms 124228 KB
in29.txt 548 ms 106952 KB
in30.txt 798 ms 123712 KB
in31.txt 541 ms 106700 KB
in32.txt 738 ms 125244 KB
in33.txt 541 ms 107028 KB
in34.txt 762 ms 122740 KB
in35.txt 542 ms 106800 KB
in36.txt 759 ms 125584 KB
in37.txt 545 ms 107448 KB
in38.txt 754 ms 123628 KB
in39.txt 545 ms 107352 KB
in40.txt 753 ms 124748 KB
in41.txt 756 ms 122216 KB
in42.txt 785 ms 123364 KB
in43.txt 784 ms 121784 KB
in44.txt 753 ms 125272 KB
in45.txt 801 ms 122196 KB
in46.txt 746 ms 125368 KB
in47.txt 765 ms 119692 KB
in48.txt 738 ms 123028 KB
in49.txt 517 ms 106796 KB
in50.txt 544 ms 107004 KB
in51.txt 550 ms 106808 KB
in52.txt 552 ms 106960 KB
in53.txt 546 ms 106716 KB
in54.txt 548 ms 107000 KB
sample_01.txt 555 ms 106932 KB
sample_02.txt 562 ms 106836 KB
sample_03.txt 544 ms 106792 KB