Submission #879535

#	Time	Username	Problem	Language	Result	Execution time	Memory
879535		Shayan86	Plus Minus (BOI17_plusminus)	C++14	100 / 100	77 ms	11856 KiB

plusminus

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// Ofast, O0, O1, O2, O3, unroll-loops, fast-math, trapv

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define Mp          make_pair
#define sep         ' '
#define endl        '\n'
#define F	        first
#define S	        second
#define pb          push_back
#define all(x)      (x).begin(),(x).end()
#define kill(res)	cout << res << '\n', exit(0);
#define set_dec(x)	cout << fixed << setprecision(x);
#define fast_io     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io     freopen("input.txt", "r", stdin) ; freopen("output.txt", "w", stdout);

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll N = 3e5 + 50;
const ll Mod = 1e9 + 7;

ll n, m, k;

map<int, int> cond1, cond2;

ll mod(ll a, ll b = Mod){
    while(a >= b) a -= b;
    return a;
}

ll power(ll a, ll b, ll md = Mod){
    ll out = 1;
    for(; b; b /= 2, a = a * a % md){
        if(b % 2) out = out * a % md;
    }
    return out;
}

int main(){
    fast_io;

    cin >> n >> m >> k;

    if(k == 0){
        ll res = mod(power(2, n) + power(2, m) - 2 + Mod);
        kill(res);
    }

    char t; int x, y;
    for(int i = 1; i <= k; i++){
        cin >> t >> x >> y;
        int z1 = (t == '+') + y; z1 %= 2;
        int z2 = (t == '+') + x; z2 %= 2;
        cond1[x] |= (1 << z1);
        cond2[y] |= (1 << z2);
    }

    bool a = false, b = false;
    for(auto i: cond1) if(i.S == 3) a = true;
    for(auto i: cond2) if(i.S == 3) b = true;

    if(a && b) kill(0);
    
    if(a){
        ll cnt = cond2.size();
        kill(power(2, m - cnt));
    }
    if(b){
        ll cnt = cond1.size();
        kill(power(2, n - cnt));
    }

    ll cnt1 = n - cond1.size();
    ll cnt2 = m - cond2.size();

    ll res = mod(power(2, cnt1) + power(2, cnt2) - 1 + Mod);
    kill(res);


}

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