Тоннель

Автор задачи и разработчик: Даниил Голов

Заметим, что так как обгон в тоннеле запрещен, единственное, что могло изменить порядок выезда машин из тоннеля относительно порядка въезда — это разворот одной машины. Если разворот располагается ближе ко въезду, то развернувшаяся машина может поменять свое место в порядке на ближе к началу, если ближе к выезду — то сдвинуться в порядке ближе к концу.

Сделаем из последовательности $$$a$$$ перестановку такого же формата, как последовательность $$$c$$$. Для этого можно, например, сделать из $$$a$$$ последовательность пар ($$$a_i$$$, $$$i + 1$$$) и отсортировать эту последовательность по первому элементу, а затем взять все вторые элементы. Будем называть такую получившуюся из $$$a$$$ перестановку $$$d$$$.

Посмотрим на изменения в $$$c$$$ относительно $$$d$$$. Если перестановки равны, то возможны несколько вариантов расположения разворота: разворот ближе к началу и развернулась машина, въехавшая первой; разворот ближе к концу и развернулась машина, въехавшая последней; разворот ровно посередине и развернулась любая машина. То есть в таком случае ответ «impossible». В случае, если две машины поменялись местами, тоже возможны несколько вариантов: либо та, которая переместилась в порядке вперед, развернулась, и тогда разворот ближе к началу; либо та, которая переместилась в порядке назад, развернулась, и разворот ближе к концу. Соответственно, в этом случае тоже «impossible».

В любом другом случае, так как мы знаем, что развернулась ровно одна машина, соответственно, одна машина переместится на несколько позиций вперед или назад, а остальные, которых она обогнала и от которых отстала, переместятся ровно на одну позицию назад или вперед. Таким образом, можно просто посмотреть на позицию машины, которая сдвинулась более, чем на один индекс в перестановке. Если она переместилась по порядку вперед, значит разворот был в начале, если назад — то в конце. Время работы решения — $$$\mathcal{O}(n \log n)$$$.