Submission #884368

#	Time	Username	Problem	Language	Result	Execution time	Memory
884368		vjudge1	Plus Minus (BOI17_plusminus)	C++17	100 / 100	155 ms	24148 KiB

plusminus

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define vec e.S
using namespace std;

const int MOD = 1e9 + 7;

int n[2], k, ans;
bool cnt1 = true, cnt2 = true, ch;
map<int, vector<pair<int, bool>>> a[2];

int power(int a, int b) {
    if (b == 0) return 1;
    int tmp = power(a, b / 2);
    if (b & 1) return (tmp * tmp % MOD) * a % MOD;
    return tmp * tmp % MOD;
}

int dard(int a, int b) {
    return (((a + b) % MOD) + MOD) % MOD;
}

signed main() {
    ios:: sync_with_stdio(0), cin.tie(0);
    cin >> n[0] >> n[1] >> k;
    for (int i = 1; i <= k; i++) {
        int x, y;
        char c;
        cin >> c >> x >> y;
        if ((((x + y) & 1) && c ^ '+') || ((x + y) % 2 == 0 && c == '+')) cnt1 = false;
        if ((((x + y) & 1) && c == '+') || ((x + y) % 2 == 0 && c ^ '+')) cnt2 = false;
        a[0][x].pb({y, (c == '+')});
        a[1][y].pb({x, (c == '+')});
    }
    for (int l = 0; l < 2; l++) {
        for (auto e : a[l]) {
            sort(all(vec));
            for (int i = 0; i < vec.size() - 1; i++) {
                if (vec[i].S == vec[i + 1].S && (vec[i + 1].F - vec[i].F) & 1) ch = true;
                if (vec[i].S ^ vec[i + 1].S && (vec[i + 1].F - vec[i].F) % 2 == 0) ch = true;
            }
        }
        if (!ch) ans = dard(ans, power(2, n[l] - a[l].size()));
        ch = false;
    }
    ans = dard(ans, -cnt1), ans = dard(ans, -cnt2);
    cout << ans << '\n';
}

Compilation message (stderr)

plusminus.cpp: In function 'int main()':
plusminus.cpp:42:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |             for (int i = 0; i < vec.size() - 1; i++) {
      |                             ~~^~~~~~~~~~~~~~~~

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