oj.uz

답안 #719825

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
719825 2023-04-06T18:50:10 Z Johann Plus Minus (BOI17_plusminus) C++14
100 / 100
 427 ms 27416 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define vb vector<bool>
#define vi vector<int>
#define vvi vector<vi>
#define F0R(i, n) for (int i = 0; i < (n); ++i)

const int MOD = 1e9+7;

ll conv(ll a, ll b) {
    return 2 * a + b % 2;
}

struct Look {
    map<ll,bool> st;
    void set(ll i) {
        st[i] = true;
    }
    bool get(ll i) {
        if (st.find(i) != st.end()) return true;
        return false;
    }
    ll size() {
        return st.size();
    }
    map<ll,bool>::iterator begin() {
        return st.begin();
    }
    map<ll,bool>::iterator end() {
        return st.end();
    }
};

ll fastExp2(int p) {
    if (p == 0) return 1;
    if (p == 1) return 2;
    ll ans = fastExp2(p / 2);
    ans = (ans * ans) % MOD;
    if (p % 2 == 1) ans *= 2;
    ans %= MOD;
    return ans;
}

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

    int n,m,k;
    cin >> n >> m >> k;
    // nxm Table: n Reihen, m Spalten
    Look R, RP, RM;
    Look S, SP, SM;

    F0R(i,k) {
        string pm;
        cin >> pm;
        int x,y; // y <= n, x <= M
        cin >> y >> x;
        --x; --y;
        R.set(y);
        S.set(x);
        if (pm[0] == '+') {
            RP.set(conv(y, x));
            SP.set(conv(x, y));
        } else {
            RM.set(conv(y,x));
            SM.set(conv(x,y));
        }
    }


    // Reihen durchgehen
    ll ansR = fastExp2(n - R.size());
    for (auto it = R.begin(); it != R.end(); ++it) {
        ll i = it->first;
        if (   (RP.get(conv(i,0)) && RP.get(conv(i,1)))
            || (RM.get(conv(i,0)) && RM.get(conv(i,1)))
            || (RM.get(conv(i,0)) && RP.get(conv(i,0)))
            || (RM.get(conv(i,1)) && RP.get(conv(i,1)))
        ) {
            ansR *= 0;
        }
    }


    // Spalten durchgehen
    ll ansS = fastExp2(m - S.size());
    for (auto it = S.begin(); it != S.end(); ++it) {
        ll i = it->first;
        if ( (SP.get(conv(i,0)) && SP.get(conv(i,1)))
          || (SM.get(conv(i,0)) && SM.get(conv(i,1)))
          || (SM.get(conv(i,0)) && SP.get(conv(i,0)))
          || (SM.get(conv(i,1)) && SP.get(conv(i,1)))
                ) {
            ansS *= 0;
        }
    }

    ll ans = ansR + ansS;
    // Schachbrett möglich?
    if (ansS > 0 && ansR > 0) {
        --ans;
        if (k == 0) --ans; // hier und nur hier sind sogar beide Schachbretter möglich
    }
    ans = (ans + MOD) % MOD;
    cout << ans << "\n";
}

Subtask #1
12.0 / 12.0

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

Subtask #2
42.0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 320 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 2 ms 456 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 60 ms 1884 KB Output is correct
17 Correct 64 ms 1808 KB Output is correct
18 Correct 58 ms 1872 KB Output is correct
19 Correct 51 ms 1536 KB Output is correct
20 Correct 52 ms 1540 KB Output is correct

Subtask #3
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 320 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 2 ms 456 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 60 ms 1884 KB Output is correct
17 Correct 64 ms 1808 KB Output is correct
18 Correct 58 ms 1872 KB Output is correct
19 Correct 51 ms 1536 KB Output is correct
20 Correct 52 ms 1540 KB Output is correct
21 Correct 302 ms 18820 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 278 ms 20012 KB Output is correct
24 Correct 274 ms 20152 KB Output is correct
25 Correct 273 ms 19968 KB Output is correct
26 Correct 285 ms 23008 KB Output is correct
27 Correct 273 ms 22972 KB Output is correct
28 Correct 278 ms 23100 KB Output is correct
29 Correct 281 ms 23004 KB Output is correct
30 Correct 427 ms 27416 KB Output is correct