#include #include #include #define MAXNM 1000 int M, N, P, Q; int X[MAXNM][MAXNM]; // Vstup int values[MAXNM*MAXNM]; // Jeho setříděná verze int px[MAXNM+1][MAXNM+1]; // 2D prefixové součty int mi, mj; // Nalezená poloha okénka int compare_values(const void *a, const void *b) { const int *aa = a, *bb = b; return (*aa > *bb) - (*aa < *bb); } // Orákulum pro binární vyhledávání: // Vrátí true, pokud existuje okénko s mediánem aspoň med. bool oracle(int med) { // Spočítáme 2D prefixové součty pomocné matice, v níž jsou jedničky // právě tam, kde X[i][j] < med. Pomocnou matici nikam neukládáme // a kvůli snazšímu výpočtu má vůči matici X indexy posunuté o 1. for (int j=0; j<=N; j++) px[0][j] = 0; for (int i=1; i<=M; i++) { px[i][0] = 0; for (int j=1; j<=N; j++) { int p = (X[i-1][j-1] < med); // Pomocná matice px[i][j] = px[i-1][j] + px[i][j-1] - px[i-1][j-1] + p; } } // Projdeme všechny možné polohy okénka a pro každou z nich spočítáme // prvky menší než med. Pokud jich je nejvýše P*Q/2, medián je aspoň med. for (int i=1; i<=M-P+1; i++) for (int j=1; j<=N-Q+1; j++) { int s = px[i+P-1][j+Q-1] - px[i-1][j+Q-1] - px[i+P-1][j-1] + px[i-1][j-1]; if (s <= P*Q/2) { mi = i-1, mj = j-1; return 1; } } return 0; } // Binární vyhledávání maximálního mediánu okénka void binary_search(void) { int l=0, r=M*N; // Invariant: values[l] <= hledané maximum < values[r] // (na konci pole values si domýšlíme +nekonečno) while (r-l > 1) { int m = (l+r)/2; if (oracle(values[m])) l = m; else r = m; } // Teď musí být ve values[l] hledané maximum. Spustíme orákulum ještě // jednou, aby našlo správnou polohu okénka. oracle(values[l]); } int main(void) { // Načteme vstup a rovnou si pořídíme jeho setříděnou verzi scanf("%d%d%d%d", &M, &N, &P, &Q); int n = 0; for (int i=0; i