Submission #591661

#	Time	Username	Problem	Language	Result	Execution time	Memory
591661		MohammadAghil	Plus Minus (BOI17_plusminus)	C++17	100 / 100	238 ms	25468 KiB

plusminus

#include <iostream>
#include <algorithm>
#include <functional>
#include <random>
#include <cmath>
#include <vector>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <cassert>
#include <string>
#include <bitset>
#include <numeric>
#include <iomanip>
#include <limits.h>
#include <tuple>

using namespace std;

#define rep(i,l,r) for(int i = l; i < (r); i++)
#define per(i,r,l) for(int i = r; i >= (l); i--)
#define sz(x) (int)size(x)
#define pb push_back
#define all(x) begin(x), end(x)
#define ff first
#define ss second

typedef long long ll;
typedef pair<int, int> pp;

const ll mod = 1e9+7, maxn = 2e5 + 5, inf = ll(1e9) + 5, lg = 20;

ll pw(ll a, ll b){
    if(b == 0) return 1;
    ll k = pw(a, b>>1ll);
    return k*k%mod*(b&1ll?a:1ll)%mod;
}

map<int, vector<pair<int, bool>>> ver, hor;
int n, m, k;
vector<pair<bool, pp>> node;

int chess_state(){
    if(k == 0) return 2;
    for(auto[vl, p]: node) if(((vl^(p.ff + p.ss))&1) != ((node.back().ff^(node.back().ss.ff + node.back().ss.ss))&1)) return 0;
    return 1;
}

int hor_state(){
    int exp = -1;
    bool dec = true;
    int cnt = 0;
    for(auto[y, v]: hor){
        cnt++;
        pair<int, bool> ex = v.back();
        int s = ((y + ex.ff)&1)^ex.ss;
        if(exp == -1) exp = s;
        else if(s != exp) dec = false;
        for(auto[x, vl]: v){
            if((((x + y)&1)^vl) != s) return 0;
        }
    }
    ll ans = pw(2, n - cnt);
    if(dec) ans -= 1 + (k == 0);
    return (ans + mod)%mod;
}

int ver_state(){
    int exp = -1;
    bool dec = true;
    int cnt = 0;
    for(auto[y, v]: ver){
        cnt++;
        pair<int, bool> ex = v.back();
        int s = ((y + ex.ff)&1)^ex.ss;
        if(exp == -1) exp = s;
        else if(s != exp) dec = false;
        for(auto[x, vl]: v){
            if((((x + y)&1)^vl) != s) return 0;
        }
    }
    ll ans = pw(2, m - cnt);
    if(dec) ans -= 1 + (k == 0);
    return (ans + mod)%mod;
}

int main(){
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> m >> k; swap(n, m);
    rep(i,0,k){
        char s; cin >> s;
        int x, y; cin >> x >> y;
        ver[x].pb({y, s == '+'});
        hor[y].pb({x, s == '+'});
        node.pb({s == '+', {x, y}});
    }
    cout << (chess_state() + hor_state() + ver_state())%mod << '\n';
    return 0;
}

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