Submission #832606

#	Time	Username	Problem	Language	Result	Execution time	Memory
832606		SAAD	Quality Of Living (IOI10_quality)	C++17	0 / 100	49 ms	44628 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];
static int R, C, H, W, Q[3001][3001], i, j, ans;
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]) {
	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;
}

/*int main() {
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	scanf("%d%d%d%d", &R, &C, &H, &W);
	for (i = 0; i < R; i++) for (j = 0; j < C; j++) scanf("%d", &Q[i][j]);
	ans = rectangle(R, C, H, W, Q);
	printf("%d\n", ans);
	return 0;
}*/

Compilation message (stderr)

quality.cpp:47:45: warning: 'ans' defined but not used [-Wunused-variable]
   47 | static int R, C, H, W, Q[3001][3001], i, j, ans;
      |                                             ^~~
quality.cpp:47:42: warning: 'j' defined but not used [-Wunused-variable]
   47 | static int R, C, H, W, Q[3001][3001], i, j, ans;
      |                                          ^
quality.cpp:47:39: warning: 'i' defined but not used [-Wunused-variable]
   47 | static int R, C, H, W, Q[3001][3001], i, j, ans;
      |                                       ^
quality.cpp:47:24: warning: 'Q' defined but not used [-Wunused-variable]
   47 | static int R, C, H, W, Q[3001][3001], i, j, ans;
      |                        ^
quality.cpp: In function 'int rectangle(int, int, int, int, int (*)[3001])':
quality.cpp:96:9: warning: 'md' may be used uninitialized in this function [-Wmaybe-uninitialized]
   96 |  return md;
      |         ^~

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