Submission #981117

#	Time	Username	Problem	Language	Result	Execution time	Memory
981117		ShaShi	Plus Minus (BOI17_plusminus)	C++17	100 / 100	114 ms	16512 KiB

plusminus

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define kill(x) cout << x << endl, exit(0);
#define endl "\n"

 
using namespace std;
typedef long long ll;
typedef long double ld;
 

const int MAXN = (int)1e6 + 7;
const int MOD = (int)1e9 + 7;
const ll INF = (ll)1e18 + 7;


int n, m, q, tmp, tmp2, tmp3, tmp4, ans, k, u, v, w, flag, N, M;
int arr[MAXN];
vector<int> Rcmp, Ccmp;
map<int, int> R, C;
char ch;


int POW(int x, int y) {
    if (!y) return 1;
    if (y&1) return x*POW(x*x%MOD, y/2)%MOD;
    return POW(x*x%MOD, y/2);
}


int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m >> q;

    N = M = 1;
    tmp3 = tmp2 = 1;

    while (q--) {
        cin >> ch >> u >> v;

        Rcmp.pb(u); Ccmp.pb(v);

        tmp = (ch == '+'? 1 : 0)+u+v;
        tmp = (tmp%2);

        if (tmp == 0) tmp2 = 0;
        else tmp3 = 0;

        tmp += 1;

        if (R[u] == 0) R[u] = tmp;
        else if (R[u] != tmp) N = 0;

        if (C[v] == 0) C[v] = tmp;
        else if (C[v] != tmp) M = 0;
    }

    sort(all(Rcmp)); Rcmp.resize(unique(all(Rcmp))-Rcmp.begin());
    sort(all(Ccmp)); Ccmp.resize(unique(all(Ccmp))-Ccmp.begin());

    // cout << "!" << N << " " << M << endl;

    ans = (POW(2, n-Rcmp.size())*N + POW(2, m-Ccmp.size())*M - (tmp2+tmp3) + MOD)%MOD;

    cout << ans << endl;



    return 0;
}

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