Submission #404801

#	Time	Username	Problem	Language	Result	Execution time	Memory
404801		rama_pang	Plus Minus (BOI17_plusminus)	C++17	100 / 100	140 ms	11716 KiB

plusminus

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int N, M, K;
  cin >> N >> M >> K;

  // Solution:
  // Note that, if there is a cell (a, b) == (a + 1, b),
  // and  acell (c, d) == (c, d + 1), it is impossible.
  //
  // Proof:
  // If (a, b) == (a + 1, b), then (a, x) == (a + 1, x)
  // for all x, and if their b's parity is different they
  // have different signs. So, if (a, b) == (a + 1, b),
  // this implies (c, d) == (c + 1, d), (c, d) == (c, d +1).
  // However, we cannot have 3 equal signs in 2 * 2 square.
  //
  // If there is (a, b) == (a + 1, b), then that means
  // all rows have alternating signs (and we can ignore columns
  // condition). So the answer is 2^{free_row} for this case.
  //
  // Thus, we only need to keep track whether the row and column
  // is free, as well as the checkerboard pattern.
  //
  // Time complexity: O(K log K).

  const int mod = 1e9 + 7;
  const auto power = [&](int a, int x) {
    int z = 1;
    while (x) {
      if (x & 1) z = 1ll * z * a % mod;
      a = 1ll * a * a % mod;
      x /= 2;
    }
    return z;
  };

  map<int, int> R, C;
  bool freeRow = true;
  bool freeCol = true;
  bool checkerBoard1 = true;
  bool checkerBoard2 = true;

  while (K--) {
    char ch;
    cin >> ch;
    int t = ch == '+' ? 1 : -1;
    int r, c;
    cin >> r >> c;

    // If in a row, sign is not alternating, then row is dependent on column
    freeRow &= R[r] == 0 || R[r] == t * (c % 2 == 0 ? 1 : -1); R[r] = t * (c % 2 == 0 ? 1 : -1);

    // If in a column, sign is not alternating, then column is dependent on row
    freeCol &= C[c] == 0 || C[c] == t * (r % 2 == 0 ? 1 : -1); C[c] = t * (r % 2 == 0 ? 1 : -1);

    checkerBoard1 &= (t * ((r + c) % 2 == 0 ? 1 : -1)) == +1;
    checkerBoard2 &= (t * ((r + c) % 2 == 0 ? 1 : -1)) == -1;
  }

  int ans = 0;
  ans += freeRow ? power(2, N - R.size()) : 0;
  ans += freeCol ? power(2, M - C.size()) : 0;
  ans -= freeRow && freeCol && checkerBoard1;
  ans -= freeRow && freeCol && checkerBoard2;
  ans %= mod;

  cout << ans << '\n';
  return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 42 / 42
• Subtask 3: 46 / 46