Submission #287266

#	Time	Username	Problem	Language	Result	Execution time	Memory
287266		Haunted_Cpp	Rectangles (IOI19_rect)	C++17	0 / 100	1 ms	512 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2500 + 5;
bool vis[MAX_N][MAX_N];

int R_max, R_min, C_max, C_min;

const int dr[] = {+1, -1, +0, +0};
const int dc[] = {+0, +0, +1, -1};

vector<vector<int>> mat;

int R, C;

int dfs(int r, int c) {
  if (r <= 0 || c <= 0 || r >= R - 1 || c >= C - 1) {
    return -2 * MAX_N * MAX_N;
  }
  R_min = min(R_min, r);
  R_max = max(R_max, r);
  C_min = min(C_min, c);
  C_max = max(C_max, c);
  vis[r][c] = 1;
  int res = 1;
  for (int i = 0; i < 4; i++) {
    if (vis[r + dr[i]][c + dc[i]]) continue;
    if (mat[r + dr[i]][c + dc[i]] > mat[r][c]) continue;
    vis[r + dr[i]][c + dc[i]] = 1;
    res += dfs(r + dr[i], c + dc[i]);
  }
  return res;
}

long long count_rectangles(vector<vector<int> > mat) {
  ::mat = mat;
  R = mat.size();
  C = mat[0].size();
  if (R <= 2) {
    return 0;
  }
  if (C <= 2) {
    return 0;
  }
  // Subtask #6
  long long res = 0;
  for (int i = 1; i < R - 1; i++) {
    for (int j = 1; j < C - 1; j++) {
      if (!vis[i][j] && mat[i][j] == 0) {
        R_max = C_max = -1;
        R_min = C_min = 1e9;
        int cur = dfs(i, j);
        cout << i << ' ' << j << ' ' << cur << '\n';
        int expected = (R_max - R_min + 1) * (C_max - C_min + 1);
        res += (cur == expected);
      }
    }
  }
	return res;
}

• 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