Problem: Along a road running in an east-west direction, there are A shrines and B temples. The i-th shrine from the west is located at a distance of s_i meters from the west end of the road, and the i-th temple from the west is located at a distance of t_i meters from the west end of the road.  Answer the following Q queries:    * Query i (1 \leq i \leq Q): If we start from a point at a distance of x_i meters from the west end of the road and freely travel along the road, what is the minimum distance that needs to be traveled in order to visit one shrine and one temple? (It is allowed to pass by more shrines and temples than required.)

Submission attempts (in order):

import numpy as np
from functools import *
import sys
sys.setrecursionlimit(100000)


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


def II():
    return int(input())

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact



def serch(x, count):
    #print("top", x, count)
            

    for d in directions:
        nx = d+x
        #print(nx)
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1 
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)  
                continue
            if field[nx[0]][nx[1]] == "#":
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)    
                 
    return count

a,b,q=acinput()

S=[]
for i in range(a):
    S.append(II())

T=[]
for i in range(b):
    T.append(II())

X=[II() for i in range(q)]

import bisect

for i in range(q):
    x=X[i]

    t=bisect.bisect(S,x)
    t=min(t,a-1)
    d1=abs(S[t]-x)
    t2=bisect.bisect(T,S[t])
    t2=min(t2,b-1)
    d2=abs(T[t2]-S[t])

    res=d1+d2

    t = bisect.bisect(T, x)
    t = min(t, b-1)
    d1 = abs(T[t]-x)
    t2 = bisect.bisect(S,T[t])
    t2 = min(t2, a-1)
    d2 = abs(S[t2]-T[t])
    res=min(res,d1+d2)
    print(res)









import numpy as np
from functools import *
import sys
sys.setrecursionlimit(100000)


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


def II():
    return int(input())

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact



def serch(x, count):
    #print("top", x, count)
            

    for d in directions:
        nx = d+x
        #print(nx)
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1 
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)  
                continue
            if field[nx[0]][nx[1]] == "#":
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)    
                 
    return count

a,b,q=acinput()

S=[]
for i in range(a):
    S.append(II())

T=[]
for i in range(b):
    T.append(II())



import bisect

for i in range(q):
    x=II()

    t=bisect.bisect(S,x)
    t=min(t,a-1)
    d1=abs(S[t]-x)
    t2=bisect.bisect(T,S[t])
    t2=min(t2,b-1)
    d2=abs(T[t2]-S[t])

    res=d1+d2

    t = bisect.bisect(T, x)
    t = min(t, b-1)
    d1 = abs(T[t]-x)
    t2 = bisect.bisect(S,T[t])
    t2 = min(t2, a-1)
    d2 = abs(S[t2]-T[t])
    res=min(res,d1+d2)
    print(res)









import numpy as np
from functools import *
import sys
sys.setrecursionlimit(100000)


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


def II():
    return int(input())

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact



def serch(x, count):
    #print("top", x, count)
            

    for d in directions:
        nx = d+x
        #print(nx)
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1 
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)  
                continue
            if field[nx[0]][nx[1]] == "#":
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)    
                 
    return count

a,b,q=acinput()

S=[]
for i in range(a):
    S.append(II())

T=[]
for i in range(b):
    T.append(II())

X=[II() for i in range(q)]

import bisect


def near(arr,v):
    t=bisect.bisect(arr,v)

    
    if t>=len(arr)-1:
        return len(arr)-1
    if t==0:
        return 0
    #print(t)
    t-=1
    m = (abs(arr[t]-v) > abs(arr[t+1]-v))
    res = t+m
   #print(arr, v, res,m)
    return res



for i in range(q):
    x=X[i]

    s=near(S,x)
    t=near(T,S[s])
    res1=abs(S[s]-x)+abs(T[t]-S[s])

    t = near(T, x)
    s = near(S, T[t])
    res2 = abs(T[t]-x)+abs(T[t]-S[s])

    print(min(res1,res2))





import numpy as np
from functools import *
import sys
sys.setrecursionlimit(100000)


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


def II():
    return int(input())

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact



def serch(x, count):
    #print("top", x, count)
            

    for d in directions:
        nx = d+x
        #print(nx)
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1 
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)  
                continue
            if field[nx[0]][nx[1]] == "#":
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)    
                 
    return count

a,b,q=acinput()

S=[]
for i in range(a):
    S.append(II())

T=[]
for i in range(b):
    T.append(II())

X=[II() for i in range(q)]

import bisect


def near(arr,v):
    t=bisect.bisect_right(arr,v)

    #print(arr,t,v)
    if t==len(arr):
        return len(arr)-1
    t-=1
    t=max(t,0)
    return t+(abs(arr[t]-v)<abs(arr[t]-v))



for i in range(q):
    x=X[i]

    s=near(S,x)
    t=near(T,S[s])
    res1=abs(S[s]-x)+abs(T[t]-S[s])

    t = near(T, x)
    s = near(S, T[t])
    res2 = abs(T[t]-x)+abs(T[t]-S[s])

    print(min(res1,res2))





import numpy as np
from functools import *
import sys
sys.setrecursionlimit(100000)


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


def II():
    return int(input())

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact


a,b,q=acinput()

S=[-10**15]
for i in range(a):
    S.append(II())
S.append(10**15)

T=[-10**15]
for i in range(b):
    T.append(II())
T.append(10**15)
X=[II() for i in range(q)]

import bisect


def near(arr,v):
    t=bisect.bisect(arr,v)
    
    #print(arr,v,t)
    if t>len(arr)-1:
        return len(arr)-1
    if t==0:
        return 0

    m = (abs(arr[t-1]-v) > abs(arr[t]-v))
    res = t+m-1
    #print(arr, v, res,m)
    return res


#print(S)
for i in range(q):
    x=X[i]

    s=bisect.bisect_right(S,x)
    t = bisect.bisect_right(T, x)
    res=10**19
    for ss in [S[s-1],S[s]]:
        for tt in [T[t-1],T[t]]:
            tmp=abs(ss-x)+abs(ss-tt)            
            res=min(res,tmp)
            tmp = abs(tt-x)+abs(ss-tt)
            res = min(res, tmp)
    print(res)




Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Accepted