Submission #441784

#	Time	Username	Problem	Language	Result	Execution time	Memory
441784		peijar	Rectangles (IOI19_rect)	C++17	13 / 100	408 ms	354820 KiB

rect

#include "rect.h"
#include <algorithm>
#include <bits/stdc++.h>
#define int long long
using namespace std;

bool seen[2500][2500];
int DX[] = {-1, 1, 0, 0};
int DY[] = {0, 0, -1, 1};
int nbLig, nbCol;
int maxLig, minLig, minCol, maxCol, nbVus;
vector<vector<signed>> val;

void dfs(int iLig, int iCol) {
  if (nbLig <= iLig or iLig < 0 or iCol < 0 or iCol >= nbCol or
      seen[iLig][iCol] or val[iLig][iCol])
    return;
  nbVus++;
  maxLig = max(maxLig, iLig);
  minLig = min(minLig, iLig);
  minCol = min(minCol, iCol);
  maxCol = max(maxCol, iCol);
  seen[iLig][iCol] = true;
  for (int d = 0; d < 4; ++d) {
    int col = iCol + DX[d];
    int lig = iLig + DY[d];
    dfs(lig, col);
  }
}

int count_rectangles(vector<vector<signed>> a) {
  val = a;
  vector<int> vals;
  nbLig = a.size(), nbCol = a[0].size();
  int ret = 0;

  for (int iLig = 0; iLig < nbLig; ++iLig)
    for (int iCol = 0; iCol < nbCol; ++iCol)
      if (!seen[iLig][iCol] and !val[iLig][iCol]) {
        minLig = maxLig = iLig;
        minCol = maxCol = iCol;
        nbVus = 0;
        dfs(iLig, iCol);
        ret += nbVus == (maxLig - minLig + 1) * (maxCol - minCol + 1) and
               maxLig < nbLig - 1 and minLig > 0 and minCol > 0 and
               maxCol < nbCol - 1;
        ;
      }
  return ret;
}

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