Submission #1275775

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275775		rtri	Plus Minus (BOI17_plusminus)	C++20	54 / 100	48 ms	4088 KiB

plusminus

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

typedef long long int ll;

ll powmod(ll b, ll e, ll m) {
  b %= m;
  ll res = 1;
  while (0 < e) {
    if (e & 1)
      res = (res * b) % m;
    b = (b * b) % m;
    e >>= 1;
  }
  return res;
}

int main() {
  ll n, m, k;
  cin >> n >> m >> k;

  vector<tuple<ll, ll, ll>> given;
  for (ll i = 0; i < k; i++) {
    char pm;
    ll y, x;
    cin >> pm >> y >> x;
    y--;
    x--;
    if (pm == '+')
      given.push_back({y, x, 1});
    else if (pm == '-')
      given.push_back({y, x, 0});
    else
      cerr << "BAD!" << "\n";
  }

  ll freehor = n, freever = m;
  bool possiblehor = true, possiblever = true;
  vector<ll> statushor(n, -1), statusver(m, -1);
  for (ll i = 0; i < k; i++) {
    auto [y, x, flip] = given[i];

    ll fliphor = (flip + x) % 2;
    if (statushor[y] == -1) {
      freehor--;
      statushor[y] = fliphor;
    } else if (statushor[y] != fliphor)
      possiblehor = false;

    ll flipver = (flip + y) % 2;
    if (statusver[x] == -1) {
      freever--;
      statusver[x] = flipver;
    } else if (statusver[x] != flipver)
      possiblever = false;
  }

  ll ans = 0;
  if (possiblehor)
    ans += powmod(2, freehor, 1e9 + 7);
  if (possiblever)
    ans += powmod(2, freever, 1e9 + 7);

  if (possiblever && possiblehor) {
    ll t1 = 1, t2 = 1;
    for (ll i = 0; i < n; i++) {
      if (statushor[i] != -1 && statushor[i] == i % 2)
        t1 = 0;
      if (statushor[i] != -1 && statushor[i] == (i + 1) % 2)
        t2 = 0;
    }
    ans = (ans + (ll)1e9 + 7 - t1 - t2) % (ll)(1e9 + 7);
  }

  cerr << freehor << " " << possiblehor << endl;
  cerr << freever << " " << possiblever << endl;

  cout << ans << endl;

  return 0;
}

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