e095: Emilia's story - 1 search
Tags : 搜索 陣列
Accepted rate : 19人/26人 ( 73% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-04-20 17:57

Content

愛蜜莉雅(エミリア),是擁有銀色長髪與紫紺色瞳孔的半妖精,是個性格十分善良但有些天然呆的少女。

但現在要說的,是生活在另一個平行宇宙的愛蜜莉雅。在這個平行宇宙中,愛蜜莉雅是個天才少女,一歲就自學組合語言,兩歲就解出Virtual Inert pair effect 的 virtual key,三歲就單獨寫出大型遊戲,而現在,要講的是她 1 + acos(-1) / 4 歲的故事。

在某個微風和徐的秋天,愛蜜莉雅正躺在床上並在心中模擬著電腦的運行方式順便解決 Virtual Inert pair effect 的 virtual key 的問題

剎那間,心中的思緒冒出了一段問題,有個n列m行的陣列以及q個詢問,問數字n是否存在此陣列中,如果是請問位於第幾列第幾行? 而這個陣列有兩個特別的條件:

1. 從左到右是遞增數列,從上到下也是。例如:

      1   2   3   4   5

    10 11 21 22 23      此即為一個合法陣列。

2. 陣列中不會出現相同數字。

 

經過一個小於量子干擾 a-tick 的時間(反正就是很短的時間)後,愛蜜莉雅已經想出了最佳解答。

而身為愛蜜莉雅的好閨密,你決定也來想想看這個問題,畢竟,秋天還很長。

Input

輸入第一行有兩個正整數n, m,接下來有n*m個整數ai(保證不超過int範圍)。

接著是一個整數q,代表詢問次數,接下來有q個整數qi(保證不超過int範圍)。

詢問過後請直接結束程式。

(1<=n, m<=1,600 1<=q<=100,000)

Output

對於存在於陣列中的數請輸出所在位置,格式:"yes [i, j]",i代表第幾列,j代表第幾行。

對於不存在的數請輸出"no"。

Sample Input
第一筆輸入:
2 4
1 2 3 4
10 12 20 100
3
1
10
30

第二筆輸入:
5 2
1 10
4 11
12 20
30 33
45 92
3
1
10
2
Sample Output
第一筆輸出:
yes [1, 1]
yes [2, 1]
no

第二筆輸出:
yes [1, 1]
yes [1, 2]
no
測資資訊:
記憶體限制: 70 MB
公開 測資點#0 (16%): 0.5s , <1K
公開 測資點#1 (16%): 0.5s , <1K
公開 測資點#2 (17%): 0.5s , <1K
公開 測資點#3 (17%): 0.6s , <10M
公開 測資點#4 (17%): 1.0s , <50M
公開 測資點#5 (17%): 1.2s , <50M
Hint :

如果測資有誤,請通知我,我會盡快調查。

請注意本題只有 70 MB。c++ map可能會被卡。

這題希望只用1600 * 1600的陣列,並配合好的搜索法。

另外,不確定C/C++以外的語言能不能開 1600 * 1600 個 int 而不超出記憶體。

如果你使用的語言無法開1600 * 1600個,請通知我,我會視情況調整。

2019 / 3 / 7 : 記憶體已增開到 70 MB。重新調整測資與時限。

Tags:
搜索 陣列
出處:
Emilia's story [管理者:
qqrainbow (愛蜜莉雅)
]


ID User Problem Subject Hit Post Date
17081
qqrainbow (愛蜜莉雅)
e095
解題方法
144 2019-03-07 14:23