TopCoder

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

User's AC Ratio

80.8% (21/26)

Submission's AC Ratio

46.9% (38/81)

Description

網路遮罩 (subnet mask) 是在讀網路概論時,會學到的東西。在這裡就稍微介紹一下「網路遮罩」。

網路遮罩的格式是 $A.B.C.D/N$。A,B,C,D的範圍是在$0\sim 255$,而N的範圍是在$1\sim 32$。$A.B.C.D$是IPv4位址,$N$是遮罩的長度。每一個網路遮罩都會包含一段IP的區間。

例如 192.168.0.1/24 就是一個網路遮罩,那要如何算這個網路遮罩的位址區間呢?

先將IP寫成2進位:11000000 10101000 00000000 00000001
接下來固定前N位:11000000 10101000 00000000 ********

所以 192.168.0.1/24 所包含的IP只要是上面這行的格式就好,換句話說就是 $192.168.0.0 \sim 192.168.0.255$ 這個區間的IP。

有一天,一位網管人員要設計防火牆,但因為他數學不好,所以請你幫忙算一些資料。

這位網管人員會給你$M$個網路遮罩,接著再給你$N$個IP,問你每個IP是否有包含在這些網路遮罩中。

Input Format

第一行包含兩個正整數$M,N$,$M$代表網路遮罩的數量,$N$代表IP的數量。
接著有$M$行,每行有一個網路遮罩。
再來有$N$行,每行有一個IP。

對於所有測資,$M \leq 2\times 10^ 5 , N \leq 3\times 10^ 5$

子任務(測資) 額外限制 分數
1 (0~5) $M \leq 2\times 10^ 3, N \leq 3\times 10^ 3$ 41
2 (0~10) 59

Output Format

針對每筆IP,如果包含在網路遮罩裡,輸出TRUE
否則輸出FALSE

Sample Input

1 3
140.112.8.8/19
140.112.30.42
140.112.30.43
140.118.31.215

Sample Output

TRUE
TRUE
FALSE

Hints

每一個網路遮罩都是一個區間。

Problem Source

Problem Set by Ting.H
建國中學106學年度校隊選拔:複試pB

Subtasks

For Testdata: 0 ~ 5, Score: 41
For Testdata: 0 ~ 10, Score: 59
No. Time Limit (ms) Memory Limit (KiB)
0 900 131072
1 900 131072
2 900 131072
3 900 131072
4 900 131072
5 900 131072
6 1900 131072
7 1900 131072
8 1900 131072
9 1900 131072
10 1900 131072