Submission #559185

#	Time	Username	Problem	Language	Result	Execution time	Memory
559185		Sweezy	Plus Minus (BOI17_plusminus)	C++17	0 / 100	0 ms	212 KiB

plusminus

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

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

#define all(a) (a).begin(), (a).end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define reps(i, s, n) for (int i = s; i < (n); ++i)
#define pb push_back
#define sz(a) (int) (a.size())

const int mod = 1e9 + 7;

int power(int a, int n) {
  int res = 1;
  while (n) {
    if (n % 2) {
      (res *= a) %= mod;
    }
    (a *= a) %= mod;
    n /= 2;
  }
  return res;
}

// typedef vector<vector<int>> matrix;

// matrix mul(matrix a, matrix b) {
//   matrix res(sz(a), vector<int> (sz(b[0])));
//   rep(i, sz(a)) {
//     rep(j, sz(b[0])) {
//       rep(k, sz(a[0])) {
//         (res[i][j] += a[i][k] * b[k][j]) %= mod;
//       }
//     }
//   }
//   return res;
// }

// matrix matpow(matrix a, int s, int n) {
//   matrix res(s, vector<int> (s));
//   rep(i, s) {
//     res[i][i] = 1;
//   }
//   while (n) {
//     if (n & 1) {
//       res = mul(res, a);
//     }
//     a = mul(a, a);
//     n /= 2;
//   }
//   return res;
// }

void solve() {
  int n, m, k;
  cin >> n >> m >> k;
  vector<int> x(k), y(k), t(k);
  rep(i, k) {
    char c;
    cin >> c >> x[i] >> y[i];
    t[i] = (c == '+');
    --x[i], --y[i];
  }
  
  // matrix transition{{1, 1}, {1, 0}};

  if (n == 1 || m == 1) {
    cout << power(2, n * m - k);
    return;
  }

  bool need = 0;
  int res = 0;
  auto add = [&] () -> void {
    debug(1);
    map<int, int> mp;
    rep(i, k) {
      int type = (t[i] == 1 ? (x[i] & 1) : (x[i] & 1 ^ 1));
      debug(y[i], x[i], t[i], type);
      if (mp.find(y[i]) != mp.end() && mp[y[i]] != type) {
        return;
      }
      mp[y[i]] = type;
    }
    debug(2);
    res += power(2, m - sz(mp));
    bool del = 1;
    int prv = -1, prv_type = -1;
    for (auto &[y, type] : mp) {
      if (prv != -1) {
        del &= (y - prv) % 2 == ((type == prv_type) ^ 1);
      }
    }
    need |= del;
  };
  add();
  rep(i, k) {
    int xx = x[i];
    int yy = y[i];
    y[i] = n - 1 - xx;
    x[i] = yy;
    // x[i] = xx - yy;
    // y[i] = xx + yy; 
  }
  swap(n, m);
  debug(x);
  debug(y);
  add();
  if (need) {
    res -= 1;
    if (res < 0) {
      res += mod;
    } 
  }
  cout << res;
  // int div2 = (mod + 1) / 2;
  // {
  //   /*
  //     11
  //     00
  //   */
  //   bool ok = 1;
  //   int add = power(2, m - 2);
  //   for (auto &[y, v] : mp) {
  //     if (y < 2) {
  //       for (auto &[x, t] : v) {
  //         if ((x & 1 ^ 1) != t) {
  //           ok = 0;
  //         }
  //       }
  //     } else {
  //       bool ft = 1, st = 1;
  //       for (auto &[x, t] : v) {
  //         if ((x & 1 ^ 1) != t) {
  //           ft = 0;
  //         } else {
  //           st = 0;
  //         }
  //       }
  //       ok &= ft | st;
  //       (add *= div2) %= mod;
  //     }
  //   }
  //   if (ok) {
  //     (res += add) %= mod;
  //   }
  // }
  // { 
  //   /*
  //     11
  //     00
  //   */
  // }
}
 
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  solve();
  return 0;
}

Compilation message (stderr)

plusminus.cpp: In lambda function:
plusminus.cpp:9:20: warning: statement has no effect [-Wunused-value]
    9 | #define debug(...) 42
      |                    ^~
plusminus.cpp:82:5: note: in expansion of macro 'debug'
   82 |     debug(1);
      |     ^~~~~
plusminus.cpp:85:50: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   85 |       int type = (t[i] == 1 ? (x[i] & 1) : (x[i] & 1 ^ 1));
plusminus.cpp:9:20: warning: statement has no effect [-Wunused-value]
    9 | #define debug(...) 42
      |                    ^~
plusminus.cpp:86:7: note: in expansion of macro 'debug'
   86 |       debug(y[i], x[i], t[i], type);
      |       ^~~~~
plusminus.cpp:9:20: warning: statement has no effect [-Wunused-value]
    9 | #define debug(...) 42
      |                    ^~
plusminus.cpp:92:5: note: in expansion of macro 'debug'
   92 |     debug(2);
      |     ^~~~~
plusminus.cpp: In function 'void solve()':
plusminus.cpp:9:20: warning: statement has no effect [-Wunused-value]
    9 | #define debug(...) 42
      |                    ^~
plusminus.cpp:113:3: note: in expansion of macro 'debug'
  113 |   debug(x);
      |   ^~~~~
plusminus.cpp:9:20: warning: statement has no effect [-Wunused-value]
    9 | #define debug(...) 42
      |                    ^~
plusminus.cpp:114:3: note: in expansion of macro 'debug'
  114 |   debug(y);
      |   ^~~~~

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