Problem Details:

Contest : Codeforces Round 589 (Div. 2)

Problem : 1228B - Filling the Grid

Solution : Submission

Solution Explanation:

Create a matrix a[r+2][c+2] to hold cell information (2 extra index for 1 based indexing + no need to check overflow)

Cell information:

-1 = Free (can be White or Black)

0 = Reserved (Must be empty and immutable)

1 = Occupied (Black cell)

[ To make r and c valid, reserved cell never be changed ]

Logic:

1. Initialize all cell as free (-1). memset(a, -1, sizeof(a[0][0]) * (r + 2) * (c + 2));

2. Take input for each row (1 to h) as "d" and do the following:

   • Make cell d+1 reserved :=> If d==0, then 1st cell (for 1 base indexing, cell d+1=1 is the 1st cell) must be reserved (0) otherwise cell d+1 reserved because if d+1 cell changed to black then r will be invalid.
   • Then make all (1 to d) cell occupied (1)

3. Take input for each col (1 to w) as "d" and do the following:(Same as logic 2, just extra need to checkout reserved cell is occupied or not before making new cell reserved or occupied)

   • Check required reserved cell is occupied or not. If occupied then it's impossible to make a grid to satisfy such r, c values, so return 0 with "0" output.
   • Make cell d+1 reserved.
   • Then make all (1 to d) cell occupied (1) BUT before made occupied check it previously reserved or not. If reserved then return 0 with "0" output.

4. Count how many free (-1) cell do you have for combinations. If free cell is zero then ans = 1(initialized) otherwise ans = 2^free_cell.

.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
const ll mod = 1e9 + 7;

#define INF 1000000000

#define ff first
#define ss second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define sz(a) a.size()
#define all(a) a.begin(), a.end()

int main() {
#ifndef ONLINE_JUDGE
  freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
#endif
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ll r, c, d, ans = 1;
  cin >> r >> c;
  int a[r + 2][c + 2];
  memset(a, -1, sizeof(a[0][0]) * (r + 2) * (c + 2));

  for (auto i = 1; i <= r; i++) {
    cin >> d;
    a[i][d + 1] = 0;
    for (auto j = 1; j <= d; j++) a[i][j] = 1;
  }

  for (auto i = 1; i <= c; i++) {
    cin >> d;
    if (a[d + 1][i] > 0) return cout << 0 << "\n", 0;
    a[d + 1][i] = 0;

    for (auto j = 1; j <= d; j++) {
      if (a[j][i] == 0) return cout << 0 << "\n", 0;
      a[j][i] = 1;
    }
  }

  for (auto i = 2; i <= r; i++) {
    for (auto j = 2; j <= c; j++) {
      if (a[i][j] == -1) ans = (ans * 2) % mod;
    }
  }
  return cout << ans << "\n", 0;
}

Happy coding