Help needed in BOI 2016 — Swaps.

Правка en3, от toxic_hack, 2020-03-31 10:40:42

Can someone help me in solving this question BOI16_swap.

You are given a sequence of n numbers $$$x_1, x_2, ..., x_n$$$. Each number appears exactly once in the sequence. You can modify the sequence using swaps. There are $$$n - 1$$$ consecutive turns numbered $$$k = 2, 3, 4, ... n$$$. On turn you can either swap values $$$x_k$$$ and $$$x_{k/2}$$$ in the sequence or do nothing. What is the lexicographically minimal sequence you can obtain?

Spoiler

Thanks!

Теги help, boi 2016, #solution

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский toxic_hack 2020-03-31 11:11:28 16 Tiny change: 'n obtain? \n\n<spoil' -> 'n obtain? $n \leq 2 * 1e5$\n\n<spoil'
en3 Английский toxic_hack 2020-03-31 10:40:42 379 Tiny change: 'There are n - 1 consecuti' -> 'There are $n - 1$ consecuti'
en2 Английский toxic_hack 2020-03-30 21:18:11 104
en1 Английский toxic_hack 2020-03-30 19:14:51 440 Initial revision (published)