MSE07B - Double Queue

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/mse07b


Ngân hàng BIG-Bank mở một chi nhánh ở Bucharest và được trang bị một máy tính hiện đại với các công nghệ mới nhập, C2#,VC3+ ... chỉ chuối mỗi cái là không ai biết lập trình.

Họ cần một phần mềm mô tả hoạt động của ngân hàng như sau: mỗi khách hàng có một mã số là số nguyên K, và khi đến ngân hàng giao dịch, họ sẽ nhận được 1 số P là thứ tự ưu tiên của họ. Các thao tác chính như sau

0 Kết thúc phục vụ

1 K P Thêm khách hàng K vào hàng đợi với độ ưu tiên P

2 Phục vụ người có độ ưu tiên cao nhất và xóa khỏi danh sách hàng đợi

3 Phục vụ người có độ ưu tiên thấp nhất và xóa khỏi danh sách hàng đợi.

Tất nhiên là họ cần bạn giúp rồi.

Input

Mỗi dòng của input là 1 yêu cầu, và chỉ yêu cầu cuối cùng mới có giá trị là 0. Giả thiết là khi có yêu cầu 1 thì không có khách hàng nào khác có độ ưu tiên là P.

K<=10^6, và P<= 10^7.Một khách hàng có thể yêu cầu phục vụ nhiều lần và với các độ ưu tiên khác nhau.

Output

Với mỗi yêu cầu 2 hoặc 3, in ra trên 1 dòng mã số của khách hàng được phục vụ tương ứng. Nếu có yêu cầu mà hàng đợi rỗng, in ra số 0.

Sample

Input :
2 
1 20 14 
1 30 3 
2 
1 10 99 
3 
2 
2 
0 

Output: 
0 
20 
30 
10 
0 

Được gửi lên bởi:psetter
Ngày:2009-04-12
Thời gian chạy:0.200s-1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Southeastern European 2007

hide comments
2021-05-27 18:02:04
Tham khảo: https://vnspoj.github.io/problems/MSE07B
2019-10-08 05:52:31
đấm bừa cx AC :))
2019-01-09 10:03:46
ôn set 1 chút
frostpixel aka.How 2 AC
2018-01-08 09:49:48 hồ vãn tuấn
lấy bộ test ở đâu nhỉ
2017-08-20 18:35:25 Con Bò Huyền Thoại
http://kienthuc24h.com/mse07b-spoj-double-queue/
2017-08-11 04:58:48
THAM KHẢO THUẬT TOÁN VÀ CODE TẠI:

http://yeulaptrinh.pw/937/mse07b-spoj/
2017-01-06 19:12:55 Lang Trat Y
Test chán quá.
Làm 2 thuật cho 2 bài toán cả 2 đều AC
1. Với yêu cầu 2 hoặc 3 thì khi phục vụ xong người nào thì hủy tất cả những yêu cầu trước đó của người đó.
2. Với yêu cầu 2 hoặc 3 thì khi phục vụ xong người nào thì chỉ hủy yêu cầu ở hiện tại.
Ví dụ: với cùng một input
VD:
[INPUT]
1 100 10
1 100 35
2
3
thì output cho bài toán 1 sẽ là
[OUTPUT]
100
0
và output của bài toán 2 sẽ là
[OUTPUT]
100
100
2016-10-11 15:10:14
Ghi nhầm truy vấn 2 thành 1, nhớ đời =)))
2016-08-12 19:13:07
C++ dùng set là AC
2016-07-26 10:21:59
Code 10 phút AC, phê vãi ~
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.