1601B - Frog Traveler - CodeForces Solution

from collections import deque

n = int(input())
a = [0] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))


def find_path_to_zero():
    paths = {n: (n, n)}
    queue = deque([n])
    curr_min_height = n + 1
    while queue:
        height = queue.popleft()
        if height <= a[height]:
            paths[0] = (height, 0)
            path = []
            curr_node = 0
            count = 0
            while curr_node != n:
                path.append(paths[curr_node][1])
                curr_node = paths[curr_node][0]
                count += 1
            return count, path[::-1]
        for node in range(curr_min_height - 1, height - a[height] - 1, -1):
            new_height = node + b[node]
            if new_height not in paths:
                paths[new_height] = (height, node)
                queue.append(new_height)
        curr_min_height = min(curr_min_height, height - a[height])
    return -1, []

num_steps, path = find_path_to_zero()
print(num_steps)
print(*path)