Submission #480906

#	Time	Username	Problem	Language	Result	Execution time	Memory
480906		hidden1	Plus Minus (BOI17_plusminus)	C++14	100 / 100	191 ms	11744 KiB

plusminus

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#ifndef LOCAL
#define cerr if(false) cerr
#endif
#define endl "\n"
#define all(x) (x).begin(), (x).end()
#define forn(i, n) for(int i = 0; i < n; i ++)
#define revn(i, n) for(int i = n - 1; i >= 0; i --)
typedef long long ll;
template<class T, template<class T2, class A=allocator<T2> > class cont> inline ostream &operator <<(ostream &out, const cont<T> &x) { for(const auto &it : x) { out << it << " ";} return out;}
template<class T, template<class T2, class A=allocator<T2> > class cont> inline istream &operator >>(istream &in, cont<T> &x) { for(auto &it : x) { in >> it;} return in;}
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;

const int MAX_N = 5010;
bool tab1[MAX_N][MAX_N], tab2[MAX_N][MAX_N];
bool onRow[MAX_N], onCol[MAX_N];
int n, m, k;

map<int, bool> up, lft;

ll fpow(ll x, ll p) {
    if(p == 0) {
        return 1;
    }
    ll ans = fpow(x, p / 2ll);
    ans = (ans * ans) % mod;
    if(p & 1) {
        return (ans * x) % mod;
    } else {
        return ans;
    }
}

bool okUp = true, okLeft = true;

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> n >> m >> k;

    ll ret = 0;

    forn(i, k) {
        int a, b;
        char c;
        cin >> c >> a >> b;

        int offset = (c == '+');

        if(up.find(b) != up.end()) {
            if(up[b] != ((offset + a) & 1)) {
                okUp = false;
            }
        } else {
            up[b] = ((offset + a) & 1);
        }

        if(lft.find(a) != lft.end()) {
            if(lft[a] != ((offset + b) & 1)) {
                okLeft = false;
            }
        } else {
            lft[a] = ((offset + b) & 1);
        }
    }

    if(okUp) {
        ret = (ret + fpow(2, m - up.size())) % mod; 
    }

    if(okLeft) {
        ret = (ret + fpow(2, n - lft.size())) % mod; 
    }

    if(okLeft && okUp) {
        if(k == 0) {
            ret = (ret - 2 + mod) % mod; 
        } else {
            ret = (ret - 1 + mod) % mod;             
        }
    }

    cout << ret << endl;

    return 0;
}

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