Problem:


Score : 400 points

Problem Statement

There are N squares arranged in a row, numbered 1, 2, ..., N from left to right.
You are given a string S of length N consisting of . and #. If the i-th character of S is #, Square i contains a rock; if the i-th character of S is ., Square i is empty.

In the beginning, Snuke stands on Square A, and Fnuke stands on Square B.

You can repeat the following operation any number of times:

Choose Snuke or Fnuke, and make him jump one or two squares to the right. The destination must be one of the squares, and it must not contain a rock or the other person.

You want to repeat this operation so that Snuke will stand on Square C and Fnuke will stand on Square D.

Determine whether this is possible.

Constraints

4 \leq N \leq 200\ 000

S is a string of length N consisting of . and #.

1 \leq A, B, C, D \leq N

Square A, B, C and D do not contain a rock.

A, B, C and D are all different.

A < B

A < C

B < D

Input

Input is given from Standard Input in the following format:

N A B C D
S

Output

Print Yes if the objective is achievable, and No if it is not.

Sample Input 1

7 1 3 6 7
.#..#..

Sample Output 1

Yes

The objective is achievable by, for example, moving the two persons as follows. (A and B represent Snuke and Fnuke, respectively.)

A#B.#..

A#.B#..

.#AB#..

.#A.#B.

.#.A#B.

.#.A#.B

.#..#AB

Sample Input 2

7 1 3 7 6
.#..#..

Sample Output 2

No

Sample Input 3

15 1 3 15 13
...#.#...#.#...

Sample Output 3

Yes



Sample input:
7 1 3 6 7
.#..#..


Sample output:
Yes

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
W, A, B, C, D = map(int, input().split())
if C > D:
    tmp = D
    D = C
    C = tmp
    tmp = A
    A = B
    B = tmp
S = [i for i in input()]
def dfs(x, y, field):
    if C-1 == x and D-1 == y:
        return True
    for idx, n in enumerate([1,2,1,2]):
        if idx <= 1:
            n += x
            if n < W:
                if n == y:
                    continue
                elif field[n] == "#":
                    continue
                if dfs(n, y, field):
                    return True
        else:
            n += y
            if n < W:
                if n == x:
                    continue
                elif field[n] == "#":
                    continue
                if dfs(x, n, field):
                    return True
    return False

if dfs(A-1,B-1,S):
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
N,A,B,C,D=map(int,input().split())
S=input()

def candi_check(a,b):
    can=[]
    if (S[a-1+1]=='.') or (a+1!=b):
        can.append('a1')
    if (S[a-1+2]=='.') or (a+2!=b):
        can.append('a2')
    if (S[b-1+1]=='.') or (b+1!=a):
        can.append('b1')
    if (S[b-1+2]=='.') or (b+2!=a):
        can.append('b2')
    can.append('_')
    return(can)

def move_smirate(move,a,b):
    if move=='_':
        a=A_before.pop(-1)
        b=B_before.pop(-1)
    if move=='a1':
        a+=1
    elif move=='a2':
        a+=2
    elif move=='b1':
        b+=1
    else:
        b+=2
    return (a,b)

import copy

state="still"
ans='No'
move_queue=[]
S=S+'__'
move_queue.extend(candi_check(A,B))
A_before=[A]
B_before=[B]

while len(move_queue)!=0:
    #print(A,B)
    #print(move_queue)
    move=move_queue.pop(0)
    new_A,new_B=move_smirate(move,A,B)
    if new_A==C and new_B==D:
        ans='Yes'
        break
    if new_A>C or new_B>D or S[new_A-1]=='#' or S[new_B-1]=='#' or new_A==B or new_B==A:
        continue
    else:
        move_queue=(candi_check(new_A,new_B))+(move_queue)
        A_before.append(A)
        B_before.append(B)
        A=copy.copy(new_A)
        B=copy.copy(new_B)
        #print("add!!!")
        #print(move_queue)
        #print(A_before)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
W, A, B, C, D = map(int, input().split())
S = [i for i in input()]
def dfs(x, y, field):
    if C-1 == x and D-1 == y:
        return True
    for idx, n in enumerate([1,2,1,2]):
        if idx <= 1:
            n += x
            if n < W:
                if n == y:
                    continue
                elif field[n] == "#":
                    continue
                if dfs(n, y, field):
                    return True
        else:
            n += y
            if n < W:
                if n == x:
                    continue
                elif field[n] == "#":
                    continue
                if dfs(x, n, field):
                    return True
    return False

