Submission #1115966

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115966		vjudge1	Plus Minus (BOI17_plusminus)	C++17	100 / 100	336 ms	52528 KiB

plusminus

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()
#define int long long
const ll N = 1e6 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
 
ll n,m,k;
map<ll,bool>mp[2][2], mp2[2][2];    
vector<ll>pos, Oy;
ll bpow(ll a, ll b){
    if(b == 0) return 1;
    ll ans = bpow(a, b / 2);
    if(b % 2) return ans * ans % mod * a % mod;
    else return ans * ans % mod;
}
ll calc1(){ // TH ko so le
    ll ok0 = 1, ok1 = 1;
    for(auto x : pos){
        for(int i = 0; i <= 1;i++) if(mp[i][0][x] && mp[i][1][x]) return 0;
        for(int i = 0; i <= 1;i++) if(mp[0][i][x] && mp[1][i][x]) return 0;
        if(x % 2){
            if(mp[1][1][x] || mp[0][0][x]) ok0 = 0;
            if(mp[0][1][x] || mp[1][0][x]) ok1 = 0;
        }
        if(x % 2 == 0){
            if(mp[1][0][x] || mp[0][1][x]) ok0 = 0;
            if(mp[0][0][x] || mp[1][1][x]) ok1 = 0;
        }
    }
    ll res = bpow(2, n - (ll)pos.size()) - ok0 - ok1;
    res = (res + mod) % mod;
    return res;
}   
ll calc2(){
    ll res = bpow(2, m - (ll)Oy.size());
    for(auto y : Oy){
        for(int i = 0; i <= 1;i++){
            if(mp2[i][0][y] && mp2[i][1][y]) return 0;
            if(mp2[0][i][y] && mp2[1][i][y]) return 0;
        }
    }
    return res;
}
void to_thic_cau(){
    cin >> n >> m >> k; 
    for(int i = 1; i <= k;i++){
        char c; ll x,y; cin >> c >> x >> y;
        pos.pb(x); Oy.pb(y);
        if(c == '-') mp[0][y % 2][x] = 1, mp2[0][x % 2][y] = 1;
        else mp[1][y % 2][x] = 1, mp2[1][x % 2][y] = 1;
    }
    sort(all(pos)); pos.erase(unique(all(pos)), pos.end());
    sort(all(Oy)); Oy.erase(unique(all(Oy)), Oy.end());
    cout << (calc1() + calc2()) % mod << '\n';
}

signed main()
{   
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int tc = 1;   
    //cin >> tc;
    while(tc--) to_thic_cau();
}

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