Submission #740013

#	Time	Username	Problem	Language	Result	Execution time	Memory
740013		fractlpaca	Quality Of Living (IOI10_quality)	C++17	100 / 100	1277 ms	147012 KiB

quality

#include "quality.h"

#include <vector>
#include <algorithm>
//#include <iostream>

#define v vector

using namespace std;

// Subtask 1 & 2: Brute Force

// int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
// 	int median = R*C;
// 	for (int i=0; i<R-H+1; i++) {
// 		for (int j=0; j<C-W+1; j++) {
// 			v<int> blocks;
// 			for (int s=i; s<i+H; s++) {
// 				for (int t=j; t<j+W; t++) {
// 					blocks.push_back(Q[s][t]);
// 				}
// 			}
// 			sort(blocks.begin(), blocks.end());
// 			median = min(median, blocks[(H*W)/2]);
// 		}
// 	}
// 	return median;
// }

// Full Solution: binary search

int q[3001][3001];
int r, c, h, w;

v<v<int>> range;


bool median_leq(int median) {
	for (int i=0; i<r; i++) {
		for (int j=0; j<c; j++) {
			range[i+1][j+1] = range[i][j+1] + range[i+1][j] - range[i][j];
			range[i+1][j+1] += (q[i][j]<=median)?1:0;
		}
	}
	for (int i=0; i<r-h+1; i++) {
		for (int j=0; j<c-w+1; j++) {
			if (range[i+h][j+w]-range[i][j+w]-range[i+h][j]+range[i][j] >= (h*w)/2+1) {
				//cerr<<"Median <= "<<median<<": "<<range[i+h][j+w]-range[i][j+w]-range[i+h][j]+range[i][j]<<" items found at ("<<i<<", "<<j<<")."<<endl;
				return true;
			}
		}
	}
	//cerr<<"Median > "<<median<<"."<<endl;
	return false;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	//cerr<<R<<" "<<C<<" "<<H<<" "<<W<<" "<<(H*W)/2<<endl;
	for (int i=0; i<R; i++) {
		for (int j=0; j<C; j++) {
			q[i][j] = Q[i][j];
		}
	}
	r=R; c=C; h=H; w=W;
	range = v<v<int>> (R+1, v<int> (C+1, 0));

	int left=0, right=R*C-(H*W)/2;
	while (left+1<right) {
		int mid = (left+right)/2;
		if (median_leq(mid)){
			right = mid;
		} else {
			left = mid;
		}
	}
	return right;
}

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