TopCoder

$(pr)^3pony$
https://prprprpony.github.io/blog/ $\\\huge PinkiePie:"OkieDokieLokie"$

User's AC Ratio

63.2% (60/95)

Submission's AC Ratio

35.1% (375/1069)

Tags

Description

之前之前,你已經成功地比較了兩個數字的大小。然而比較兩個數字的大小非常無聊,所以我們不妨把問題變難。接下來我們要同時考慮多個數字之間的大小關係,而我們在意的是這些數字中的最大和最小值。

具體而言,我們每次都可以做如下操作:
(1)將這些數字中的某個最大值移除
(2)將這些數字中的某個最小值移除
(3)加入一個數至這些數字
(4)詢問當前最大值
(5)詢問當前最小值

假設一開始沒有任何數字,請你實作這五個操作。

Input Format

本題沒有輸入。
#include "lib1168.h"
你需要實作五個函式:
void pop_big();
void pop_small();
void push(int s);
int big();
int small();
其中第一個函式需要將最大的數字移除,第二個函式需要將最小的數字移除,第三個函式需要將一個數加入目前的數字們,第四個函式需要回傳當前的最大值,第五個函式需要回傳當前的最小值。
在測試時保證當沒有數字的時候只會呼叫push,而且保證加入的數字$\leq 10 ^ 9$,五個函數的總呼叫次數$\leq 10 ^ 6$。評測時每筆測資只會有一組測試資料。

子任務(測資) 額外限制 分數
1 (0~4) 呼叫次數$\leq 1000$ 10
2 (5~9) 所有數字$\leq 1000$ 15
3 (10~14) 無限制 28
4 (15~19) 時限縮為300ms 47

Output Format

本題沒有輸出。

Sample Input 1

注意:本題沒有輸入,本輸入為提供測試標頭檔(參見Hints)使用。
7
3 10
3 100
3 1000
1
2
4
5

Sample Output 1

注意:本題沒有輸出,本輸出為提供測試標頭檔(參見Hints)使用。
100
100

Hints

這裡有一個測試用的標頭檔,可以用來測試。
該標頭檔接受以下輸入,數字間皆以空白分隔:
第一行有一個正整數$n$,代表函數總呼叫次數。
之後的$n$行,每行代表一次函數的呼叫。
如果是1,代表你要呼叫pop_big()
如果是2,代表你要呼叫pop_small()
如果是3 s,代表你要呼叫push(s)
如果是4,程式會輸出big()
如果是5,程式會輸出small()
如果不是上述情況,程式會輸出"Case number is out of range!!"。

Problem Source

Problem set / Description by Paupière
建國中學105學年度校內第一次模擬賽pA

20210322 Update: 因為地球暖化日漸嚴重,導致伺服器變慢,所以最後一個subtask的時限由300ms調整為320ms

Subtasks

No. Testdata Range Score
1 0~4 10
2 5~9 15
3 10~14 28
4 15~19 47

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 1
2 1000 65536 262144 1
3 1000 65536 262144 1
4 1000 65536 262144 1
5 1000 65536 262144 2
6 1000 65536 262144 2
7 1000 65536 262144 2
8 1000 65536 262144 2
9 1000 65536 262144 2
10 1000 65536 262144 3
11 1100 65536 262144 3
12 1000 65536 262144 3
13 1000 65536 262144 3
14 1000 65536 262144 3
15 400 40960 262144 4
16 400 40960 262144 4
17 400 40960 262144 4
18 400 40960 262144 4
19 400 40960 262144 4