TopCoder

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

User's AC Ratio

73.5% (25/34)

Submission's AC Ratio

26.0% (45/173)

Description

在一群M 個數字中,如果有某個數字出現的次數超過M/2,則稱為此數為這群數的「絕對多數」,一群數字最多有一個絕對多數,但也可能沒有,例如(1,2,1,1,3)的絕對多數是1,而(1,2,1,3)沒有絕對多數,本題的任務是計算絕對多數。
每一筆測試資料包含一個N×N 的整數方陣A 與q 個計算要求,矩陣的元素儲存在A[0][0]~A[N-1][N-1],矩陣的橫的一排稱為列(row),直的一排稱為行(column)。每一個計算要求包含四個整數r1、r2、c1、c2,0 ≤r1 ≤ r2 < N,0 ≤ c1 ≤ c2 < N,代表一個子矩陣A[r1:r2][c1:c2],也就是第r1 列到第r2 列且第c1 行到第c2 行所組成的子矩陣,我們要計算這個子矩陣中是否有絕對多數。下圖為一個N=5 的方陣A,子矩陣A[0:1][0:2]共有六個元素,出現最多的元素是1,出現了3 次,並未超過總數的一半,因此沒有絕對多數。而子矩陣A[2:4][1:3]共有9 個元素,3 出現了5 次,超過總數的一半,因此絕對多數是3。

對於某些子題,你的程式必須很有效率的決定是否存在絕對多數。

Input Format

輸入包含多個測試資料,每筆測試資料包含一個輸入矩陣以及若干個子矩陣計算要求。每個測試資料的第一行(line)是矩陣大小的N,接下來N 行(lines)是矩陣內容,以row-major 方式排列,由第0 列(row)至第N-1 列,每列有N 個非負整數是該列第0 行(column)至第N-1 行(column),數字之間以一個空白間格。接著一行包含一個整數q 代表計算要求數,其下有q 行,每行是一個計算要求依序是子矩陣範圍的四個整數r1,r2,c1,c2。一筆測試資料結束後是下一筆測試資料,若N=0 代表輸入資料結束。

Output Format

針對每個測試資料的每個計算要求,以一行輸出絕對多數,如果沒有絕對多數則輸出-1。

Sample Input

5
1 2 3 3 2
2 1 1 2 3
1 2 3 1 1
0 2 3 3 1
0 3 1 3 2
2
0 1 0 2
2 4 1 3
0

Sample Output

-1
3

Hints

本題共有四組測試資料。每組可有多個輸入檔案,全部答對該組才得分。每組測試資料的輸入檔參數N、D、Q 和S 如下,其中N 是矩陣大小的上限,D 代表陣列中數字的上限,Q 是計算需求總數即該檔案中q 值的總和,也就是該子題總共輸出Q 行,S 則是輸入檔案中,所有矩陣的元素總量,即N2 的總和。
第一組15 分,N ≤ 100、D ≤ 5000、Q ≤ 40、S ≤ 32000。
第二組27 分,N ≤ 1010、D ≤ 5000、Q ≤ 30、S ≤ 3200000。
第三組19 分,N ≤ 1010、D ≤ 231-1、Q ≤ 50、S ≤ 3200000。
第四組39 分,N ≤ 2000、D ≤ 231-1、Q ≤ 70、S ≤ 12500000。

注意事項:
使用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

For Testdata: 0 ~ 0, Score: 15
For Testdata: 1 ~ 1, Score: 27
For Testdata: 2 ~ 2, Score: 19
For Testdata: 3 ~ 3, Score: 39
No. Time Limit (ms) Memory Limit (KiB)
0 6000 30720
1 6000 30720
2 6000 30720
3 6000 30720