1916 . 絕對多數
TopCoder
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 1
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
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 15 |
| 2 | 1 | 27 |
| 3 | 2 | 19 |
| 4 | 3 | 39 |