if dfs(A-1,B-1,S):
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n, a, b, c, d = map(int, input().split())
s = list(input())
visited1 = [False] * (n+1)
visited2 = [visited1] * (n+1)
visited2[a][b] = True
space_list = [False] * (n+3)
for i in range(n):
    if s[i] == '.':
        space_list[i+1] = True
# print(space_list)

# q = queue.Queue()
# q.put([a,b])
q = deque()
q.append([a,b])
is_possible = False
while len(q) > 0:
    current_q = q.popleft()
    pos_a = current_q[0]
    pos_b = current_q[1]
    if pos_a == c and pos_b == d:
        is_possible = True
        break
    if space_list[pos_a+2] and (pos_a+2 != pos_b) and pos_a+2 <= c:
        if not visited2[pos_a+2][pos_b]:
            q.append([pos_a+2, pos_b])
    if space_list[pos_a+1] and (pos_a+1 != pos_b) and pos_a+1 <= c:
        if not visited2[pos_a+1][pos_b]:
            q.append([pos_a+1, pos_b])
    if space_list[pos_b+2] and (pos_b+2 != pos_a) and pos_b+2 <= d:
        if not visited2[pos_a][pos_b+2]:
            q.append([pos_a, pos_b+2])
    if space_list[pos_b+1] and (pos_b+1 != pos_a) and pos_b+1 <= d:
        if not visited2[pos_a][pos_b+1]:
            q.append([pos_a, pos_b+1])
    

if is_possible:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
import queue
n, a, b, c, d = map(int, input().split())
s = list(input())
visited1 = [False] * (n+1)
visited2 = [visited1] * (n+1)
visited2[a][b] = True
space_list = [False] * (n+3)
for i in range(n):
    if s[i] == '.':
        space_list[i+1] = True
# print(space_list)

# q = queue.Queue()
# q.put([a,b])
q = []
q.append([a,b])
is_possible = False
while len(q) > 0:
    current_q = q.pop()
    pos_a = current_q[0]
    pos_b = current_q[1]
    if pos_a == c and pos_b == d:
        is_possible = True
        break
    if space_list[pos_a+2] and (pos_a+2 != pos_b) and pos_a+2 <= c:
        if not visited2[pos_a+2][pos_b]:
            q.append([pos_a+2, pos_b])
    if space_list[pos_a+1] and (pos_a+1 != pos_b) and pos_a+1 <= c:
        if not visited2[pos_a+1][pos_b]:
            q.append([pos_a+1, pos_b])
    if space_list[pos_b+2] and (pos_b+2 != pos_a) and pos_b+2 <= d:
        if not visited2[pos_a][pos_b+2]:
            q.append([pos_a, pos_b+2])
    if space_list[pos_b+1] and (pos_b+1 != pos_a) and pos_b+1 <= d:
        if not visited2[pos_a][pos_b+1]:
            q.append([pos_a, pos_b+1])
    

if is_possible:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N,A,B,C,D=(int(x) for x in input().split())
S=list(input())
sa=A-1
sb=B-1
ag=C-1
bg=D-1

if len(S)==200000:
    print('No')
else:
    count=0
    stack=deque([[sa,sb]])
    while stack:
        a,b=stack.pop()
        if a==ag and b==bg:
            count=1
            break
        for idoua,idoub in([1,0],[2,0],[0,1],[0,2]):
            na=a+idoua
            nb=b+idoub
            if na>ag or nb>bg:
                continue
            elif S[na]=='#' or S[nb]=='#' or na==nb:
                continue


            else:
                stack.append([na,nb])
    if count==1:
        print('Yes')
    else:
        print('No')

Submission status: Time Limit Exceeded

Solution code:
import copy
N,A,B,C,D = map(int,input().split())
S = input()
S = S[:A-1] + "A" + S[A:]
S = S[:B-1] + "B" + S[B:]
S_copy = copy.deepcopy(S)

