oj.uz

Submission #559199

# Submission time Handle Problem Language Result Execution time Memory
559199 2022-05-09T13:26:07 Z Sweezy Plus Minus (BOI17_plusminus) C++17
100 / 100
 154 ms 11056 KB 
#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];
  }

  // debug(x);
  // debug(y);

  if (k == 0){
    cout << (power(2, n) + power(2, m) - 2 + 5 * mod) % mod;
    return;
  }
  
  // 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 {
    map<int, int> mp;
    rep(i, k) {
      // debug(i, y[i]);
      int type = (t[i] == 1 ? (x[i] & 1) : (x[i] & 1 ^ 1));
      if (mp.find(y[i]) != mp.end() && mp[y[i]] != type) {
        return;
      }
      mp[y[i]] = type;
    }
    // debug(mp);
    // debug(sz(mp));
    (res += power(2, m - sz(mp))) %= mod;
    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);
      }
      prv = y;
      prv_type = type;
    }
    need |= del;
  };
  add();
  // debug(res);
  rep(i, k) {
    int xx = x[i];
    int yy = y[i];
    y[i] = n - 1 - xx;
    x[i] = yy;
  }
  swap(n, m);
  add();
  // debug(res);
  if (need) {
    res -= 1;
    if (res < 0) {
      res += mod;
    } 
  }
  cout << res;
}
 
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  solve();
  return 0;
}

Compilation message

plusminus.cpp: In lambda function:
plusminus.cpp:93:50: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   93 |       int type = (t[i] == 1 ? (x[i] & 1) : (x[i] & 1 ^ 1));

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #2
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 16 ms 3624 KB Output is correct
17 Correct 17 ms 3560 KB Output is correct
18 Correct 17 ms 3552 KB Output is correct
19 Correct 48 ms 3684 KB Output is correct
20 Correct 54 ms 3620 KB Output is correct

Subtask #3
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 16 ms 3624 KB Output is correct
17 Correct 17 ms 3560 KB Output is correct
18 Correct 17 ms 3552 KB Output is correct
19 Correct 48 ms 3684 KB Output is correct
20 Correct 54 ms 3620 KB Output is correct
21 Correct 102 ms 7720 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 18 ms 3908 KB Output is correct
24 Correct 19 ms 4036 KB Output is correct
25 Correct 19 ms 3992 KB Output is correct
26 Correct 54 ms 7736 KB Output is correct
27 Correct 49 ms 7212 KB Output is correct
28 Correct 67 ms 8020 KB Output is correct
29 Correct 107 ms 9308 KB Output is correct
30 Correct 154 ms 11056 KB Output is correct