Submission #860688

#	Time	Username	Problem	Language	Result	Execution time	Memory
860688		Iliya_	Plus Minus (BOI17_plusminus)	C++17	100 / 100	136 ms	24404 KiB

plusminus

//IN THE NAME OF GOD
#include<bits/stdc++.h>
#pragma GCC optimize("O2,unroll-loops")
#define endl '\n'
#define F first
#define S second
using namespace std;
typedef long long ll; 

const ll mod = 1e9+7; 
map<ll,vector<pair<ll,char>>> r, c; 

ll power(ll a, ll b){
     if (b == 0) return 1ll;
     ll c = power(a,b/2);
     return 1ll*c*c%mod*(b&1?a:1)%mod;
}

int32_t main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

     ll n,m,k; cin >> n >> m >> k; 
     bool can1 = true, can2 = true;
     for(ll i=1; i<=k; i++){
          char val; cin >> val; 
          ll x,y; cin >> x >> y; 
          if ((((x+y)%2) == 0 && val == '-') || (((x+y)%2) == 1 && val == '+')) can1 = false;  
          if ((((x+y)%2) == 1 && val == '-') || (((x+y)%2) == 0 && val == '+')) can2 = false;  
          r[x].push_back({y,val});
          c[y].push_back({x,val}); 
     }
     ll ans = 0; 
     bool ok = true; 
     for(pair<ll,vector<pair<ll,char>>> cur : r){
          sort(cur.S.begin(),cur.S.end());
          for(ll i=1; i<ll(cur.S.size()); i++){
               if (cur.S[i].S == cur.S[i-1].S && ((cur.S[i].F - cur.S[i-1].F)%2) == 1) ok = false; 
               if (cur.S[i].S != cur.S[i-1].S && ((cur.S[i].F - cur.S[i-1].F)%2) == 0) ok = false; 
          }
     }
     if (ok) ans = (ans + power(2,n-ll(r.size())))%mod;
     ok = true; 
     for(pair<ll,vector<pair<ll,char>>> cur : c){
          sort(cur.S.begin(),cur.S.end());
          for(ll i=1; i<ll(cur.S.size()); i++){
               if (cur.S[i].S == cur.S[i-1].S && ((cur.S[i].F - cur.S[i-1].F)%2) == 1) ok = false; 
               if (cur.S[i].S != cur.S[i-1].S && ((cur.S[i].F - cur.S[i-1].F)%2) == 0) ok = false; 
          }
     }
     if (ok) ans = (ans + power(2,m-ll(c.size())))%mod;
     ans = (ans + mod - can1) % mod; 
     ans = (ans + mod - can2) % mod;
     cout << ans << endl;

     return 0;
}

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