IO - Hàng đợi với độ ưu tiên
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: nguyenxuanhaa3

HÀNG ĐỢI VỚI ĐỘ ƯU TIÊN

Cho trước một danh sách rỗng. Người ta xét hai thao tác trên danh sách đó:

  • Thao tác "+V" (ở đây V là một số tự nhiên £ 109): Nếu danh sách đang có ít hơn 15000 phần tử thì thao tác này bổ sung thêm phần tử V vào danh sách; Nếu không, thao tác này không có hiệu lực.
  • Thao tác "-": Nếu danh sách đang không rỗng thì thao tác này loại bỏ tất cả các phần tử lớn nhất của danh sách; Nếu không, thao tác này không có hiệu lực

Ví dụ: Với danh sách ban đầu là rỗng:

  • Nếu ta thực hiện liên tiếp các thao tác: +1, +3, +2, +3 ta sẽ được danh sách (1, 3, 2, 3)
  • Thực hiện thao tác -, ta sẽ được danh sách (1, 2)
  • Thực hiện hai thao tác +4, ta sẽ được danh sách (1, 2, 4, 4)
  • Thực hiện thao tác -, ta sẽ được danh sách (1, 2)
  • Tiếp tục với các thao tác +2, +9, +7, +8, ta sẽ được danh sách (1, 2, 2, 9, 7, 8)
  • Cuối cùng thực hiện thao tác -, ta còn lại danh sách (1, 2, 2, 7, 8)

 

Vấn đề đặt ra là cho trước một dãy không quá 100000 thao tác, hãy xác định những giá trị số nào còn lại trong danh sách, mỗi giá trị chỉ được liệt kê một lần.

 

Dữ liệu: 

  • Gồm nhiều dòng, mỗi dòng ghi một thao tác. Thứ tự các thao tác trên các dòng được liệt kê theo đúng thứ tự sẽ thực hiện.

 

Kết quả: 

  • Dòng 1: Ghi số lượng những giá trị còn lại trong danh sách.
  • Dòng 2: Liệt kê những giá trị đó theo giá trị giảm dần

Ví dụ

  • input
    +1
    +3
    +2
    +3
    -
    +4
    +4
    -
    +2
    +9
    +7
    +8
    -
    output
    4
    8 7 2 1
Back to Top