Problem:


Score: 600 points

Problem Statement

M-kun is a brilliant air traffic controller.

On the display of his radar, there are N airplanes numbered 1, 2, ..., N, all flying at the same altitude.

Each of the airplanes flies at a constant speed of 0.1 per second in a constant direction. The current coordinates of the airplane numbered i are (X_i, Y_i), and the direction of the airplane is as follows:

if U_i is U, it flies in the positive y direction;

if U_i is R, it flies in the positive x direction;

if U_i is D, it flies in the negative y direction;

if U_i is L, it flies in the negative x direction.

To help M-kun in his work, determine whether there is a pair of airplanes that will collide with each other if they keep flying as they are now.

If there is such a pair, find the number of seconds after which the first collision will happen.

We assume that the airplanes are negligibly small so that two airplanes only collide when they reach the same coordinates simultaneously.

Constraints

1 \leq N \leq 200000

0 \leq X_i, Y_i \leq 200000

U_i is U, R, D, or L.

The current positions of the N airplanes, (X_i, Y_i), are all distinct.

N, X_i, and Y_i are integers.

Input

Input is given from Standard Input in the following format:

N
X_1 Y_1 U_1
X_2 Y_2 U_2
X_3 Y_3 U_3
:
X_N Y_N U_N

Output

If there is a pair of airplanes that will collide with each other if they keep flying as they are now, print an integer representing the number of seconds after which the first collision will happen.

If there is no such pair, print SAFE.

Sample Input 1

2
11 1 U
11 47 D

Sample Output 1

230

If the airplanes keep flying as they are now, two airplanes numbered 1 and 2 will reach the coordinates (11, 24) simultaneously and collide.  

Sample Input 2

4
20 30 U
30 20 R
20 10 D
10 20 L

Sample Output 2

SAFE

No pair of airplanes will collide.

Sample Input 3

8
168 224 U
130 175 R
111 198 D
121 188 L
201 116 U
112 121 R
145 239 D
185 107 L

Sample Output 3

100



Sample input:
2
11 1 U
11 47 D


Sample output:
230

Submission status: Wrong Answer

Solution code:
#root.search(x): ◯.data == x のものが存在するある場合それを出力、ない場合Noneを出力
#root.insert(x): ◯.data == xが存在する場合Falseを出力、ない場合◯.data == x なる頂点を作る
#y.to_s(): 頂点yのdataを出力
#y.left_s(): 頂点yのleftを出力(ない場合はNone)
#root.search_lower(x,None): ○.dataがxより小さいものの中で最も大きいものを出力、ない場合Noneを出力
#root.search_higher(x,None): xより大きいものの中で最も小さいものを出力、ない場合Noneを出力

################################################################################
class Avltree:
    def __init__(self,key=None):
        self.key = key
        self.left = None
        self.right = None 
        self.balance = "Even"
    def search(self,key):
        if self.key == None:
            return None
        if self.key > key:
            if self.left == None:
                return None
            else:
                return self.left.search(key)
        if self.key < key:
            if self.right == None:
                return None
            else:
                return self.right.search(key)
        return self # self.key == keyの場合
        
    def search_lower(self,key,key_lower):
        if self.key == None:
            return key_lower
        if self.key > key:
            if self.left == None:
                return key_lower
            else:
                return self.left.search_lower(key,key_lower)
        if self.key < key:
            key_lower = self.key
            if self.right == None:
                return key_lower
            else:
                return self.right.search_lower(key,key_lower)
        #self.key == keyの場合
        if self.left == None:
            return key_lower
        else:
            if key_lower == None:
                return self.left.end_higher(self.left.key)
            else:
                return max(key_lower,self.left.end_higher(self.left.key))
    
    def search_higher(self,key,key_higher):
        if self.key == None:
            return key_higher
        if self.key > key:
            key_higher = self.key
            if self.left == None:
                return key_higher
            else:
                return self.left.search_higher(key,key_higher)
        if self.key < key:
            if self.right == None:
                return key_higher
            else:
                return self.right.search_higher(key,key_higher)
        #self.key == keyの場合
        if self.right == None:
            return key_higher
        else:
            if key_higher == None:
                return self.right.end_lower(self.right.key)
            else:
                return min(key_higher,self.right.end_lower(self.right.key))
        
    
    def end_lower(self,end_lower_key):
        if self.left == None:
            return end_lower_key
        else:
            end_lower_key = self.left.key
            return self.left.end_lower(end_lower_key)
    def end_higher(self,end_higher_key):
        if self.right == None:
            return end_higher_key
        else:
            end_higher_key = self.right.key
            return self.right.end_higher(end_higher_key)
    
            
    def DoubleRightRotation(self):
        tl = self.left
        self.left = tl.right.right
        tl.right.right = self # selfはそのノード
        tlr = tl.right
        tl.right = tlr.left
        tlr.left = tl
        if tlr.balance == "Left":
            tlr.right.balance = "Right"
            tlr.left.balance = "Even"
        elif tlr.balance == "Right":
            tlr.right.balance = "Even"
            tlr.left.balance = "Left"
        elif tlr.balance == "Even":
            tlr.right.balance = "Even"
            tlr.left.balance = "Even"
        tlr.balance = "Even"
        return tlr
    def DoubleLeftRotation(self):
        tr = self.right
        self.right = tr.left.left
        tr.left.left = self
        trl = tr.left
        tr.left = trl.right
        trl.right = tr
        if trl.balance == "Right":
            trl.left.balance = "Left"
            trl.right.balance = "Even"
        elif trl.balance == "Left":
            trl.left.balance = "Even"
            trl.right.balance = "Right"
        elif trl.balance == "Even":
            trl.left.balance = "Even"
            trl.right.balance = "Even"
        trl.balance = "Even"
        return trl
    def SingleLeftRotation(self):
        tr = self.right
        tr.balance = "Even"
        self.balance = "Even"
        self.right = tr.left
        tr.left = self
        return tr
    def SingleRightRotation(self):
        tl = self.left
        tl.balance = "Even"
        self.balance = "Even"
        self.left = tl.right
        tl.right = self
        return tl
    def replace(self,p,v): # 親ノードpの下にある自分(self)をvに置き換える。
        if p.left == self:
            p.left = v
        else :
            p.right = v 
    def insert(self,key): # rootでのみ呼ばれる挿入
        if self.key == None: # rootを含むrotationはしないことにする。
            self.key = key
            return self
        if key < self.key:
            if self.left == None:
                self.left = Avltree(key)
            else:
                self.left.insertx(self,key)
        elif key > self.key:
            if self.right == None:
                self.right = Avltree(key)
            else:
                self.right.insertx(self,key)
        else: # key == self.key:
            pass # do not overwrite
    def insertx(self,p,key): # replaceを呼ぶために一つ上の親を持っているinsert
        if self.key > key:
            if self.left == None:
                self.left = Avltree(key)
            else:
                if not self.left.insertx(self, key): # 左の木が生長しなければ、
                    return False # 成長しない
            if self.balance == "Right":
                self.balance = "Even"
                return False
            elif self.balance == "Even":
                self.balance = "Left"
                return True # 成長した
            elif self.balance == "Left":
                if self.left.balance == "Right":
                    self.replace(p,self.DoubleRightRotation())
                elif self.left.balance == "Left":
                    self.replace(p,self.SingleRightRotation())
                return False # rotationを行うと成長しない
        if self.key < key:
            if self.right == None:
                self.right = Avltree(key)
            else:
                if not self.right.insertx(self, key):
                    return False 
            if self.balance == "Left":
                self.balance = "Even"
                return False
            elif self.balance == "Even":
                self.balance = "Right"
                return True
            elif self.balance == "Right":
                if self.right.balance == "Left": 
                    self.replace(p,self.DoubleLeftRotation())
                elif self.right.balance == "Right":
                    self.replace(p,self.SingleLeftRotation())
                return False
        return False # self.key == keyの時は何もしないので成長もしない 

    def to_s(self):
        return self.key
    def left_s(self):
        if self.left == None:
            return None
        return (self.left).key
    def right_s(self):
        if self.right == None:
            return None
        return (self.right).key


n = int(input())
a = [list(input().split()) for i in range(n)]
for i in range(n):
    if a[i][2] == "R":
        a[i][2] = 1
    elif a[i][2] == "L":
        a[i][2] = 2
    elif a[i][2] == "U" :
        a[i][2] = 3
    else:
        a[i][2] = 4
    a[i][0] = int(a[i][0])
    a[i][1]=int(a[i][1])
a.sort(key=lambda x: x[2])
m = 200001
R1 = [Avltree() for i in range(400002)]
R2 = [Avltree() for i in range(400002)]
L1 = [Avltree() for i in range(400002)]
L2 = [Avltree() for i in range(400002)]
U = [Avltree() for i in range(400002)]
R = [Avltree() for i in range(400002)]

M=100000000000
for x, y, u in a:
    if u == 1:
        R1[y - x + m].insert(x)
        R2[x + y].insert(x)
        R[y].insert(x)
    elif u == 2:
        L1[x + y].insert(x)
        L2[y - x + m].insert(x)
        k = R[y].search_lower(x, None)
        if k:
            M = min((x-k)*5, M)

    if u == 3:
        k = L2[y - x + m].search_higher(x, None)
        if k:
            M = min(M, (k-x)*10)
        k = R2[x + y].search_lower(x, None)
        if k:
            M = min(M, (x - k)*10)
        U[x].insert(y)
    if u == 4:
        k = L1[x + y].search_higher(x, None)
        if k:
            M = min(M, (k-x)*10)
        k = L1[y - x + m].search_lower(x, None)
        if k:
            M = min(M, (x - k)*10)
        k = U[x].search_lower(y, None)
        if k:
            M = min(M, (y-k)*5)
print(M if M<100000000000 else "SAFE")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from bisect import bisect_left

INF = 10**18


