Codeforces Global Round 3 |
---|
Закончено |
На числовой прямой расположены $$$n$$$ камней. Изначально $$$i$$$-й камень находится в точке с координатой $$$s_i$$$. В одной точке может находиться более одного камня одновременно.
Вы можете выполнить ноль или более операций следующего вида:
Вы хотите подвинуть камни так, чтобы они находились в позициях $$$t_1, t_2, \ldots, t_n$$$. Порядок камней не важен — требуется лишь, чтобы мультимножество координат камней в конце совпадало с мультимножеством, состоящим из $$$t_1, t_2, \ldots, t_n$$$.
Выясните, возможно ли сдвинуть камни требуемым образом, и если да, то найдите способ это сделать. Минимизировать число операций не нужно.
Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) – количество камней.
Вторая строка содержит целые числа $$$s_1, s_2, \ldots, s_n$$$ ($$$1 \le s_i \le 10^9$$$) — изначальные позиции камней.
Третья строка содержит целые числа $$$t_1, t_2, \ldots, t_n$$$ ($$$1 \le t_i \le 10^9$$$) — требуемые позиции камней.
В случае, если невозможно подвинуть камни требуемым образом, выведите «NO».
Иначе на первой строке выведите «YES», на второй строке выведите количество операций $$$m$$$ ($$$0 \le m \le 5 \cdot n$$$), которое нужно сделать. Вам не нужно минимизировать число операций.
Затем выведите $$$m$$$ строк, каждая из которых содержит три целых числа $$$i, j, d$$$ ($$$1 \le i, j \le n$$$, $$$s_i \le s_j$$$, $$$0 \leq 2 \cdot d \leq s_j - s_i$$$), обозначающие операцию, которую нужно сделать.
Можно показать, что если какой-то ответ существует, то существует и ответ, использующий не более чем $$$5 \cdot n$$$ операций.
5 2 2 7 4 9 5 4 5 5 5
YES 4 4 3 1 2 3 1 2 5 2 1 5 2
3 1 5 10 3 5 7
NO
Рассмотрим первый пример.
Название |
---|