Submission #1150947

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150947		gyg	Rectangles (IOI19_rect)	C++20	0 / 100	24 ms	23620 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define sig signed
#define int long long
#define arr array 
#define vec vector
#define pii pair<int, int>
#define fir first 
#define sec second
const int R = 3e2 + 5, C = 3e2 + 5, INF = 1e18;

int r, c;
arr<arr<int, C>, R> a;

arr<arr<int, C>, R> rw;
arr<arr<int, R>, C> cl;
void rw_cl_cmp() {
	for (int i = 1; i <= r; i++)
		for (int j = 1; j <= c; j++)
			rw[i][j] = rw[i][j - 1] + (!a[i][j]);
	for (int j = 1; j <= c; j++)
		for (int i = 1; i <= r; i++)
			cl[j][i] = cl[j][i - 1] + (!a[i][j]);
}

vec<pii> adj(int i, int j) {
	vec<pii> opt = {{i - 1, j}, {i + 1, j}, {i, j - 1}, {i, j + 1}}, ans;
	for (pii x : opt)
		if (1 <= x.fir && x.fir <= r && 1 <= x.sec && x.sec <= c) 
			ans.push_back(x);
	return ans;
}
arr<arr<bool, C>, R> vs;
vec<pii> cmp;
void dfs(int i, int j) {
	vs[i][j] = true, cmp.push_back({i, j});
	for (pii x : adj(i, j))
		if (!vs[x.fir][x.sec] && !a[x.fir][x.sec]) dfs(x.fir, x.sec);
}

bool chck() {
	int w = INF, x = -1, y = INF, z = -1;
	for (pii xx : cmp) {
		w = min(w, xx.fir);
		x = max(x, xx.fir);
		y = min(y, xx.sec);
		z = max(z, xx.sec);
	}
	if (cmp.size() != (x - w + 1) * (z - y + 1)) return false;

	if (w == 1 || x == r || y == 1 || z == c) return false;
	if (rw[w - 1][z] - rw[w - 1][y - 1]) return false;
	if (rw[x + 1][z] - rw[x + 1][y - 1]) return false;
	if (cl[y - 1][x] - cl[y - 1][w - 1]) return false;
	if (cl[z + 1][x] - cl[z + 1][w - 1]) return false;
	return true;
}

int ans_cmp() {
	int ans = 0;
	for (int i = 1; i <= r; i++) {
		for (int j = 1; j <= c; j++) {
			if (vs[i][j]) continue;
			if (a[i][j]) continue;
			cmp.clear();
			dfs(i, j);

			// for (pii x : cmp) {
			// 	cout << x.fir << "," << x.sec << " ";
			// }
			// cout << endl;

			ans += chck();
		}
	}
	return ans;
}

int count_rectangles(vec<vec<sig>> _a) {
	r = _a.size(), c = _a[0].size();
	for (int i = 1; i <= r; i++)
		for (int j = 1; j <= c; j++)
			a[i][j] = _a[i - 1][j - 1];
	
	rw_cl_cmp();
	int ans = ans_cmp();
	return ans;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 0 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28