oj.uz

답안 #557846

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
557846 2022-05-06T06:42:17 Z fatemetmhr Plus Minus (BOI17_plusminus) C++17
100 / 100
 216 ms 26704 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb     push_back
#define all(x) x.begin(), x.end()
#define fi     first
#define se     second

const int maxn5 = 2e3 + 10;
const int mod   = 1e9 + 7;

map <ll, vector <pair<ll, int>>> avsatr, avstoon;
vector <pair<pair<ll, ll>, int>> have;

inline ll pw(ll a, ll b){
    ll ret = 1;
    for(; b; b >>= 1, a = a * a % mod)
        if(b & 1)
            ret = ret * a % mod;
    return ret;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int n, m, k; cin >> n >> m >> k;

    if(k == 0){
        return cout << (pw(2, n) + pw(2, m) + mod - 2) % mod << endl, 0;
    }

    for(int i = 0; i < k; i++){
        int x, y;
        char ty; cin >> ty >> x >> y;
        x--; y--;
        avsatr[x].pb({y, ty == '+' ? 0 : 1});
        avstoon[y].pb({x, ty == '+' ? 0 : 1});
        have.pb({{x, y}, ty == '+' ? 0 : 1});
    }

    ll ans = 0;
    bool ok = true;
    for(auto it = avstoon.begin(); it != avstoon.end(); it++){
        int v = (it -> fi);
        bool re1 = true, re2 = true;
        for(auto [u, z] : (it -> se)){
            re1 &= ((v + u) % 2 == z);
            re2 &= ((v + u) % 2 != z);
        }
        ok &= (re1 || re2);
    }
    if(ok)
        ans = pw(2, m - avstoon.size());

    //cout << "ok " << ans << endl;

    ok = true;
    for(auto it = avsatr.begin(); it != avsatr.end(); it++){
        int v = (it -> fi);
        bool re1 = true, re2 = true;
        for(auto [u, z] : (it -> se)){
            re1 &= ((v + u) % 2 == z);
            re2 &= ((v + u) % 2 != z);
            //cout << "ok " << v << ' '<< u << ' ' << z << ' ' << re1 << ' ' << re2 << endl;
        }
        ok &= (re1 || re2);
    }
    //cout << "then " << ok << ' ' << avsatr.size() << endl;
    if(ok)
        ans = (ans + pw(2, n - avsatr.size())) % mod;

    //cout << ans << endl;

    bool re1 = true, re2 = true;
    for(auto [p, z] : have){
        int x = p.fi, y = p.se;
        re1 &= ((x + y) % 2 == z);
        re2 &= ((x + y) % 2 != z);
    }
    if(re1 || re2)
        ans = (ans + mod - 1) % mod;
    cout << ans << endl;
}

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct

Subtask #2
42.0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 424 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 43 ms 7384 KB Output is correct
17 Correct 39 ms 7508 KB Output is correct
18 Correct 40 ms 7292 KB Output is correct
19 Correct 42 ms 7296 KB Output is correct
20 Correct 46 ms 7348 KB Output is correct

Subtask #3
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 424 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 43 ms 7384 KB Output is correct
17 Correct 39 ms 7508 KB Output is correct
18 Correct 40 ms 7292 KB Output is correct
19 Correct 42 ms 7296 KB Output is correct
20 Correct 46 ms 7348 KB Output is correct
21 Correct 156 ms 18588 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 183 ms 18576 KB Output is correct
24 Correct 175 ms 18564 KB Output is correct
25 Correct 144 ms 18608 KB Output is correct
26 Correct 142 ms 22380 KB Output is correct
27 Correct 158 ms 22456 KB Output is correct
28 Correct 160 ms 22376 KB Output is correct
29 Correct 146 ms 22308 KB Output is correct
30 Correct 216 ms 26704 KB Output is correct