제출 #1067217

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1067217		kunzaZa183	Plus Minus (BOI17_plusminus)	C++17	100 / 100	217 ms	26824 KiB

plusminus

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  cin.tie(0)->sync_with_stdio(0);
  int x,y,n;
  cin>>x>>y>>n;
  struct symbol{
    char c;
    int a,b;
  };

  vector<int> ok(2,1);

  vector<symbol> vs(n);
  for(int i = 0; i < n;i++) {
    cin>>vs[i].c>>vs[i].a>>vs[i].b;
    if(vs[i].c=='+')
    {
      if((vs[i].a + vs[i].b)%2 == 0)
        ok[0] = 0;
      else
        ok[1] = 0;
    } else {
      if((vs[i].a + vs[i].b) %2 == 0)
        ok[1] = 0;
      else
        ok[0] = 0;
    }
  }

  map<int,vector<int>> rowvi,colvi;
  for(int i = 0; i < n;i++) {
    rowvi[vs[i].a] = vector<int>(2,1);
    colvi[vs[i].b] = vector<int>(2,1);
  }

  for(int i = 0; i < n; i++) {
    if(vs[i].c=='+') {
      if(vs[i].b % 2 == 0)
        rowvi[vs[i].a][1] = 0;
      else
        rowvi[vs[i].a][0] = 0;

      if(vs[i].a % 2 == 0)
        colvi[vs[i].b][0] = 0;
      else
        colvi[vs[i].b][1] = 0;   
    } else {
      if(vs[i].b % 2 == 0)
        rowvi[vs[i].a][0] = 0;
      else
        rowvi[vs[i].a][1] = 0;

      if(vs[i].a % 2 == 0)
        colvi[vs[i].b][1] = 0;
      else
        colvi[vs[i].b][0] = 0;   
    }
  }

  const int mod = 1e9+7;
  function<int(int, int)> logpow = [&](int a, int b) {
    if(b==0)
      return 1ll;
    int x = logpow(a,b/2);
    if(b%2==1)
      return x*x % mod * a % mod;
    return x * x % mod;
  };

  int cur = mod-accumulate(ok.begin(),ok.end(),0);
  cur %= mod;
  int num = logpow(2, x);
  // cout<<num<<'\n';
  for(auto a: rowvi) {
    // cout<<a.first<<" ";
    // for(auto b:a.second)
      // cout<<b;
    // cout<<"\n";
    int x = accumulate(a.second.begin(),a.second.end(),0);
    if(x==1)
      num *= logpow(2,mod-2);
    else if(x==0)
      num =0;
    num %= mod;
  }
  // cout<<num<<'\n';
  cur += num;
  cur %= mod;

  num = logpow(2,y);
  // cout<<num<<'\n';
  for(auto a:colvi) {
    // cout<<a.first<<" ";
    // for(auto b:a.second)
      // cout<<b;
    // cout<<"\n";
    int x = accumulate(a.second.begin(),a.second.end(),0);
    if(x==1)
      num *= logpow(2,mod - 2);
    else if(x==0)
      num = 0;
    num %= mod;
  }
  // cout<<num<<'\n';
  cur += num;
  cur %= mod;

  cout<<cur<<"\n";

}

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