toxic_hack's blog

By toxic_hack, history, 2 months 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

»
2 months 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).

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone?

»
2 months 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).