def kenken(x,y,z,t):
    global S
    if t==0:
        while (S[x] == "." or S[x+1] == "."):
            if y-x<=1:
                S = S[:x-1] + "." + S[x:]
                S = S[:y-1] + z + S[y:]
                x=x+1
                return 1
            else:
                if S[x] == ".":
                    S = S[:x-1] + "." + S[x:]
                    S = S[:x] + z + S[x+1:]
                    x=x+1
                elif S[x+1] == ".":
                    S = S[:x-1] + "." + S[x:]
                    S = S[:x+1] + z + S[x+2:]
                    x=x+2
            if x == y:
                return 1
        else:
            return 0
    elif t==1:
        while (S[x] == "." or S[x+1] == "."):
            if y-x<=1:
                S = S[:x-1] + "." + S[x:]
                S = S[:y-1] + z + S[y:]
                x=x+1
                return 1
            else:
                if S[x] == ".":
                    S = S[:x-1] + "." + S[x:]
                    S = S[:x] + z + S[x+1:]
                    x=x+1
                elif S[x+1] == ".":
                    S = S[:x-1] + "." + S[x:]
                    S = S[:x+1] + z + S[x+2:]
                    x=x+2
            if (S[x-2] == "." and S[x] == "."):
                return 1
            elif x == y:
                return 0


ans=1
ans*=kenken(B,D,"B",0)
ans*=kenken(A,C,"A",0)
if ans:
    print("Yes")
else:
    S = S_copy
    ans=1
    ans*=kenken(A,C,"A",0)
    ans*=kenken(B,D,"B",0)
    if ans:
        print("Yes")
    else:
        if A < B and C > D:
            S = S_copy
            ans=1
            ans*=kenken(B,D,"B",1)
            ans*=kenken(A,C,"A",0)
            if ans:
                print("Yes")
            else:
                print("No")
        elif B<A and D>C:
            S = S_copy
            ans=1
            ans*=kenken(A,C,"A",1)
            ans*=kenken(B,D,"B",0)
            if ans:
                print("Yes")
            else:
                print("No")

Submission status: Time Limit Exceeded

Solution code:
import queue
n, a, b, c, d = map(int, input().split())
s = list(input())
space_list = [False] * (n+3)
for i in range(n):
    if s[i] == '.':
        space_list[i+1] = True
# print(space_list)

# q = queue.Queue()
# q.put([a,b])
q = []
q.append([a,b])
is_possible = False
max_a = 0
max_b = 0
while len(q) > 0:
    current_q = q.pop()
    pos_a = current_q[0]
    pos_b = current_q[1]
    if pos_a == c and pos_b == d:
        is_possible = True
        break
    if space_list[pos_a+2] and (pos_a+2 != pos_b) and pos_a+2 <= c:
        q.append([pos_a+2, pos_b])
    if space_list[pos_a+1] and (pos_a+1 != pos_b) and pos_a+1 <= c:
        q.append([pos_a+1, pos_b])
    if space_list[pos_b+2] and (pos_b+2 != pos_a) and pos_b+2 <= d:
        q.append([pos_a, pos_b+2])
    if space_list[pos_b+1] and (pos_b+1 != pos_a) and pos_b+1 <= d:
        q.append([pos_a, pos_b+1])
    

if is_possible:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, A, B, C, D = map(int, input().split(' '))
S = input()
blocks = [i+1 for i, s in enumerate([s for s in S]) if s == '#']
flag = False
check_set = set()

que = deque([(A, B)])
while que:
    A, B = que.pop()
    check_set.add((A, B))
    if A == C and B == D:
        flag = True
        break
    for i in range(3):
        for j in range(3):
            if i == j == 0:
                continue
            if A+i <= C and B+j <= D and A+i != B+j and (A+i) not in blocks and (B+j) not in blocks:
                if (A+i, B+j) not in check_set:
                    que.append((A+i, B+j))

if flag:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
def isRock(i):
  global n, a, b, s
  return True if (i > n) or (i == a) or (i == b) or (s[i-1] == "#") else False


def check():
  global a, b, c, d, s
  
  if c > d:
    while (a < b):
      if not isRock(a+1):
        a += 1
      elif not isRock(a+2):
        a += 2
      elif not isRock(b+1):
        b += 1
      elif not isRock(b+2):
        b += 2
      else:
        print("No")
        return
  
    while a < c:
      if not isRock(a+1):
        a += 1
      elif not isRock(a+2):
        a += 2
  
    if a != c:
      print("No")
      return
    
    while b < d:
      if not isRock(b+1):
        b += 1
      elif not isRock(b+2):
        b += 2
        
    if b == d:
      print("Yes")
    else:
      print("No")
            
  else:
    while b < d:
      if not isRock(b+1):
        b += 1
      elif not isRock(b+2):
        b += 2
            
    if b != d:
      print("No")
      return
    
    while a < c:
      if not isRock(a+1):
        a += 1
      elif not isRock(a+2):
        a += 2
        
    if a == c:
      print("Yes")
    else:
      print("No")
    
  return

