toxic_hack's blog

By toxic_hack, history, 4 years ago, In English

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? $$$n \leq 2 * 1e5$$$

Spoiler

Thanks!

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by toxic_hack (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by toxic_hack (previous revision, new revision, compare).