Submission #388211

#	Time	Username	Problem	Language	Result	Execution time	Memory
388211		fammo	Plus Minus (BOI17_plusminus)	C++11	100 / 100	268 ms	24276 KiB

plusminus

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
#define X first
#define Y second
#define pb push_back
#define fastio ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
#define rndom mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())

//#define endl '\n'
//#define int long long
const int  N =1000 + 20, MOD = 1000 * 1000 * 1000 + 7;
int n, m, k;
//set<int>x, y;
int Pow(int a, int b){
    if(b == 0)return 1;
    ll x = Pow(a, b/2);
    x *= x;
    x %= MOD;
    if(b%2)x*=a;
    x%=MOD;
    return int(x);
}
map<int, vector<pii>>mpx, mpy;
int32_t main(){
    fastio;
    ///auto t = clock();
    cin >> n >> m >> k;
    if(k == 0){
        cout <<(Pow(2 , n) + (2*((Pow(2,m-1) - 1 + MOD)%MOD))%MOD)%MOD << endl;return 0;
    }
    ll ansx = 1, ansy = 1;int ext = 1;
    for(int i = 0; i < k; i ++){
        int x, y; char c;
        cin >> c >> x >> y;
        x --; y --;
        mpx[x].pb({y, (c=='+'?1:-1)});
        mpy[y].pb({x, (c=='+'?1:-1)});
    }
    // satra yeki darmion
    for(auto it = mpx.begin(); it != mpx.end(); it ++){
        auto x = it->X; auto vec = it->Y;
        //cout << "VEC " << x <<  ": ";
        //for(auto p : vec)cout << p.X << ' ' << p.Y << ' ';
        //cout << endl;
        int b[] = {0, 0};
        if(vec.empty()){
            ansx *=2;ansx%=MOD;
            continue;
        }
        for(auto p : vec){
            int y = p.X, s = p.Y;
            b[(s>0)^((x+y)&1)]++;
        }
        if(b[0] > 0 && b[1] > 0){
            ext = 0;
            ansx = 0;
            break;
        }
    }
    ansx *= Pow(2, n-(int(mpx.size()))); ansx%=MOD;
    // sotoona yeki darmion
    for(auto it = mpy.begin(); it != mpy.end(); it ++){
        auto y = it->X; auto vec = it->Y;
        int b[] = {0, 0};
        if(vec.empty()){
            ansy *=2;ansy%=MOD;
            continue;
        }
        for(auto p : vec){
            int x = p.X, s = p.Y;
            b[(s>0)^((x+y)&1)]++;
        }
        if(b[0] > 0 && b[1] > 0){
            ext = 0;
            ansy = 0;
            break;
        }
    }
    ansy *= Pow(2, m-(int(mpy.size()))); ansy%=MOD;
    cout << ((ansx + ansy)%MOD - ext + MOD) %MOD;
    ///cout << clock() - t << "ms" << endl;
    return 0;

}

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