def main():

    N = int(input())

    X = defaultdict(lambda: [[] for _ in range(4)])
    Y = defaultdict(lambda: [[] for _ in range(4)])
    XY_plus = defaultdict(lambda: [[] for _ in range(4)])
    XY_minus = defaultdict(lambda: [[] for _ in range(4)])
    URDL = ['U', 'R', 'D', 'L']

    for i in range(N):
        x, y, u = input().split()
        x, y = int(x), int(y)
        u = URDL.index(u)

        X[y][u].append(x)
        Y[x][u].append(y)
        XY_plus[x + y][u].append(x)
        XY_minus[x - y][u].append(x)

    for s in (X, Y, XY_plus, XY_minus):
        for k in s.keys():
            for i in range(4):
                s[k][i].sort()

    def calc(data, p, q):

        ret = INF
        for k in data.keys():
            for i in range(len(data[k][p])):
                now = data[k][p][i]
                j = bisect_left(data[k][q], now)

                if j < len(data[k][q]):
                    next = data[k][q][j]
                    ret = min(ret, (next - now) * 10)

        return ret

    ans = INF
    ans = min(ans, calc(X, 1, 3) // 2)
    ans = min(ans, calc(Y, 0, 2) // 2)
    ans = min(ans, calc(XY_plus, 1, 0))
    ans = min(ans, calc(XY_plus, 2, 3))
    ans = min(ans, calc(XY_minus, 1, 2))
    ans = min(ans, calc(XY_minus, 0, 3))

    if ans >= 500000:
        print('SAFE')
    else:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
xyu=[list(input().split()) for i in range(n)]
for i in range(n):
    x,y,u=xyu[i]
    xyu[i]=[int(x),int(y),u]

ans=mod

xyu.sort(lambda x: x[1])
tate=[-1]*200001
for i in range(n):
    x,y,u=xyu[i]
    if u=="D":
        if tate[x]!=-1:
            ans=min(ans,(y-tate[x])*5)
    else:
        tate[x]=y

xyu.sort(lambda x: x[0])
yoko=[-1]*200001
for i in range(n):
    x,y,u=xyu[i]
    if u=="L":
        if yoko[y]!=-1:
            ans=min(ans,(x-yoko[y])*5)
    else:
        yoko[y]=x



cnt=[[] for i in range(2*200001)]
for i in range(n):
    x,y,u=xyu[i]
    cnt[x+y].append(i)

for i in range(len(cnt)):
    ul=[-1]*2
    cnt[i].sort(lambda x: xyu[x][1])
    for j in range(len(cnt[i])):
        x,y,u=xyu[cnt[i][j]]
        if u=="U":
            ul[0]=y
        elif u=="L":
            ul[1]=y
        elif u=="D" and ul[1]!=-1:
            ans=min(ans,(y-ul[1])*10)
        elif u=="R" and ul[0]!=-1:
            ans=min(ans,(y-ul[0])*10)
    
cnt=[[] for i in range(2*200001)]
for i in range(n):
    x,y,u=xyu[i]
    cnt[200000-x+y].append(i)

for i in range(len(cnt)):
    ur=[-1]*2
    cnt[i].sort(lambda x: xyu[x][1])
    for j in range(len(cnt[i])):
        x,y,u=xyu[cnt[i][j]]
        if u=="U":
            ur[0]=y
        elif u=="R":
            ur[1]=y
        elif u=="D" and ur[1]!=-1:
            ans=min(ans,(y-ur[1])*10)
        elif u=="L" and ur[0]!=-1:
            ans=min(ans,(y-ur[0])*10)

if ans!=mod:
    print(ans)
else:
    print("SAFE")

Submission status: Wrong Answer

Solution code:
import numpy as np
ans = []
#
#f = open('./input_F.txt')
#
#N = int(f.readline())
#X = []
#Y = []
#U = []
#for i in range(N):
#    XYU = list(map(str, f.readline().split()))
#    X.append(int(XYU[0]))
#    Y.append(int(XYU[1]))
#    U.append(XYU[2])



N = int(input())
U = []
X = []
Y=[]
for i in range(N):
    XYU = list(map(str, input().split()))
    X.append(int(XYU[0]))
    Y.append(int(XYU[1]))
    U.append(XYU[2])
    
    
    
X_minus_Y = [X[i]-Y[i] for i in range(N)]
X_plus_Y = [X[i]+Y[i] for i in range(N)]

X_argsort = np.argsort(np.array(X))
Y_argsort = np.argsort(np.array(Y))
XmY_argsort = np.argsort(np.array(X_minus_Y))
XpY_argsort = np.argsort(np.array(X_plus_Y))

for i in range(N-1):
    Xi = X_argsort[i]
    Xii = X_argsort[i+1]
    Yi = Y_argsort[i]
    Yii = Y_argsort[i+1]
    XmYi = XmY_argsort[i]
    XmYii = XmY_argsort[i+1]
    XpYi = XpY_argsort[i]
    XpYii = XpY_argsort[i+1]
    
    if X[Xi]==X[Xii]:
        if Y[Xi]>Y[Xii] and U[Xi] == "D" and U[Xii] == "U":
            ans.append((Y[Xi]-Y[Xii])*10//2)
        elif Y[Xi]<Y[Xii] and U[Xi] == "U" and U[Xii] == "D":
            ans.append((Y[Xii]-Y[Xi])*10//2)
    
    if Y[Yi]==Y[Yii]:
        if X[Yi]>X[Yii] and U[Yi] == "L" and U[Yii] == "R":
            ans.append((X[Yi]-X[Yii])*10//2)
        elif X[Yi]<X[Yii] and U[Yi] == "R" and U[Yii] == "L":
            ans.append((X[Yii]-X[Yi])*10//2)

    if X_minus_Y[XmYi]==X_minus_Y[XmYii]:
        if X[XmYi]>X[XmYii]:
            if U[XmYi] == "D" and U[XmYii] == "R":
                ans.append((X[XmYi]-X[XmYii])*10)
            elif U[XmYi] == "L" and U[XmYii] == "U":
                ans.append((X[XmYi]-X[XmYii])*10)                
        elif X[XmYi]<X[XmYii]:
            if U[XmYi] == "R" and U[XmYii] == "D":
                ans.append((X[XmYi]-X[XmYii])*10*(-1))
            elif U[XmYi] == "U" and U[XmYii] == "L":
                ans.append((X[XmYi]-X[XmYii])*10*(-1))
                
    if X_plus_Y[XpYi]==X_plus_Y[XpYii]:
        if X[XpYi]>X[XpYii]:
            if U[XpYi] == "U" and U[XpYii] == "R":
                ans.append((X[XpYi]-X[XpYii])*10)
            elif U[XpYi] == "L" and U[XpYii] == "D":
                ans.append((X[XpYi]-X[XpYii])*10)                
        elif X[XpYi]<X[XpYii]:
            if U[XpYi] == "D" and U[XpYii] == "L":
                ans.append((X[XpYi]-X[XpYii])*10*(-1))
            elif U[XpYi] == "R" and U[XpYii] == "U":
                ans.append((X[XpYi]-X[XpYii])*10*(-1))
                
#XYarray = np.array([X,Y,X_minus_Y,X_plus_Y]).T

ans = [abs(x) for x in ans]                

if len(ans)==0:
    final_ans = "SAFE"
else:
    final_ans = int(min(ans))


print(final_ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
x = [0]*n
y = [0]*n

ux = [0]*n
uy = [0]*n


for i in range(n):
    px,py,u =  input().split()
    if u=="U":
        uy[i] =1
    elif u=="R":
        ux[i] =1
    elif u=="D":
        uy[i] =-1
    elif u=="L":
        ux[i] =-1
    x[i]= int(px)
    y[i]= int(py)
time = 2*10**7
for i in range(n):
    for j in range(n-1-i):

            if x[i]-x[i+1+j] == 0 and  y[i]-y[i+1+j] == 0:
                time = min(time,0)
            elif x[i]-x[i+1+j] == 0 and uy[i]*uy[i+1+j]==-1:
                if (y[i]-y[i+1+j])<0 and uy[i]>0:
                    time = min(time,abs((y[i]-y[i+1+j])/0.2))
                elif (y[i]-y[i+1+j])>0 and uy[i]<0:
                    time = min(time,abs((y[i]-y[i+1+j])/0.2))
            elif y[i]-y[i+1+j] == 0 and ux[i]*ux[i+1+j]==-1:
                if (x[i] - x[i + 1 + j]) < 0 and ux[i] > 0:
                    time = min(time,abs((x[i]-x[i+1+j])/0.2))
                elif (x[i] - x[i + 1 + j]) > 0 and ux[i] < 0:
                    time = min(time,abs((x[i]-x[i+1+j])/0.2))
            elif (ux[i]-ux[i+1+j])==0 or (uy[i]-uy[i+1+j])==0:
                time =time

            elif (x[i]-x[i+1+j]) ==(y[i]-y[i+1+j]) and (ux[i]-ux[i+1+j]) ==(uy[i]-uy[i+1+j]):
                time = min(time,abs((x[i]-x[i+1+j])/0.1))
            elif (x[i]-x[i+1+j]) ==-(y[i]-y[i+1+j]) and (ux[i]-ux[i+1+j]) ==-(uy[i]-uy[i+1+j]):
                time = min(time,abs((x[i]-x[i+1+j])/0.1))

if time == 2*10**7:
    print("SAFE")
else:
    print(int(time))

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
xyu=[list(input().split()) for i in range(n)]
for i in range(n):
    x,y,u=xyu[i]
    xyu[i]=[int(x),int(y),u]

ans=mod

xyu.sort(lambda x: x[1])
tate=[-1]*200001
for i in range(n):
    x,y,u=xyu[i]
    if u=="D" and tate[x]!=-1:
            ans=min(ans,(y-tate[x])*5)
    else:
        tate[x]=y

xyu.sort(lambda x: x[0])
yoko=[-1]*200001
for i in range(n):
    x,y,u=xyu[i]
    if u=="L" and yoko[y]!=-1:
        ans=min(ans,(x-yoko[y])*5)
    else:
        yoko[y]=x



cnt=[[] for i in range(2*200001)]
for i in range(n):
    x,y,u=xyu[i]
    cnt[x+y].append(i)

for i in range(len(cnt)):
    ul=[-1]*2
    cnt[i].sort(lambda x: xyu[x][1])
    for j in range(len(cnt[i])):
        x,y,u=xyu[cnt[i][j]]
        if u=="U":
            ul[0]=y
        elif u=="L":
            ul[1]=y
        elif u=="D" and ul[1]!=-1:
            ans=min(ans,(y-ul[1])*10)
        elif u=="R" and ul[0]!=-1:
            ans=min(ans,(y-ul[0])*10)
    
cnt=[[] for i in range(2*200001)]
for i in range(n):
    x,y,u=xyu[i]
    cnt[200000-x+y].append(i)

for i in range(len(cnt)):
    ul=[-1]*2
    cnt[i].sort(lambda x: xyu[x][1])
    for j in range(len(cnt[i])):
        x,y,u=xyu[cnt[i][j]]
        if u=="U":
            ul[0]=y
        elif u=="R":
            ul[1]=y
        elif u=="D" and ul[1]!=-1:
            ans=min(ans,(y-ul[1])*10)
        elif u=="L" and ul[0]!=-1:
            ans=min(ans,(y-ul[0])*10)

if ans!=mod:
    print(ans)
else:
    print("SAFE")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N=int(input())

uddic=defaultdict(list)
lrdic=defaultdict(list)
uldic=defaultdict(list)
urdic=defaultdict(list)
dldic=defaultdict(list)
drdic=defaultdict(list)

for _ in range(N):
  XS,YS,U=input().split()
  x=int(XS)
  y=int(YS)
  if U=="U":
    uddic[x].append((y,U))
    uldic[x-y].append((x,U))
    urdic[x+y].append((x,U))
  elif U=="D":
    uddic[x].append((y,U))
    dldic[x+y].append((x,U))
    drdic[x-y].append((x,U))
  elif U=="L":
    lrdic[y].append((x,U))
    uldic[x-y].append((x,U))
    dldic[x+y].append((x,U))
  else:
    lrdic[y].append((x,U))
    urdic[x+y].append((x,U))
    drdic[x-y].append((x,U))
    
answer=float("inf")
#UD
for x in uddic:
  ylist=sorted(uddic[x])
  for i in range(len(ylist)-1):
    y1,u1=ylist[i]
    y2,u2=ylist[i+1]
    if u1=="U" and u2=="D":
      answer=min(answer,(y2-y1)*5)
#LR
for y in lrdic:
  xlist=sorted(lrdic[y])
  for i in range(len(xlist)-1):
    x1,u1=xlist[i]
    x2,u2=xlist[i+1]
    if u1=="R" and u2=="L":
      answer=min(answer,(x2-x1)*5)
        
#UL
for xmy in uldic:
  xlist=sorted(uldic[xmy])
  for i in range(len(xlist)-1):
    x1,u1=xlist[i]
    x2,u2=xlist[i+1]
    if u1=="U" and u2=="L":
      answer=min(answer,(x2-x1)*10)
#UR
for xpy in urdic:
  xlist=sorted(urdic[xpy])
  for i in range(len(xlist)-1):
    x1,u1=xlist[i]
    x2,u2=xlist[i+1]
    if u1=="R" and u2=="U":
      answer=min(answer,(x2-x1)*10)
#DL
for xpy in dldic:
  xlist=sorted(dldic[xpy])
  for i in range(len(xlist)-1):
    x1,u1=xlist[i]
    x2,u2=xlist[i+1]
    if u1=="D" and u2=="L":
      answer=min(answer,(x2-x1)*10)
#DR
for xmy in drdic:
  xlist=sorted(dldic[xmy])
  for i in range(len(xlist)-1):
    x1,u1=xlist[i]
    x2,u2=xlist[i+1]
    if u1=="R" and u2=="D":
      answer=min(answer,(x2-x1)*10)
  
if answer==float("inf"):
  print("SAFE")
else:
  print(answer)

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
xyu=[list(input().split()) for i in range(n)]
print("SAFE")

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
xyu=[list(input().split()) for i in range(n)]
for i in range(n):
    x,y,u=xyu[i]
    xyu[i]=[int(x),int(y),u]

ans=mod

xyu.sort(lambda x: x[1])
tate=[-1]*200001
for i in range(n):
    x,y,u=xyu[i]
    if u=="D" and tate[x]!=-1:
            ans=min(ans,(y-tate[x])*5)
    else:
        tate[x]=y

xyu.sort(lambda x: x[0])
yoko=[-1]*200001
for i in range(n):
    x,y,u=xyu[i]
    if u=="L" and yoko[y]!=-1:
        ans=min(ans,(x-yoko[y])*5)
    else:
        yoko[y]=x



cnt=[[] for i in range(2*200001)]
for i in range(n):
    x,y,u=xyu[i]
    cnt[x+y].append(i)

for i in range(len(cnt)):
    ul=[-1]*2
    if len(cnt[i])==0:
        continue
    cnt[i].sort(lambda x: xyu[x][1])
    for j in range(len(cnt[i])):
        x,y,u=xyu[cnt[i][j]]
        if u=="U":
            ul[0]=y
        elif u=="L":
            ul[1]=y
        elif u=="D" and ul[1]!=-1:
            ans=min(ans,(y-ul[1])*10)
        elif u=="R" and ul[0]!=-1:
            ans=min(ans,(y-ul[0])*10)
    
cnt=[[] for i in range(2*200001)]
for i in range(n):
    x,y,u=xyu[i]
    cnt[200000-x+y].append(i)

for i in range(len(cnt)):
    ul=[-1]*2
    if len(cnt[i])==0:
        continue
    cnt[i].sort(lambda x: xyu[x][1])
    for j in range(len(cnt[i])):
        x,y,u=xyu[cnt[i][j]]
        if u=="U":
            ul[0]=y
        elif u=="R":
            ul[1]=y
        elif u=="D" and ul[1]!=-1:
            ans=min(ans,(y-ul[1])*10)
        elif u=="L" and ul[0]!=-1:
            ans=min(ans,(y-ul[0])*10)

if ans!=mod:
    print(ans)
else:
    print("SAFE")

Submission status: Wrong Answer

Solution code:
import numpy as np
ans = []
#
#f = open('./input_F.txt')
#
#N = int(f.readline())
#XY = []
#X = []
#Y = []
#U = []
#for i in range(N):
#    XYU = list(map(str, f.readline().split()))
#    XY.append([int(XYU[0]),int(XYU[1])])
#    X.append(int(XYU[0]))
#    Y.append(int(XYU[1]))
#    U.append(XYU[2])



N = int(input())
XY = []
U = []
X = []
Y=[]
for i in range(N):
    XYU = list(map(str, input().split()))
    XY.append([int(XYU[0]),int(XYU[1])])
    X.append(int(XYU[0]))
    Y.append(int(XYU[1]))
    U.append(XYU[2])
    
    
    
X_minus_Y = [X[i]-Y[i] for i in range(N)]
X_plus_Y = [X[i]+Y[i] for i in range(N)]

X_argsort = np.argsort(np.array(X))
Y_argsort = np.argsort(np.array(Y))
XmY_argsort = np.argsort(np.array(X_minus_Y))
XpY_argsort = np.argsort(np.array(X_plus_Y))

for i in range(N-1):
    Xi = X_argsort[i]
    Xii = X_argsort[i+1]
    Yi = Y_argsort[i]
    Yii = Y_argsort[i+1]
    XmYi = XmY_argsort[i]
    XmYii = XmY_argsort[i+1]
    XpYi = XpY_argsort[i]
    XpYii = XpY_argsort[i+1]
    
    if X[Xi]==X[Xii]:
        if Y[Xi]>Y[Xii] and U[Xi] == "D" and U[Xii] == "U":
            ans.append((Y[Xi]-Y[Xii])*10//2)
        elif Y[Xi]<Y[Xii] and U[Xi] == "U" and U[Xii] == "D":
            ans.append((Y[Xii]-Y[Xi])*10//2)
    
    if Y[Yi]==Y[Yii]:
        if X[Yi]>X[Yii] and U[Yi] == "L" and U[Yii] == "R":
            ans.append((X[Yi]-X[Yii])*10//2)
        elif X[Yi]<X[Yii] and U[Yi] == "R" and U[Yii] == "L":
            ans.append((X[Yii]-X[Yi])*10//2)

    if X_minus_Y[XmYi]==X_minus_Y[XmYii]:
        if X[XmYi]>X[XmYii]:
            if U[XmYi] == "D" and U[XmYii] == "R":
                ans.append((X[XmYi]-X[XmYii])*10)
            elif U[XmYi] == "L" and U[XmYii] == "U":
                ans.append((X[XmYi]-X[XmYii])*10)                
        elif X[XmYi]<X[XmYii]:
            if U[XmYi] == "R" and U[XmYii] == "D":
                ans.append((X[XmYi]-X[XmYii])*10*(-1))
            elif U[XmYi] == "U" and U[XmYii] == "L":
                ans.append((X[XmYi]-X[XmYii])*10*(-1))
                
    if X_plus_Y[XpYi]==X_plus_Y[XpYii]:
        if X[XpYi]>X[XpYii]:
            if U[XpYi] == "U" and U[XpYii] == "R":
                ans.append((X[XpYi]-X[XpYii])*10)
            elif U[XpYi] == "L" and U[XpYii] == "D":
                ans.append((X[XpYi]-X[XpYii])*10)                
        elif X[XpYi]<X[XpYii]:
            if U[XpYi] == "D" and U[XpYii] == "L":
                ans.append((X[XpYi]-X[XpYii])*10*(-1))
            elif U[XpYi] == "R" and U[XpYii] == "U":
                ans.append((X[XpYi]-X[XpYii])*10*(-1))
                
#XYarray = np.array([X,Y,X_minus_Y,X_plus_Y]).T
if len(ans)==0:
    final_ans = "SAFE"
else:
    final_ans = int(min(ans))


print(final_ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = [0]*N
Y = [0]*N
U = [0]*N
const = 400010
const2 = 200010
S_U = [[] for i in range(const)]
S_R = [[] for i in range(const)]
S_D = [[] for i in range(const)]
S_L = [[] for i in range(const)]

D_U = [[] for i in range(const)]
D_R = [[] for i in range(const)]
D_D = [[] for i in range(const)]
D_L = [[] for i in range(const)]

UD_U = [[] for i in range(const2)]
UD_D = [[] for i in range(const2)]
LR_L = [[] for i in range(const2)]
LR_R = [[] for i in range(const2)]

for i in range(N):
    X[i],Y[i],U[i] = input().split()
    X[i] = int(X[i])
    Y[i] = int(Y[i])
    if U[i]=="U":
        S_U[X[i]+Y[i]].append(X[i])
        D_U[X[i]-Y[i]+200000].append(X[i])
        UD_U[X[i]].append(Y[i])
    elif U[i]=="R":
        S_R[X[i]+Y[i]].append(X[i])
        D_R[X[i]-Y[i]+200000].append(X[i])
        LR_R[Y[i]].append(X[i])
    elif U[i]=="D":
        S_D[X[i]+Y[i]].append(X[i])
        D_D[X[i]-Y[i]+200000].append(X[i])
        UD_D[X[i]].append(Y[i])
    else:
        S_L[X[i]+Y[i]].append(X[i])
        D_L[X[i]-Y[i]+200000].append(X[i])
        LR_L[Y[i]].append(X[i])
        
        
import itertools

safe = 0
time = 1000000
for i in range(const2):
    if UD_U[i] != [] and UD_D[i] != []:

        for temp in list(itertools.product(UD_U[i], UD_D[i])):
            if temp[1]-temp[0]>0:
                safe += 1
                time = min(abs(temp[0]-temp[1])*5,time)

    if LR_L[i] != [] and LR_R[i] != []:

        for temp in list(itertools.product(LR_L[i], LR_R[i])):
            if temp[0]-temp[1]>0:
                safe += 1
                time = min(abs(temp[0]-temp[1])*5,time)

for i in range(const):
    if S_U[i] != [] and S_R[i] != []:

        for temp in list(itertools.product(S_U[i], S_R[i])):
            if temp[0]-temp[1]>0:
                safe += 1
                time = min(abs(temp[0]-temp[1])*10,time)
            
    if S_D[i] != [] and S_L[i] != []:

        for temp in list(itertools.product(S_D[i], S_L[i])):
            if temp[1]-temp[0]>0:
                safe += 1
                time = min(abs(temp[0]-temp[1])*10,time)
            
    if D_U[i] != [] and D_L[i] != []:

        for temp in list(itertools.product(D_U[i], D_L[i])):
            if temp[1]-temp[0]>0:
                safe += 1
                time = min(abs(temp[0]-temp[1])*10,time)
            
    if D_D[i] != [] and S_R[i] != []:

        for temp in list(itertools.product(D_D[i], S_R[i])):
            if temp[0]-temp[1]>0:
                safe += 1
                time = min(abs(temp[0]-temp[1])*10,time)

if safe == 0:
    print("SAFE")
else:
    print(time)