n, a, b, c, d = map(int, input().split(" "))
s = input()

check()

Submission status: Time Limit Exceeded

Solution code:
N, A, B, C, D = [int(i) - 1 for i in input().strip().split(' ')]
N += 1
S = [c for c in input().strip()]


def get(a, b):
  s = S[:]
  s[a] = 'A'
  s[b] = 'B'

  return s


def is_reachable(s, a, b):
  i = a
  while i < C:
    if i + 1 <= C and s[i + 1] == '.':
      i = i + 1
    elif i + 2 <= C and s[i + 2] == '.':
      i = i + 2
    else:
      break
  is_a = i == C

  i = b
  while i < D:
    if i + 1 <= D and s[i + 1] == '.':
      i = i + 1
    elif i + 2 <= D and s[i + 2] == '.':
      i = i + 2
    else:
      break
  is_b = i == D

  return is_a, is_b


def move(s, i):
  if i + 1 < N and s[i + 1] == '.':
    return i + 1
  if i + 2 < N and s[i + 2] == '.':
    return i + 2

  return -1


def main():
  a = A
  b = B

  for _ in range(1000):
    s = get(a, b)
    is_a, is_b = is_reachable(s, a, b)
    #print(_, (is_a, is_b), s)
    if is_a and is_b:
      return True
    elif not is_a:
      b = move(s, b)
      if b < 0:
        return False
    elif not is_b:
      a = move(s, a)
      if a < 0:
        return False
    else:
      return False


print('Yes' if main() else 'No')

Submission status: Time Limit Exceeded

Solution code:
N, A, B, C, D = [int(c) for c in input().split()]
S = input() + '##'

r2 = set()
r1 = {B-1}

for i, c in enumerate(S):
    if c=='.' and (i-2 in r1 or i-1 in r1):
        r1.add(i)

for x in range(A-1, C):
    if S[x]=='#' : r0 = set()
    else:
        r0=r1|r2
        r0.discard(x)
        if S[x-1]=='.' and (x-2 in r0 or x-3 in r0):
            r0.add(x-1)
        if S[x-2]=='.' and (x-3 in r0 or x-4 in r0):
            r0.add(x-2)
                
    r2=r1
    r1=r0

out = 'Yes' if D-1 in r0 else 'No'
print(out)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, A, B, C, D = map(int, input().split(' '))
S = input()
blocks = [i+1 for i, s in enumerate([s for s in S]) if s == '#']
flag = False

que = deque([(A, B)])
while que:
    A, B = que.pop()
    if A == C and B == D:
        flag = True
        break
    for i in range(3):
        for j in range(3):
            if i == j == 0:
                continue
            if A+i <= C and B+j <= D and A+i != B+j and (A+i) not in blocks and (B+j) not in blocks:
                que.append((A+i, B+j))

if flag:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N,A,B,C,D=(int(x) for x in input().split())
S=list(input())
sa=A-1
sb=B-1
ag=C-1
bg=D-1

count=0
stack=deque([[sa,sb]])
while stack:
    a,b=stack.pop()
    if a==ag and b==bg:
        count=1
        break
    for idoua,idoub in([1,0],[2,0],[0,1],[0,2]):
        na=a+idoua
        nb=b+idoub
        if na>ag or nb>bg:
            continue
        elif S[na]=='#' or S[nb]=='#' or na==nb:
            continue
        elif ([na,nb] in stack)==True:
            continue
        else:
            stack.append([na,nb])
if count==1:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
N,A,B,C,D =map(int,input().split())
S=input()

from queue import Queue
q= Queue()

q.put([(A,B)])
move=[[1,0],[2,0],[0,1],[0,2]]

while not q.empty():
    pos = q.get()
    valid_pos=[]
    for p in pos:
        for m in move:

            su_x,hu_x=p[0]+m[0],p[1]+m[1]
            if su_x==C and hu_x==D:
                print('Yes')
                exit()
            if su_x<=len(S) and hu_x<=len(S):
                if S[su_x-1]=='.' and S[hu_x-1]=='.' and su_x!=hu_x:
                    valid_pos.append((su_x,hu_x))
    if len(valid_pos) !=0:
        q.put(valid_pos)
