Submission #834743

#	Time	Username	Problem	Language	Result	Execution time	Memory
834743		SAAD	Quality Of Living (IOI10_quality)	C++17	100 / 100	1921 ms	254748 KiB

quality

#define F first
#define S second
#define rep(i,a,b) for(int i=a;!(a==b&&i!=b)&&((i<=b&&b>=a)||(i>=b&&a>=b));i+=(a<=b?1:-1))
#define pb push_back
#define Fbitl __builtin_ffs
#define bit1 __builtin_popcount
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <map>
#include <unordered_map>
#include <unordered_set>

#include "quality.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<string, string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<vl> vvl;
 
/*int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	
	return R * C / 2;
}
static int R, C, H, W, Q[3001][3001], i, j, ans;
int main() {
	cin >> R >> C >> H >> W ;
	for (i = 0; i < R; i++) for (j = 0; j < C; j++) cin >> Q[i][j];
	ans = rectangle(R, C, H, W, Q);
	printf("%d\n", ans);
	return 0;
}*/
bool q[3003][3003];
int cm[3003][3003];
int ps[3003][3003];
pii psof[(int)1e7];
int R, C, H, W;
bool test( int idx ) {
	memset(q,false,sizeof(q));
	memset(cm, 0, sizeof(cm));
	for (int i = 1; i <= idx; i++) {
		q[psof[i].F][psof[i].S] = true;
	}
	int target = (H * W)/2 + 1;
	bool th = false;
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			cm[i][j] = (q[i][j] ? 1 : 0) + (cm[i][j - 1] + cm[i - 1][j] - cm[i - 1][j - 1]);
			if (i >= H && j >= W) {
				int sum = 0;
				sum = cm[i][j] + cm[i - H][j - W] - (cm[i-H][j]+cm[i][j-W]);
				if (sum >= target) {
					th = true;
				}
			}
		}
	}
	return th;
}
 
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
		::R = R;
		::C = C ;
		::H = H ;
		::W = W ;
	int l = 1, r = R * C , md ;
	
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++)
		{

			ps[i + 1][j + 1] = Q[i][j];
			psof[Q[i][j]] = {i+1,j+1};
		}
	}
	while (r > l ) {
		int ll = l, rr = r;
		md = (r + l) / 2;
		if (test(md)) {
			r = md ;
		}
		else {
			l = md+1 ;
		}
		if (ll == l && rr == r) break;
	}
	for (int i = l; i <= r; i++) {
		if (test(i)) {
			return i;
		}
	}
	return md;
}

Compilation message (stderr)

quality.cpp: In function 'int rectangle(int, int, int, int, int (*)[3001])':
quality.cpp:103:9: warning: 'md' may be used uninitialized in this function [-Wmaybe-uninitialized]
  103 |  return md;
      |         ^~

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