Bedao PERMSORT Hay Không? Hay Hay

Xem dạng PDF

Gửi bài giải


Điểm: 1,20 (OI)
Giới hạn thời gian: 2.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Tác giả:
Nguồn bài:
DMOPC '21 Contest 3 P4
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, 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]~.

Bình luận

Hãy đọc nội quy trước khi bình luận.



  • 0
    flechilavt  đã bình luận lúc 7, Tháng 2, 2024, 3:21

    ILOVYOU


  • -47
    duyanh  đã bình luận lúc 15, Tháng 4, 2022, 13:35

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -47
    duyanh  đã bình luận lúc 15, Tháng 4, 2022, 13:35

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -47
    duyanh  đã bình luận lúc 15, Tháng 4, 2022, 13:35

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -47
    duyanh  đã bình luận lúc 15, Tháng 4, 2022, 13:35

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.