Submission #630839

#	Time	Username	Problem	Language	Result	Execution time	Memory
630839		CDuong	Plus Minus (BOI17_plusminus)	C++14	0 / 100	0 ms	212 KiB

plusminus

#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const int mxN = 1e4 + 5;
const int mod = 1e9 + 7;
struct point{
    int x, y;
    char c;
    point(char c1, int x1, int y1){
        c = c1; x = x1; y = y1;
    }
};
bool cmp(point a, point b){
    if(a.x == b.x) return (a.y < b.y);
    return (a.x < b.x);
}
int binpow(int x, int y){
    int res = 1;
    while(y != 0){
        if(y % 2 == 1) res = (res * x) % mod;
        x = (x * x) % mod;
        y /= 2;
    }
    return res;
}
int n, m, k;
map<int, int> mp1;
vector<point> v;
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> k;
    for(int i = 1; i <= k; ++i){
        char c; int x, y;
        cin >> c >> x >> y;
        point tmp(c, x, y);
        v.pb(tmp);
    }
    sort(v.begin(), v.end(), cmp);
    bool flag = true;
    int diff = 1;
    for(int i = 1; i < k; ++i){
        if(v[i - 1].x == v[i].x){
            int tmp = v[i].y - v[i - 1].y, tmp1 = 0;
            if(v[i - 1].c != v[i].c) tmp1 = 1;
            if(tmp % 2 != tmp1){
                flag = false;
                break;
            }
        }
        else{
            diff++;
            //cout << v[i - 1].x << ' ' << v[i].x << " " << i << endl;
        }
    }
    int ans = 0;
    //cout << flag << " " << diff << endl;
    if(flag){
        ans += binpow(2, n - diff);
        //cout << ans << endl;
        for(int i = 0; i < k; ++i){
            int tmp = -1;
            if(v[i].c == '+') tmp += 2;
            if(mp1[v[i].y] == 0) mp1[v[i].y] = tmp;
            if(mp1[v[i].y] != tmp){
                 cout << ans << endl;
                 return 0;
            }
        }
        ans = (ans + binpow(2, m - mp1.size())) % mod;
        cout << ans << endl;
    }
    else{
        for(int i = 0; i < k; ++i){
            int tmp = -1;
            if(v[i].c == '+') tmp += 2;
            if(mp1[v[i].y] == 0) mp1[v[i].y] = tmp;
            if(mp1[v[i].y] != tmp){
                 cout << ans << endl;
                 return 0;
            }
        }
        ans = (ans + binpow(2, m - mp1.size())) % mod;
        cout << ans << endl;
    }
}

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