Elearning CodePath – CTP Online Judge

Dãy con tăng chặt thứ k

KTHLIS

## Đề bài

Cho dãy số nguyên $A$ gồm $n$ phần tử:

$A_1, A_2, \ldots, A_n$

Một dãy con tăng chặt của dãy $A$ là một dãy chỉ số:

$i_1 < i_2 < \ldots < i_t$

sao cho:

$A_{i_1} < A_{i_2} < \ldots < A_{i_t}$

Độ dài của dãy con trên là $t$.

Gọi $L$ là độ dài lớn nhất của một dãy con tăng chặt trong dãy $A$.

Xét tất cả các dãy con tăng chặt có độ dài đúng bằng $L$. Mỗi dãy con được xác định bởi dãy chỉ số của nó. Hai dãy con được xem là khác nhau nếu tồn tại ít nhất một vị trí trong dãy chỉ số khác nhau.

Các dãy con tăng chặt độ dài $L$ được sắp xếp theo thứ tự từ điển như sau:

- Trước hết so sánh dãy giá trị tương ứng của hai dãy con.
- Dãy nào có giá trị nhỏ hơn tại vị trí khác nhau đầu tiên thì đứng trước.
- Nếu hai dãy giá trị hoàn toàn giống nhau, so sánh tiếp dãy chỉ số tương ứng theo thứ tự từ điển.

Yêu cầu: Hãy tìm dãy con tăng chặt độ dài $L$ đứng thứ $K$ trong thứ tự trên. Nếu không tồn tại dãy con thứ $K$, in ra `-1`.

## Dữ liệu vào

Dữ liệu vào từ file `KTHLIS.INP`.

| Dòng | Mô tả |
| :-- | :-- |
| 1 | Chứa hai số nguyên $n, K$ |
| 2 | Chứa $n$ số nguyên $A_1, A_2, \ldots, A_n$ |

## Dữ liệu ra

Ghi ra file `KTHLIS.OUT`.

## Ví dụ 1

| `KTHLIS.INP` | `KTHLIS.OUT` |
| :-- | :-- |
| `5 2` <br> `1 3 2 4 5` | `1 3 4 5` |

## Giải thích ví dụ 1

Các dãy con tăng chặt có độ dài lớn nhất là:

| Thứ tự | Dãy chỉ số | Dãy giá trị |
| :-- | :-- | :-- |
| 1 | $1, 3, 4, 5$ | $1, 2, 4, 5$ |
| 2 | $1, 2, 4, 5$ | $1, 3, 4, 5$ |

Dãy đứng thứ $2$ là:

$1, 3, 4, 5$

## Ví dụ 2

| `KTHLIS.INP` | `KTHLIS.OUT` |
| :-- | :-- |
| `5 2` <br> `1 2 1 2 3` | `1 2 3` |

## Giải thích ví dụ 2

Độ dài LIS là $3$.

Các dãy con tăng chặt có độ dài $3$ là:

| Thứ tự | Dãy chỉ số | Dãy giá trị |
| :-- | :-- | :-- |
| 1 | $1, 2, 5$ | $1, 2, 3$ |
| 2 | $1, 4, 5$ | $1, 2, 3$ |
| 3 | $3, 4, 5$ | $1, 2, 3$ |

Dãy đứng thứ $2$ có dãy giá trị là:

$1, 2, 3$

## Ví dụ 3

| `KTHLIS.INP` | `KTHLIS.OUT` |
| :-- | :-- |
| `4 3` <br> `4 1 2 3` | `-1` |

## Giải thích ví dụ 3

Độ dài LIS là $3$.

Chỉ có một dãy con tăng chặt có độ dài $3$ là:

$1, 2, 3$

Vì không tồn tại dãy con tăng chặt thứ $3$, kết quả là `-1`.

## Giới hạn

| Subtask | Ràng buộc | Điểm |
| :-- | :-- | :-- |
| 1 | $n \le 50$ | $30\%$ |
| 2 | $n \le 100$ | $70\%$ |

Với mọi test:

$1 \le n \le 100$

$1 \le K \le 10^{18}$

$|A_i| \le 10^9$

✅ Đã AC: 1 / 1 submissions