Buổi Phỏng Vấn Của Bessie

Đ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

Bessie đang chờ phỏng vấn xin việc. Có $K$ nông dân ( $1 \leq K \leq N$ ) đang phỏng vấn. Trước Bessie có $N$ con bò được đánh số từ 1 đến $N$ ( $1 \leq N \leq 3 \times 10^{5}$ ), Bessie là con bò thứ $N + 1$ .

Ban đầu, nông dân thứ $i$ phỏng vấn bò thứ $i$ (với $1 \leq i \leq K$ ) bắt đầu từ thời điểm 0. Thời gian phỏng vấn bò thứ $j$ là $t_{j}$ ( $1 \leq t_{j} \leq 10^{9}$ ). Khi một nông dân hoàn thành, họ phỏng vấn con bò tiếp theo trong hàng.

Nếu nhiều nông dân hoàn thành đồng thời, con bò tiếp theo trong hàng sẽ chọn nông dân ưa thích của mình (không cố định thứ tự).

Hãy xác định:

Thời điểm Bessie bắt đầu phỏng vấn
Những nông dân nào có thể phỏng vấn Bessie (tùy thuộc vào lựa chọn của các bò trước)

Dữ liệu vào

Dòng 1: Hai số nguyên $N$ và $K$
Dòng 2: $N$ số nguyên $t_{1}, t_{2}, \dots, t_{N}$

Dữ liệu ra

Dòng 1: Thời điểm Bessie bắt đầu phỏng vấn
Dòng 2: Chuỗi $K$ bit, bit thứ $i$ bằng 1 nếu nông dân $i$ có thể phỏng vấn Bessie

Ràng buộc

$1 \leq K \leq N \leq 3 \times 10^{5}$
$1 \leq t_{j} \leq 10^{9}$
Test 2-3: Không có hai nông dân nào hoàn thành đồng thời
Test 4-9: $N \leq 3000$

Ví dụ

Input	Output	Giải thích
6 3 3 1 4159 2 6 5	8 110	Nông dân 1 xong bò 1 lúc $t = 3$ , nhận bò 4. Nông dân 2 xong bò 2 lúc $t = 1$ , nhận bò 3. Nông dân 1 xong bò 4 lúc $t = 5$ , nhận bò 5. Nông dân 2 xong bò 3 lúc $t = 4160$ . Nông dân 1 xong bò 5 lúc $t = 11$ . Nông dân 3 chưa xong bò 3. Lúc $t = 5$ : nông dân 1 rảnh, nhận bò 5. Lúc $t = 5$ : cũng có thể nông dân 1 nhận bò 6. Bessie bắt đầu lúc $t = 8$ , nông dân 1 hoặc 2 có thể phỏng vấn.

Bình luận

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