TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

94.6% (87/92)

Submission's AC Ratio

40.2% (130/323)

Description

雲端列印服務公司提出一個新型服務。該公司有n 台3D 印表機,其中印表機 P1,P2, …, Pk 用以優先服務最為重要客戶,印表機 Pk+1, Pk+2, ..., Pn 列印速度較慢,用以優先服務一般客戶。每個客戶依該年度所選擇服務等級及所繳交費用可有不同的列印優先權,以1, …, 10000 表示之;10000 代表最高列印優先權,1 代表最低列印優先權。
為了不讓低列印優先權的客戶永無止盡的等待,印表機 P1,P2, …, Pk 一旦有空,等待的工作中優先權最高的工作就會被交付列印;而印表機 Pk+1, Pk+2, ..., Pn 一旦有空,等待的工作中優先權最低的工作就會被交付列印。
請寫一個程式列舉交付列印工作的順序。

Input Format

輸入只有一行,共有不定數量的整數,整數可為{-2, -1, 0, 1, 2, …, 10000},兩整數之間以一個空白隔開。-2 表示印表機 P1,P2, …, Pk其中一台有空,可以列印最高優先權的工作;-1 表示印表機Pk+1, Pk+2, ..., Pn 其中一台有空,可以列印最低優先權的工作;1, 2, …,10000 代表新增一個優先權為該數字之工作;0 則代表輸入結束。若輸入為 -1 或 -2但無等待列印的工作,則不列印,需等待下一個 -1 或 -2 才再列印新的工作。

Output Format

請依被列印工作的順序,輸出該工作的優先權代號,之後緊接著一個空白。尚未交付列印的工作不需輸出。

Sample Input

輸入範例1:
20 15 10 -2 -1 -1 0

輸入範例2:
1 2 3 -2 4 5 6 -1 7 0

Sample Output

輸出範例1:
20 10 15

輸出範例2:
3 1

Hints

本題共有五組測試資料。每組可有多個輸入檔案,全部答對該組才得分。
第一組15 分,最多11 個工作需要被列印,且只有一次交付列印指令。
第二組15 分,最多20 個工作需要被列印,且只有二次交付列印指令。
第三組20 分,最多50 個工作需要被列印,且最多有25 次交付列印指令。
第四組20 分,最多15,000 個工作需要被列印或交付列印。
第五組30 分,最多500,000 個工作需要被列印或交付列印。

注意事項:
使用C++作答的同學,請在程式碼開頭加上#include<cstdio>,並利用scanf讀入資料。使用cin 讀入資料可能會因為讀入效率太差以致於程式執行時間超過限制。
scanf 常用的讀入方式如下:
scanf("%d",&x); 讀入一個有號整數至int 型態變數x。
scanf("%lld",&y); 讀入一個有號整數至long long 型態變數y。
scanf("%u",&x); 讀入一個無號整數至unsigned int 型態變數x。
scanf("%llu",&y); 讀入一個無號整數至unsigned long long 型態變數y。

Problem Source

104學年度高級中學資訊學科能力競賽決賽程式設計試題第一題
Set by Paupière

Subtasks

No. Testdata Range Score
1 0~6 15
2 7~11 15
3 12~16 20
4 17~23 20
5 24~29 30

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1500 131072 262144 1
1 1500 131072 262144 1
2 1500 131072 262144 1
3 1500 131072 262144 1
4 1500 131072 262144 1
5 1500 131072 262144 1
6 1500 131072 262144 1
7 1500 131072 262144 2
8 1500 131072 262144 2
9 1500 131072 262144 2
10 1500 131072 262144 2
11 1500 131072 262144 2
12 1500 131072 262144 3
13 1500 131072 262144 3
14 1500 131072 262144 3
15 1500 131072 262144 3
16 1500 131072 262144 3
17 1500 131072 262144 4
18 1500 131072 262144 4
19 1500 131072 262144 4
20 1500 131072 262144 4
21 1500 131072 262144 4
22 1500 131072 262144 4
23 1500 131072 262144 4
24 1500 131072 262144 5
25 1500 131072 262144 5
26 1500 131072 262144 5
27 1500 131072 262144 5
28 1500 131072 262144 5
29 1500 131072 262144 5