oj.uz

답안 #480906

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
480906 2021-10-18T16:17:46 Z hidden1 Plus Minus (BOI17_plusminus) C++14
100 / 100
 191 ms 11744 KB 
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#ifndef LOCAL
#define cerr if(false) cerr
#endif
#define endl "\n"
#define all(x) (x).begin(), (x).end()
#define forn(i, n) for(int i = 0; i < n; i ++)
#define revn(i, n) for(int i = n - 1; i >= 0; i --)
typedef long long ll;
template<class T, template<class T2, class A=allocator<T2> > class cont> inline ostream &operator <<(ostream &out, const cont<T> &x) { for(const auto &it : x) { out << it << " ";} return out;}
template<class T, template<class T2, class A=allocator<T2> > class cont> inline istream &operator >>(istream &in, cont<T> &x) { for(auto &it : x) { in >> it;} return in;}
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;

const int MAX_N = 5010;
bool tab1[MAX_N][MAX_N], tab2[MAX_N][MAX_N];
bool onRow[MAX_N], onCol[MAX_N];
int n, m, k;

map<int, bool> up, lft;

ll fpow(ll x, ll p) {
    if(p == 0) {
        return 1;
    }
    ll ans = fpow(x, p / 2ll);
    ans = (ans * ans) % mod;
    if(p & 1) {
        return (ans * x) % mod;
    } else {
        return ans;
    }
}

bool okUp = true, okLeft = true;

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> n >> m >> k;

    ll ret = 0;

    forn(i, k) {
        int a, b;
        char c;
        cin >> c >> a >> b;

        int offset = (c == '+');

        if(up.find(b) != up.end()) {
            if(up[b] != ((offset + a) & 1)) {
                okUp = false;
            }
        } else {
            up[b] = ((offset + a) & 1);
        }

        if(lft.find(a) != lft.end()) {
            if(lft[a] != ((offset + b) & 1)) {
                okLeft = false;
            }
        } else {
            lft[a] = ((offset + b) & 1);
        }
    }

    if(okUp) {
        ret = (ret + fpow(2, m - up.size())) % mod; 
    }

    if(okLeft) {
        ret = (ret + fpow(2, n - lft.size())) % mod; 
    }

    if(okLeft && okUp) {
        if(k == 0) {
            ret = (ret - 2 + mod) % mod; 
        } else {
            ret = (ret - 1 + mod) % mod;             
        }
    }

    cout << ret << endl;

    return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
42.0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 336 KB Output is correct
16 Correct 47 ms 1288 KB Output is correct
17 Correct 45 ms 1348 KB Output is correct
18 Correct 48 ms 1292 KB Output is correct
19 Correct 45 ms 1348 KB Output is correct
20 Correct 48 ms 1292 KB Output is correct

Subtask #3
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 336 KB Output is correct
16 Correct 47 ms 1288 KB Output is correct
17 Correct 45 ms 1348 KB Output is correct
18 Correct 48 ms 1292 KB Output is correct
19 Correct 45 ms 1348 KB Output is correct
20 Correct 48 ms 1292 KB Output is correct
21 Correct 123 ms 7348 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 104 ms 7248 KB Output is correct
24 Correct 120 ms 7244 KB Output is correct
25 Correct 106 ms 7192 KB Output is correct
26 Correct 114 ms 9924 KB Output is correct
27 Correct 112 ms 9804 KB Output is correct
28 Correct 109 ms 9904 KB Output is correct
29 Correct 121 ms 9924 KB Output is correct
30 Correct 191 ms 11744 KB Output is correct