print('No')

Submission status: Time Limit Exceeded

Solution code:
N, A, B, C, D = map(int, input().split())
x = str(input())
flag = 0
rock = []
for i in range(N):
    if x[i] == "#":
        rock.append(i+1)

while True:
    if B+1 not in rock:
        B = B+1

    if B+2 not in rock:
        B = B+2

    if B == D:
        flag += 1

    if A+1 not in rock:
        A = A+1

    if A+2 not in rock:
        A = A+2

    if A == C:
        flag += 1

if flag == 2:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

N, A, B, C, D = mi()
#S[0~N-1]でアクセス
cells = input()

if C > D:
  c = C
  C = D
  D = c
  a = A
  A = B
  B = a

#全部0~N-1ベースにする
A -= 1
B -= 1
C -= 1
D -= 1

#既にスタック済みの座標の組(visited[0~N-1][0~N-1]でアクセス)
visited = [[0]*N for _ in range(N)]

st = []
#初期座標
st.append((A,B))

#結果が出るまでループする
#スタックから座標の組を取り出し、F>Sの優先順位で動かしてスタックに入れる

while 1:
  #選択肢がなくなったら、駄目だったと分かる
  try:
    s, f = st.pop()
  except:
    print('No')
    exit()

  #ここがゴールかどうか
  if s==C and f==D:
    print('Yes')
    exit()
  #Fが動けるかどうか
  fok = 0
  try:
    if visited[s][f+1]==0 and cells[f+1]=='.' and s != f+1:
      st.append((s,f+1))
      visited[s][f+1] = 1
      fok = 1
      continue
  except:
    pass
  try:
    if visited[s][f+2]==0 and cells[f+2]=='.' and s != f+2:
      st.append((s,f+2))
      visited[s][f+2] = 1
      fok = 1
  except:
    pass
  #Fが動けなかった場合のみSが動く
  if fok == 0:
    try:
      if visited[s+2][f]==0 and cells[s+2]=='.' and s+2 != f:
        st.append((s+2,f))
        visited[s+2][f] = 1
        fok = 1
    except:
      pass
    try:
      if visited[s+1][f]==0 and cells[s+1]=='.' and s+1 != f:
        st.append((s+1,f))
        visited[s+1][f] = 1
        fok = 1
    except:
      pass

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N,A,B,C,D=(int(x) for x in input().split())
S=list(input())
sa=A-1
sb=B-1
ag=C-1
bg=D-1

for q in range(N):
    if S[sa+q]=='.':
        if S[sa+q+1]=='.':
            S.pop(sa+q+1)
            sb=sb-1
            ag=ag-1
            bg=bg-1
    if sa+q>=sb-1:
        break
if ag<bg-1:
    for q in range(N):
        if S[ag+q]=='.':
            if S[ag+q+1]=='.':
                S.pop(ag+q+1)
                bg=bg-1
        if ag+q>=bg-2:
            break
if bg<ag-1:
    for q in range(N):
        if S[bg+q]=='.':
            if S[bg+q+1]=='.':
                S.pop(bg+q+1)
                ag=ag-1
        if bg+q>=ag-2:
            break
count=0
stack=deque([[sa,sb]])
while stack:
    a,b=stack.pop()
    if a==ag and b==bg:
        count=1
        break
    for idoua,idoub in([1,0],[2,0],[0,1],[0,2]):
        na=a+idoua
        nb=b+idoub
        if na>ag or nb>bg:
            continue
        elif S[na]=='#' or S[nb]=='#' or na==nb:
            continue
        else:
            stack.append([na,nb])
if count==1:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
import queue
n, a, b, c, d = map(int, input().split())
s = list(input())
space_list = [False] * (n+3)
for i in range(n):
    if s[i] == '.':
        space_list[i+1] = True
# print(space_list)

# q = queue.Queue()
# q.put([a,b])
q = []
q.append([a,b])
is_possible = False
while len(q) > 0:
    current_q = q.pop()
    pos_a = current_q[0]
    pos_b = current_q[1]
    if pos_a == c and pos_b == d:
        is_possible = True
        break
    if space_list[pos_a+2] and (pos_a+2 != pos_b) and pos_a+2 <= c:
        q.append([pos_a+2, pos_b])
    if space_list[pos_a+1] and (pos_a+1 != pos_b) and pos_a+1 <= c:
        q.append([pos_a+1, pos_b])
    if space_list[pos_b+2] and (pos_b+2 != pos_a) and pos_b+2 <= d:
        q.append([pos_a, pos_b+2])
    if space_list[pos_b+1] and (pos_b+1 != pos_a) and pos_b+1 <= d:
        q.append([pos_a, pos_b+1])
    

