oj.uz

Submission #197743

# Submission time Handle Problem Language Result Execution time Memory
197743 2020-01-22T18:23:46 Z Minnakhmetov Rectangles (IOI19_rect) C++14
13 / 100
 766 ms 354772 KB 
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int N = 2505;
int dx[4] = {-1, 1, 0, 0},
	dy[4] = {0, 0, -1, 1};
bool used[N][N];
int mn_x, mx_x, mn_y, mx_y, ct, n, m;

void dfs(vector<vector<int>> &a, int x, int y) {
	used[x][y] = 1;
	ct++;

	mn_x = min(mn_x, x);
	mx_x = max(mx_x, x);

	mn_y = min(mn_y, y);
	mx_y = max(mx_y, y);

	for (int i = 0; i < 4; i++) {
		int p = x + dx[i],
			q = y + dy[i];
		if (p >= 0 && p < n && q >= 0 && q < m && 
			a[p][q] == 0 && !used[p][q]) {
			dfs(a, p, q);
		}
	}
}

bool check(vector<vector<int>> &a, int xl, int xr, int yl, int yr) {
	for (int i = xl; i <= xr; i++) {
		for (int j = yl; j <= yr; j++) {
			if (a[i][j] >= a[i][yl - 1] ||
				a[i][j] >= a[i][yr + 1] ||
				a[i][j] >= a[xl - 1][j] ||
				a[i][j] >= a[xr + 1][j]) {
				return false;
			}
		}
	}	
	return true;
}

ll solve_slow(vector<vector<int>> a) {
	n = a.size();
	m = a[0].size();
 
	ll ans = 0;
 
	for (int xl = 1; xl < n - 1; xl++) {
		for (int yl = 1; yl < m - 1; yl++) {
			for (int xr = xl; xr < n - 1; xr++) {
				for (int yr = yl; yr < m - 1; yr++) {
					if (check(a, xl, xr, yl, yr))
						ans++;
				}
			}
		}
	}
 
	return ans;
}

ll solve01(vector<vector<int>> a) {
	n = a.size();
	m = a[0].size();

	ll ans = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (!used[i][j] && a[i][j] == 0) {
				mn_x = N, mx_x = -1, mn_y = N, mx_y = -1, ct = 0;

				dfs(a, i, j);

				if (mn_x > 0 && mx_x < n - 1 &&
					mn_y > 0 && mx_y < m - 1 &&
					ct == (mx_x - mn_x + 1) * (mx_y - mn_y + 1)) {
					ans++;
				}
			}
		}
	}

	return ans;
}

ll count_rectangles(vector<vector<int>> a) {
	return solve01(a);
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 376 KB Output is correct
2 Correct 149 ms 42716 KB Output is correct
3 Correct 314 ms 92064 KB Output is correct
4 Correct 321 ms 92448 KB Output is correct
5 Correct 321 ms 92360 KB Output is correct
6 Correct 300 ms 130340 KB Output is correct
7 Correct 706 ms 302648 KB Output is correct
8 Correct 766 ms 354772 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -