Яндекс.Кон­тест: Задача о таксистах, которые смогут добраться до точки заказа за отведенное время

Ограничение времени: 1 секунда
Ограничение памяти: 256 Мб

Описание задачи

При вызове такси не всегда можно точно сказать, за сколько времени таксист сможет доехать до пользователя. В этой задаче необходимо разработать алгоритм, который будет определять, какие таксисты смогут гарантированно добраться до точки заказа за отведенное время, если примут его моментально.

Таксист может стоять на месте или перемещаться по кругу по часовой стрелке. На момент вызова его позиция может измениться по сравнению с последней известной — он мог двигаться с любой скоростью, вплоть до максимально разрешенной. Точка заказа и точки, в которых находятся или могут находиться таксисты, — это точки на круге. Перемещаться к заказу такси может только по часовой стрелке.

Формат ввода

В первой строке указаны три целых числа:

• N — количество событий (1 ≤ N ≤ 5000),
• L — длина круга (0 < L ≤ 100000, метры),
• S — максимальная скорость такси (0 < S ≤ 10, метры в секунду).

В следующих N строках описаны события в следующем формате:

TAXI <timestamp> <taxi_id> <taxi_position> — таксист с номером taxi_id в момент времени timestamp прислал координату своего местоположения taxi_position (0 ≤ taxi_position < L).

ORDER <timestamp> <order_id> <order_position> <order_time> — заказ с номером order_id на точку order_position (0 ≤ order_position < L), (где 0 означает, что заказ произошел в начале круга, а любое положительное число — дальность позиции вызова от начала круга при движении по часовой стрелке), до которой нужно гарантированно доехать за order_time секунд.

timestamp - это unix-like секундный таймстемп, все приходящие команды отсортированы по нему в порядке возрастания. Возрастание нестрогое: в нескольких последовательных командах могут быть одинаковые таймстемпы, но на момент события вызова мы рассматриваем только те события, которые нам известны (то есть не рассматриваем события, которые пришли после вызова, даже если у них такой же таймстемп)

Формат вывода

Для каждого события типа ORDER нужно вывести строку с таксистами (набор taxi_id, разделенных пробелами), которые гарантированно смогут добраться до точки заказа не более чем за order_time секунд. Если таких таксистов больше 5, то выведите 5 любых. Если ни один таксист не может гарантированно приехать в отведенное время, выведите строку с единственным значением -1.

IN:
3 100 1
TAXI 1738300000 0 0
TAXI 1738300000 1 2
ORDER 1738300001 0 1 1

OUT:
0

Вопрос: На каком тесте может дать неверный ответ? И как это фиксить вообще?

Мой код:

number_of_events, len_circle, speed = map(int, input().split())
taxi_dict = {}
for _ in range(number_of_events):
    command = input().split()
    if command[0] == "TAXI":
        taxi_timestamp, taxi_id, taxi_position = int(command[1]), command[2], int(command[3])
        taxi_dict[taxi_id] = (taxi_position, taxi_timestamp)
    else:
        answer = []
        order_timestamp, order_position, order_time =int(command[1]), int(command[3]), int(command[4])
        for taxi_id in taxi_dict:
            taxi_position = taxi_dict[taxi_id][0]
            taxi_timestamp = taxi_dict[taxi_id][1]
            timestamp_different = (order_timestamp - taxi_timestamp)
            new_position = (taxi_position + speed * timestamp_different) % len_circle
            d = (order_position - new_position + len_circle) % len_circle
            if new_position == order_position:
                d = order_position - taxi_position
            if d <= order_time * speed:
                answer.append(taxi_id)
        if len(answer) > 0:
            print(" ".join(answer[:5]))
        else:
            print(-1)