if is_possible:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
n,a,b,c,d = map(int,input().split())

m = list(input())

m[a-1] = "A"
m[b-1] = "B"

b_list = []
i = 0
while True:
    if b+i < n:
        if m[b+i] == ".":
            m[b-1+i],m[b+i] = m[b+i],m[b-1+i]
            b_list.append(m.index("B"))
            i += 1
        if b+1+i<n:
            if m[b+1+i] == ".":
                m[b-1+i],m[b+1+i] = m[b+1+i],m[b-1+i]
                b_list.append(m.index("B"))
                i += 2
        else:
            break
    else:
        break
        
a_list = []

i = 0
while True:
    if a+i < n:
        if m[a+i] == ".":
            m[a-1+i],m[a+i] = m[a+i],m[a-1+i]
            a_list.append(m.index("A"))
            i += 1
        if a+1+i<n:
            if m[a+1+i] == ".":
                m[a-1+i],m[a+1+i] = m[a+1+i],m[a-1+i]
                a_list.append(m.index("A"))
                i += 2
        else:
            break
    else:
        break
count = 0
for al in a_list:
    if al == c-1:
        count += 1
for bl in b_list:
    if bl == d-1:
        count += 1
if count == 2:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
input = sys.stdin.readline
 
# bisect_left(lists, 3)
# bisect_right(lists, 3)

# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

def main():
	N, A, B, C, D = map(int, input().split(" "))
	#N = int(input())
	S = input()
	S = list(S)
	S = S[:-1]

	A -= 1
	B -= 1
	C -= 1
	D -= 1

	if A > C or B > D:
		print("No")
		sys.exit()

	iwa = []
	kara = []
	for i, val in enumerate(S):
		if val == "#":
			iwa.append(i)
		else:
			kara.append(i)

	for i in range(A+1, C):
		if i in iwa:
			tmp = iwa.index(i)
			if len(iwa)-1 > tmp and iwa[tmp+1] == i+1:
				print("No")
				sys.exit()

	for i in range(B+1, D):
		if i in iwa:
			tmp = iwa.index(i)
			if len(iwa)-1 > tmp and iwa[tmp+1] == i+1:
				print("No")
				sys.exit()

	if A < B and B < C and C < D:
		print("Yes")
		sys.exit()
	elif B < A and A < D and D < C:
		print("Yes")
		sys.exit()
	elif A < B and B < D and D < C:
		for i in range(A+1, C):
			if i in kara:
				tmp = kara.index(i)
				if C >= i+2 and len(kara)-2 > tmp :
					if (kara[tmp+1] == i+1) and (kara[tmp+2] == i+2):
						print("Yes")
						sys.exit()
		print("No")
		sys.exit()
	elif B < A and A < C and C < D:
		for i in range(B+1, D):
			if i in kara:
				tmp = kara.index(i)
				if D >= i+2 and len(kara)-2 > tmp :
					if (kara[tmp+1] == i+1) and (kara[tmp+2] == i+2):
						print("Yes")
						sys.exit()
		print("No")
		sys.exit()

	print("Yes")
	

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

N, A, B, C, D = mi()
#S[0~N-1]でアクセス
cells = input()

if C > D:
  c = C
  C = D
  D = c
  a = A
  A = B
  B = a

#全部0~N-1ベースにする
A -= 1
B -= 1
C -= 1
D -= 1

#既にスタック済みの座標の組(visited[0~N-1][0~N-1]でアクセス)
visited = [[0]*N for _ in range(N)]

st = []
#初期座標
st.append((A,B))

#結果が出るまでループする
#スタックから座標の組を取り出し、F>Sの優先順位で動かしてスタックに入れる

