Sắp Xếp Từng Phần

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có $N$ con bò được đánh số từ $1$ đến $N$ , đứng thành hàng với thứ tự ban đầu $a_{1}, a_{2}, \dots, a_{N}$ (một hoán vị của $1, 2, \dots, N$ ).

Khi "gọi" một con bò, nó sẽ di chuyển bằng cách đổi chỗ với các bò kề nhau theo quy tắc sau: trước tiên nó đi sang phải cho đến khi không còn con nào nhỏ hơn nó ở bên phải; sau đó nó đi sang trái cho đến khi không còn con nào lớn hơn nó ở bên trái. Quá trình này lặp lại cho đến khi bò không di chuyển nữa.

Chọn một tập con các con bò và gọi lần lượt các bò trong tập đó theo thứ tự ID tăng dần (lặp lại nhiều lần cho đến khi tất cả bò được sắp xếp). Mục tiêu là toàn bộ hàng bò đạt thứ tự $1, 2, \dots, N$ .

Hãy tìm tập con có kích thước nhỏ nhất và trong số các tập con nhỏ nhất, in ra tập con thứ $K$ theo thứ tự từ điển nhỏ nhất (sắp xếp theo ID bò tăng dần).

Dữ liệu vào

Dòng 1: hai số nguyên $N$ và $K$ ( $1 \leq N \leq 10^{5}$ , $1 \leq K \leq 10^{18}$ )
Dòng 2: $N$ số nguyên $a_{1}, a_{2}, \dots, a_{N}$ — hoán vị ban đầu

Dữ liệu ra

Dòng 1: kích thước tập con tối thiểu $M$
$M$ dòng tiếp theo: ID các bò trong tập, mỗi dòng một ID, theo thứ tự tăng dần

Ràng buộc

$1 \leq N \leq 10^{5}$
$1 \leq K \leq 10^{18}$
Đảm bảo $K$ không vượt quá số tập con tối thiểu thực tế

Ví dụ

Input	Output	Giải thích
4 1 4 2 1 3	2 1 4	Dãy con không được chọn phải là dãy tăng. LIS của $[4, 2, 1, 3]$ có độ dài $2$ (ví dụ: $[2, 3]$ ). Tập con tối thiểu có $4 - 2 = 2$ phần tử. Tập từ điển nhỏ nhất là ${1, 4}$ (phần bù của LIS lớn từ điển nhất $[2, 3]$ ).

Bình luận

Không có bình luận tại thời điểm này.