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 
Ouput: 
0 
20 
30 
10 
0 

Được gửi lên bởi:~!(*(@*!@^&
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
2013-10-17 18:24:16 G
thực sự thỳ mình downtest về test thử thỳ chạy không việc gì? nhưng chả hiểu sao test trên đây toàn lỗi NZEC ! chả hiểu sao nữa :-s
2013-06-18 03:34:47 PASS ? WIN : T-L-H
làm 2 cái set mà cũng lỗi =="
2013-06-06 03:45:07 a;slkfjasl;fkj
bài này biết là dùng 2 heap nhưng làm kĩ thì thấy đề xoắn kinh khủng :|

Last edit: 2013-06-25 04:38:25
2013-06-05 15:10:56 a;slkfjasl;fkj
biết được giới hạn của số truyvấn thì hay biết mấy :D
2013-04-14 14:21:15 Doraemon Grapes
2 priority queue SIGSEGV
2 set AC!!!
2012-07-18 09:23:00 the apple of my eyes
không đọc cái này của rockman thì chắc không AC nổi, đề bựa quá
2011-10-18 13:12:16 Noyethug
người K bất kì vào X lần thỳ sau khi đc phục vụ 1 lần sẽ k còn đc phục vụ cho đến khi vào lại........khá xoắn......:d
2011-06-18 09:32:09 Tâm Chớp Nhoáng
mình dùng 2 heap gặp lỗi SIGKILL hoài, chả hiểu :(
ko biết có độ ưu tiên P là số âm ko ?

Last edit: 2011-06-18 10:26:13
2011-06-04 20:16:25 Noyethug
co' bao nhieu cau truy van vay.......:-/
2010-07-02 11:22:12 [HD]
Treap :D
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.