while 1:
  #選択肢がなくなったら、駄目だったと分かる
  try:
    s, f = st.pop()
  except:
    print('No')
    exit()

  #ここがゴールかどうか
  if s==C and f==D:
    print('Yes')
    exit()
  #Fが動けるかどうか
  fok = 0
  try:
    if visited[s][f+2]==0 and cells[f+2]=='.' and s != f+2:
      st.append((s,f+2))
      visited[s][f+2] = 1
      fok = 1
  except:
    pass
  try:
    if visited[s][f+1]==0 and cells[f+1]=='.' and s != f+1:
      st.append((s,f+1))
      visited[s][f+1] = 1
      fok = 1
  except:
    pass
  #Fが動けなかった場合のみSが動く
  if fok == 0:
    try:
      if visited[s+2][f]==0 and cells[s+2]=='.' and s+2 != f:
        st.append((s+2,f))
        visited[s+2][f] = 1
        fok = 1
    except:
      pass
    try:
      if visited[s+1][f]==0 and cells[s+1]=='.' and s+1 != f:
        st.append((s+1,f))
        visited[s+1][f] = 1
        fok = 1
    except:
      pass

Submission status: Time Limit Exceeded

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

N, A, B, C, D = mi()
#S[0~N-1]でアクセス
cells = input()

if C > D:
  c = C
  C = D
  D = c
  a = A
  A = B
  B = a

#全部0~N-1ベースにする
A -= 1
B -= 1
C -= 1
D -= 1

#既にスタック済みの座標の組(visited[0~N-1][0~N-1]でアクセス)
visited = [[0]*N for _ in range(N)]

from collections import deque
st = deque(maxlen=10000)
#初期座標
st.append((A,B))

#結果が出るまでループする
#スタックから座標の組を取り出し、F>Sの優先順位で動かしてスタックに入れる
num = 0
while num < 10000:
  num += 1
  #選択肢がなくなったら、駄目だったと分かる
  try:
    s, f = st.popleft()
  except:
    print('No')
    exit()

  #ここがゴールかどうか
  if s==C and f==D:
    print('Yes')
    exit()
  #Fが動けるかどうか
  fok = 0
  try:
    if visited[s][f+2]==0 and cells[f+2]=='.' and s != f+2:
      st.append((s,f+2))
      visited[s][f+2] = 1
      fok = 1
  except:
    pass
  try:
    if visited[s][f+1]==0 and cells[f+1]=='.' and s != f+1:
      st.append((s,f+1))
      visited[s][f+1] = 1
      fok = 1
  except:
    pass
  #Fが動けなかった場合のみSが動く
  if fok == 0:
    try:
      if visited[s+2][f]==0 and cells[s+2]=='.' and s+2 != f:
        st.append((s+2,f))
        visited[s+2][f] = 1
        fok = 1
    except:
      pass
    try:
      if visited[s+1][f]==0 and cells[s+1]=='.' and s+1 != f:
        st.append((s+1,f))
        visited[s+1][f] = 1
        fok = 1
    except:
      pass

Submission status: Time Limit Exceeded

Solution code:
import queue
n, a, b, c, d = map(int, input().split())
s = list(input())
space_list = [False] * (n+3)
for i in range(n):
    if s[i] == '.':
        space_list[i+1] = True
# print(space_list)

q = queue.Queue()
q.put([a,b])
is_possible = False
while q.qsize() > 0:
    current_q = q.get()
    pos_a = current_q[0]
    pos_b = current_q[1]
    if pos_a == c and pos_b == d:
        is_possible = True
        break
    if space_list[pos_a+2] and (pos_a+2 != pos_b) and pos_a+2 <= c:
        q.put([pos_a+2, pos_b])
    if space_list[pos_a+1] and (pos_a+1 != pos_b) and pos_a+1 <= c:
        q.put([pos_a+1, pos_b])
    if space_list[pos_b+2] and (pos_b+2 != pos_a) and pos_b+2 <= d:
        q.put([pos_a, pos_b+2])
    if space_list[pos_b+1] and (pos_b+1 != pos_a) and pos_b+1 <= d:
        q.put([pos_a, pos_b+1])
    

if is_possible:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
import queue
n, a, b, c, d = map(int, input().split())
s = list(input())
space_list = [False] * (n+3)
for i in range(n):
    if s[i] == '.':
        space_list[i+1] = True
# print(space_list)

