b859: 水梨
Tags :
Accepted rate : 27人/39人 ( 69% ) [非即時]
評分方式:
Tolerant

最近更新 : 2016-09-13 21:22

Content

小李有顆水梨。有天,小李的水梨掉進了水裡,水裡有很多水貍,水裡的水貍拿走了小李的水梨。小李想從水裡的水貍手裡拿回小李的水梨。小李發現,若一隻水貍手裡有水梨,該水貍會把水梨拿給任一隻身高更高而且體重更重的水貍。若沒有更高而且更重的水貍,那水貍就會把水梨拿在手裡。請問最後水梨可能在哪幾隻水貍的手裡?

Input

第 1 行有一正整數 T(T <= 50),接下來有 T 筆輸入。
每一筆輸入的第 1 行有 2 個正整數 N, M(M <= N <= 20,000),代表有 N 隻水貍(編號為 1~N),水梨目前在 M 號水貍的手裡。接下來有 N 行,第 i 行有兩個正整數 Hi, Wi(Hi, Wi <= 10^9),分別代表 i 號水貍的身高和體重。

 

有 40% 的測資 N <= 200

Output

對於每一筆輸入,先輸出最後水梨可能會落在幾隻水梨的手裡,下一行輸出這些水貍的編號,編號由小到大輸出。

Sample Input
2
3 1
1 1
2 3
3 2
4 2
1 3
1 1
2 2
3 3
Sample Output
2
2 3
1
4
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (20%): 3.0s , <1K
公開 測資點#1 (20%): 3.0s , <1M
公開 測資點#2 (20%): 3.0s , <50M
公開 測資點#3 (20%): 3.0s , <50M
公開 測資點#4 (20%): 3.0s , <50M
Hint :

第 1 筆輸入,1 號水貍可能會把水梨拿給 2 號或 3 號水貍,2 號和 3 號水貍不會把水梨拿給其他水貍。

Tags:
出處:
105學年度板橋高中校內資訊學科能力競賽(二) [管理者:
snail (蝸牛)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」