Problem: You are given an array A of length N. Your task is to divide it into several contiguous subarrays. Here, all subarrays obtained must be sorted in either non-decreasing or non-increasing order. At least how many subarrays do you need to divide A into?

Submission attempts (in order):
def search(v, A, B, flg, p, c, s):
  if flg[v-1] == 1:
    return c
#  print("v=", v, "flg=", flg, "p=", p, "cnt=", c)
  flg[v-1] = 1
  for idx in A:
    if v == A[idx]:
      c += 1
      if search(B[idx], A, B, flg, p, c, s) == 0:
        return 0
  for idx in B:
    if v == B[idx]:
      c += 1
      if search(A[idx], A, B, flg, p, c, s) == 0:
        return 0
#  for idx in A:
#    if v==A[idx] and flg[B[idx]-1] == 0:
#      return 0
#  for idx in B:
#    if v==B[idx] and flg[A[idx]-1] == 0:
#      return 0
  p.append(v)
  return c+1

str = input()
NM = list(map(int,str.split()))
print(NM)
ANS = 1
AB = []
C = []
A = []
B = []
for i in range(0,int(NM[1])):
  str = input()
  AB.append(list(map(int,str.split())))
  A.append(AB[i][0])
  B.append(AB[i][1])

e = 0  
#

#
for i in range(0,int(NM[1])):  
  flg = [] # Clear the flag list
  for j in range(0,int(NM[0])):
    flg.append(0)
  c = AB[i][0]  
  s = c   
  p = []

  cnt = search(c, A, B, flg, p, 0, s)
  if cnt != 0:
#    print(p)
    print(cnt)
    for i in p:
      print(i)
    break

N = input()
state = 0
max = 0
min = 0
prev = 0
len = 0
ANS = 1
S = input()
A = list(map(int,S.split()))
 
for i in range(0,int(N)):
  len = len + 1
  if state in {0}:	# Initial state
      prev = A[i]
      state = 1
  elif state in {1}: # Newtral state
    if A[i] > prev:
      state = 2
    elif A[i] < prev:
      state = 3
  elif state in {2}: # Acsending state
    if A[i] < prev:
      state = 1
      ANS = ANS + 1
      len = 0
  elif state in {3}: # Descending state
    if A[i] > prev:
      state = 1
      ANS = ANS + 1
      len = 0
  prev = A[i]
  print('s=', state, 'in=', A[i], 'prev=', prev, 'ANS=', ANS, 'len=', len)
print(ANS)

def search(v, A, B, flg, p, c, s):
  if c > 2:
    print("v=", v, "flg=", flg, "p=", p, "cnt=", c)
  if flg[v-1] == 1:
    return c
  flg[v-1] = 1
  p.append(v)
  c += 1
  for idx in range(len(A)):
    if v == A[idx]:
      cnt = search(B[idx], A, B, flg, p, c, s)
      if cnt != 0:
        return cnt
      else:
        flg[idx] = 0
        return 0
  for idx in range(len(B)):
    if v == B[idx]:
      cnt = search(A[idx], A, B, flg, p, c, s)
      if cnt != 0:
        return cnt
      else:
        flg[idx] = 0
        return 0
  return c

#
# Main Routine
#
str = input()
NM = list(map(int,str.split()))
print(NM)
ANS = 1
AB = []
C = []
A = []
B = []
for i in range(0,int(NM[1])):
  str = input()
  AB.append(list(map(int,str.split())))
  A.append(AB[i][0])
  B.append(AB[i][1])

#

#
for i in range(0,int(NM[1])):  
  flg = [] # Clear the flag list
  for j in range(0,int(NM[0])):
    flg.append(0)
  v = AB[i][0]  
  s = v   
  p = []
  cnt = search(v, A, B, flg, p, 0, s)
  for idx in range(len(A)):
    if s == A[idx] and B[idx] == 1:
      cnt = 0	# Start vertex doesn't satisfy the condition.
  for idx in range(len(B)):
    if s == B[idx] and A[idx] == 1:
      cnt = 0	# Start vertex doesn't satisfy the condition.
  if cnt != 0:
    print(cnt)	# If all the conditions are met, output the result and stop.
    print(p)
    for i in p:
      print(i)
    break

def search(v, A, B, flg, p, c, s):
#  if c > 2:
#    print("v=", v, "flg=", flg, "p=", p, "cnt=", c)
  if flg[v-1] == 1:
    return c
  flg[v-1] = 1
  p.append(v)
  c += 1
  for idx in range(len(A)):
    if v == A[idx]:
      cnt = search(B[idx], A, B, flg, p, c, s)
      if cnt != 0:
        return cnt
      else:
        flg[idx] = 0
        return 0
  for idx in range(len(B)):
    if v == B[idx]:
      cnt = search(A[idx], A, B, flg, p, c, s)
      if cnt != 0:
        return cnt
      else:
        flg[idx] = 0
        return 0
  return c

#
# Main Routine
#
str = input()
NM = list(map(int,str.split()))
#print(NM)
ANS = 1
AB = []
C = []
A = []
B = []
for i in range(0,int(NM[1])):
  str = input()
  AB.append(list(map(int,str.split())))
  A.append(AB[i][0])
  B.append(AB[i][1])

#

#
for i in range(0,int(NM[1])):  
  flg = [] # Clear the flag list
  for j in range(0,int(NM[0])):
    flg.append(0)
  v = AB[i][0]  
  s = v   
  p = []
  cnt = search(v, A, B, flg, p, 0, s)
  for idx in range(len(A)):
    if s == A[idx] and B[idx] == 1:
      cnt = 0	# Start vertex doesn't satisfy the condition.
  for idx in range(len(B)):
    if s == B[idx] and A[idx] == 1:
      cnt = 0	# Start vertex doesn't satisfy the condition.
  if cnt != 0:
    print(cnt)	# If all the conditions are met, output the result and stop.
#    print(p)
    for i in p:
      print(i)
    break

N = input()
state = 0
max = 0
min = 0
prev = 0
len = 0
ANS = 1
S = input()
A = list(map(int,S.split()))
 
for i in range(0,int(N)):
  len = len + 1
  if state in {0}:	# Initial state
      prev = A[i]
      state = 1
  elif state in {1}: # Newtral state
    if A[i] > prev:
      state = 2
    elif A[i] < prev:
      state = 3
  elif state in {2}: # Acsending state
    if A[i] < prev:
      state = 1
      ANS = ANS + 1
      len = 0
  elif state in {3}: # Descending state
    if A[i] > prev:
      state = 1
      ANS = ANS + 1
      len = 0
  prev = A[i]

print(ANS)

Verdicts: Runtime Error

Wrong Answer

Runtime Error

Runtime Error

Accepted