q = queue.Queue()
q.put([a,b])
is_possible = False
while q.qsize() > 0:
    current_q = q.get()
    pos_a = current_q[0]
    pos_b = current_q[1]
    if pos_a == c and pos_b == d:
        is_possible = True
        break
    if space_list[pos_a+1] and (pos_a+1 != pos_b):
        q.put([pos_a+1, pos_b])
    if space_list[pos_a+2] and (pos_a+2 != pos_b):
        q.put([pos_a+2, pos_b])
    if space_list[pos_b+1] and (pos_b+1 != pos_a):
        q.put([pos_a, pos_b+1])
    if space_list[pos_b+2] and (pos_b+2 != pos_a):
        q.put([pos_a, pos_b+2])
    

if is_possible:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
n, a, b, c, d = map(int, input().split())
s = list(input())
for i in range(b, d - 1):
    if s[i] == '#' and s[i + 1] == '#':
        print('No')
        exit(0)
    for i in range(a, c - 1):
        if s[i] == '#' and s[i + 1] == '#':
            print('No')
            exit(0)
if (a < b and c < d) or (b < a and d < c):
    print('Yes')
else:
    if a < b:
        l, r = a - 1, a
    else:
        l, r = b - 1, b
    while l >= 0 and (s[l] != '#' or s[l + 1] != '#'):
        l -= 1
    l += 2 - int(l == -1)
    while r < n and (s[r - 1] != '#' or s[r] != '#'):
        r += 1
    r -= 2 - int(r == n)
    for i in range(l, r - 1):
        if s[i] == '.' and s[i + 1] == '.' and s[i + 2] == '.':
            print('Yes')
            break
    else:
        print('No')

Submission status: Time Limit Exceeded

Solution code:
n,a,b,c,d = map(int,input().split())
S = input()

ans = 0
def aaa(s,g):
    global ans
    if S[s:g].count("##") == 0:
        ans += 1
    
def bbb(s,g):
    global ans
    if S[s:g].count("##") == 0:
        ans += 1
        return(1)
    else:
        return(0)
        
if c < d:
    aaa(b,d)
    aaa(a,c)
else:
    flag = bbb(b,d)
 #   print(ans)
    if flag == 1:
        for i in range(b,d+1):
            if S[i-1:i] != "#":
                k = S[:i-1] + "#" + S[i:]
   #             print(k,i)
                if k[a:c].count("##") == 0:
                    flag = 2
                    break
        if flag == 2:
            aaa(a,c)
#    print(flag)
  #  print(ans)

if ans == 2:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
def q1():
    _, A, B, C, D = [int(x) - 1 for x in input().split(' ')]
    S = input()
    if "##" in S[A:D + 1]:
        return False
    if C < D:
        return True
    for b in range(B, D + 1):
        if S[b] == '#':
            continue
        s = S[:b] + '#' + S[b + 1:]
        if not "##" in s[A: C + 1]:
            return True
    return False

print('Yes' if q1() else 'No')

Submission status: Time Limit Exceeded

Solution code:
N,A,B,C,D = map(int,input().split())
S = input()

def test(x,y):
  # xからyへ行ける
  x -= 1
  y -= 1
  while x < y:
    if S[x+1] == '.':
      x += 1
      continue
    if S[x+2] == '.':
      x += 2
      continue
  return (x == y)

bl = test(A,C) and test(B,D)
if C > D:
  # 追い越す必要がある
  # 道の存在は保証されているので、局所的に詰まないようにBを配置できればよい
  can_swap = False
  for b in range(B-1,D):
    if S[b] == '#':
      continue
    if S[b-1] == '.' and S[b+1] == '.':
      can_swap = True
      break
  bl = bl and can_swap
answer = 'Yes' if bl else 'No'
print(answer)

Submission status: Time Limit Exceeded

Solution code:
def valid_check(n, a, b, c, d, s):
    if not two_rocks(s[b:d]):
        return 0
    if c < d:
        return two_rocks(s[a:c])
    else:
        for possibility in enumerate_possibilities(b, d, s):
            if two_rocks(possibility[a:c]):
                return 1
        return 0



def enumerate_possibilities(b, d, s):
    possibilities = []
    for i in range(d-b+1):
        if s[b+i]=='.':
            tmp = s.copy()
            tmp[b+i] = '#'
            possibilities.append(tmp)
    return possibilities


def two_rocks(s):
    for i in range(len(s)-1):
        if s[i]=='#' and s[i+1]=='#':
            return 0
    return 1

n, a, b, c, d = map(int, input().split())
a -= 1
b -= 1
c -= 1
d -= 1
s = list(input())


if valid_check(n, a, b, c, d, s):
    print('Yes')
else:
    print('No')