oj.uz

Submission #960644

# Submission time Handle Problem Language Result Execution time Memory
960644 2024-04-10T18:24:17 Z AkibAzmain Rectangles (IOI19_rect) C++17
13 / 100
 320 ms 61948 KB 
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

long long count_rectangles (std::vector<std::vector<int> > a) {
  ll n = a.size ();
  ll m = a[0].size ();
  int c = 0;
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j)
      if (a[i][j] == 0)
        {
          int k = i, l = j;
          while (k + 1 < n && a[k + 1][j] == 0) ++k;
          while (l + 1 < m && a[i][l + 1] == 0) ++l;
          bool y = 0 < i && k < n - 1 && 0 < j && l < m - 1;
          for (int ii = i + 1; y && ii <= k; ++ii)
            for (int jj = j + 1; y && jj <= l; ++jj)
              if (a[ii][jj]) y = false;
          for (int ii = i; y && ii <= k; ++ii)
            if (a[ii][j - 1] == 0 || a[ii][l + 1] == 0)
              y = false;
          for (int ii = j; y && ii <= l; ++ii)
            if (a[i - 1][ii] == 0 || a[k + 1][ii] == 0)
              y = false;
          if (y) ++c;
          queue < pair < int, int > > q;
          q.push ({ i, j });
          while (q.size ())
            {
              auto [x, y] = q.front ();
              q.pop ();
              if (x < 0 || x >= n || y < 0 || y >= m || a[x][y]) continue;
              a[x][y] = 1;
              q.push ({ x - 1, y });
              q.push ({ x + 1, y });
              q.push ({ x, y - 1 });
              q.push ({ x, y + 1 });
            }
        }
  return c;
  // vector < vector < vector < ll > > >
  //   ra (n, vector < vector < ll > > (m, vector < ll > (m))),
  //   ca (m, vector < vector < ll > > (n, vector < ll > (n)));
  // for (ll k = 0; k < n; ++k)
  //   for (ll i = 0; i < m; ++i)
  //     {
  //       int mx = 0;
  //       for (ll j = i + 2; j < m; ++j)
  //         {
  //           mx = max (mx, a[k][j - 1]);
  //           if (mx < a[k][i] && mx < a[k][j]) ra[k][i + 1][j - 1] = 1;
  //         }
  //     }
  // for (ll k = 0; k < m; ++k)
  //   for (ll i = 0; i < n; ++i)
  //     {
  //       int mx = 0;
  //       for (ll j = i + 2; j < n; ++j)
  //         {
  //           mx = max (mx, a[j - 1][k]);
  //           if (mx < a[i][k] && mx < a[j][k]) ca[k][i + 1][j - 1] = 1;
  //         }
  //     }
  // for (ll i = 1; i < n; ++i)
  //   for (ll j = 0; j < m; ++j)
  //     for (ll k = 0; k < m; ++k)
  //       ra[i][j][k] += ra[i - 1][j][k];
  // for (ll i = 1; i < m; ++i)
  //   for (ll j = 0; j < n; ++j)
  //     for (ll k = 0; k < n; ++k)
  //       ca[i][j][k] += ca[i - 1][j][k];
  // auto alp = [&] (auto &x, int a, int b, int c, int d)
  // {
  //   return (x[d][a][b] - (c ? x[c - 1][a][b] : 0)) == d - c + 1;
  // };
  // int c = 0;
  // for (ll i1 = 0; i1 < n; ++i1)
  //   for (ll i2 = i1; i2 < n; ++i2)
  //     for (ll j1 = 0; j1 < m; ++j1)
  //       for (ll j2 = j1; j2 < m; ++j2)
  //         if (alp (ca, i1, i2, j1, j2) && alp (ra, j1, j2, i1, i2))
  //           ++c;
  // return c;
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 12.0

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

Subtask #4
0 / 22.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 356 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 348 KB Output is correct
2 Correct 111 ms 22908 KB Output is correct
3 Correct 241 ms 61436 KB Output is correct
4 Correct 252 ms 61724 KB Output is correct
5 Correct 251 ms 61728 KB Output is correct
6 Correct 143 ms 30696 KB Output is correct
7 Correct 277 ms 57988 KB Output is correct
8 Correct 320 ms 61948 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct

Subtask #7
0 / 28.0

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