Bedao PERMSORT Hay Không? Hay Hay

View as PDF

Submit solution


Points: 1.20 (partial)
Time limit: 2.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem types
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Hôm nay là ngày đầu Hiệp đến trường sau ~8~ tháng nghỉ ~30/4~. Hiệp ôm trong lòng tâm trạng vui vẻ, phấn khởi vì cuối cùng cậu cũng được gặp crush.

Thế nhưng niềm vui thì lại hay đi kèm với nỗi buồn. Crush của Hiệp là một người rất thích những câu đố. Lần này khi vừa bước vào lớp, Hiệp còn chưa được gặp mặt crush mà đã thấy một dãy số khó hiểu trên bảng.

Câu đố của crush là: Cho dãy ~N~ số nguyên ~p_1, p_2, \dots, p_n~ là một hoán vị của ~1, 2, \dots, N~. Bạn được thực hiện thao tác sau nhiều lần: chọn một dãy con (không nhất thiết liên tiếp) của ~p~ chứa không quá ~K~ phần tử và sắp xếp các phần tử trong dãy con đó tăng dần. Tuy nhiên, mỗi phần tử của ~p~ chỉ được chọn trong tối đa một thao tác. Tìm hoán vị có thứ tự từ điển nhỏ nhất có thể đạt được.

Hiệp rất muốn giải câu đố này để lấy le nhưng não Hiệp đang bị dừng mất mấy nhịp vì nụ cười tỏa nắng của crush. Bạn hãy giúp Hiệp nhé!

Input

  • Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~K~ ~(1 \le K \le N \le 2 \times 10^5)~.
  • Dòng thứ hai chứa ~N~ số nguyên dương ~p_1, p_2, \dots, p_N~ là một hoán vị của ~1, 2, \dots, N~.

Output

  • In ra trên một dòng duy nhất ~N~ số nguyên dương là hoán vị có thứ tự từ điển nhỏ nhất có thể đạt được.

Subtask

  • Subtask 1 (50% số điểm): ~N \le 3000~
  • Subtask 2 (50% số điểm): Không có ràng buộc gì thêm

Sample Input 1

5 2
4 3 2 5 1

Sample Output 1

1 2 3 5 4

Sample Input 2

10 3
5 8 2 1 7 6 9 3 10 4

Sample Output 2

1 2 3 4 6 7 9 8 10 5

Note

Trong ví dụ thứ nhất, các thao tác là:

  • Chọn dãy con chứa phần tử thứ nhất và phần tử thứ năm. Sau thao tác, ~p = [1, 3, 2, 5, 4]~.
  • Chọn dãy con chứa phần tử thứ hai và phần tử thứ ba. Sau thao tác, ~p = [1, 2, 3, 5, 4]~.

Trong ví dụ thứ hai, các thao tác là:

  • Chọn dãy con chứa các phần tử có chỉ số ~1~, ~4~ và ~10~. Sau thao tác, ~p = [1, 8, 2, 4, 7, 6, 9, 3, 10, 5]~.
  • Chọn dãy con chứa các phần tử có chỉ số ~2~, ~3~ và ~8~. Sau thao tác, ~p = [1, 2, 3, 4, 7, 6, 9, 8, 10, 5]~.
  • Chọn dãy con chứa các phần tử có chỉ số ~5~ và ~6~. Sau thao tác, ~p = [1, 2, 3, 4, 6, 7, 9, 8, 10, 5]~.

Comments

Please read the guidelines before commenting.



  • -12
    duyanh   commented on April 15, 2022, 8:35 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -14
    duyanh   commented on April 15, 2022, 8:35 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -14
    duyanh   commented on April 15, 2022, 8:35 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -12
    duyanh   commented on April 15, 2022, 8:35 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.