Submission #1034742

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034742		belgianbot	Quality Of Living (IOI10_quality)	C++14	100 / 100	1940 ms	138032 KiB

quality

#include "quality.h"
#include <bits/stdc++.h>

using namespace std;

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	int l = 1, r = R * C;
	int ans = 1;
	while (l <= r) {
		int mid = l + (r - l) / 2;
		//cout << mid << " ";
		bool possible = false, ok = false;
		vector<vector<int>> nbSmaller (R, vector<int>(C - W + 1));
		vector<vector<int>> nbBigger (R, vector<int>(C - W + 1));
		for (int i = 0; i < R; i++) {
			int cnt = 0, cnt2 = 0;
			for (int j = 0; j < W; j++) {cnt += (Q[i][j] < mid); cnt2 += (Q[i][j] > mid);}
			nbSmaller[i][0] = cnt;
			nbBigger[i][0] = cnt2;
			for (int j = 0; j < C - W; j++) {
				cnt -= (Q[i][j] < mid);
				cnt += (Q[i][j + W] < mid);
				cnt2 -= (Q[i][j] > mid);
				cnt2 += (Q[i][j + W] > mid);
				nbSmaller[i][j + 1] = cnt;
				nbBigger[i][j + 1] = cnt2;
			}
		}
		/*cout << mid << '\n';
		for (auto x : nbSmaller) {
			for (auto y : x) cout << y << ' ';
			cout << '\n';
		}
		cout << "\n\n";*/
		for (int i = 0; i < C - W + 1; i++) {
			int cnt = 0, cnt2 = 0;
			for (int j = 0; j < H; j++) {cnt += nbSmaller[j][i]; cnt2 += nbBigger[j][i];}
			if (cnt2 <= (W * H) / 2) {
				possible = true;
				if (cnt == cnt2 && cnt == W * H / 2) {
					ok = true;
					break;
				}
			}
			for (int j = 0; j < R - H; j++) {
				cnt -= nbSmaller[j][i];
				cnt += nbSmaller[j + H][i];
				cnt2 -= nbBigger[j][i];
				cnt2 += nbBigger[j + H][i];
				if (cnt2 <= (W * H) / 2) {
					possible = true;
					if (cnt == cnt2 && cnt == W * H / 2) {
						ok = true;
						break;
					}
				}
			}
			if (ok) break;
		}
		if (possible) {
			//cout << "passed\n";
			if (ok) ans = mid;
			r = mid - 1;
		}
		else {
			//cout << "failed\n";
			l = mid + 1;
		}
	}
	return ans;
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20