oj.uz

답안 #388211

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
388211 2021-04-10T14:36:34 Z fammo Plus Minus (BOI17_plusminus) C++11
100 / 100
 268 ms 24276 KB 
#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
#define X first
#define Y second
#define pb push_back
#define fastio ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
#define rndom mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())

//#define endl '\n'
//#define int long long
const int  N =1000 + 20, MOD = 1000 * 1000 * 1000 + 7;
int n, m, k;
//set<int>x, y;
int Pow(int a, int b){
    if(b == 0)return 1;
    ll x = Pow(a, b/2);
    x *= x;
    x %= MOD;
    if(b%2)x*=a;
    x%=MOD;
    return int(x);
}
map<int, vector<pii>>mpx, mpy;
int32_t main(){
    fastio;
    ///auto t = clock();
    cin >> n >> m >> k;
    if(k == 0){
        cout <<(Pow(2 , n) + (2*((Pow(2,m-1) - 1 + MOD)%MOD))%MOD)%MOD << endl;return 0;
    }
    ll ansx = 1, ansy = 1;int ext = 1;
    for(int i = 0; i < k; i ++){
        int x, y; char c;
        cin >> c >> x >> y;
        x --; y --;
        mpx[x].pb({y, (c=='+'?1:-1)});
        mpy[y].pb({x, (c=='+'?1:-1)});
    }
    // satra yeki darmion
    for(auto it = mpx.begin(); it != mpx.end(); it ++){
        auto x = it->X; auto vec = it->Y;
        //cout << "VEC " << x <<  ": ";
        //for(auto p : vec)cout << p.X << ' ' << p.Y << ' ';
        //cout << endl;
        int b[] = {0, 0};
        if(vec.empty()){
            ansx *=2;ansx%=MOD;
            continue;
        }
        for(auto p : vec){
            int y = p.X, s = p.Y;
            b[(s>0)^((x+y)&1)]++;
        }
        if(b[0] > 0 && b[1] > 0){
            ext = 0;
            ansx = 0;
            break;
        }
    }
    ansx *= Pow(2, n-(int(mpx.size()))); ansx%=MOD;
    // sotoona yeki darmion
    for(auto it = mpy.begin(); it != mpy.end(); it ++){
        auto y = it->X; auto vec = it->Y;
        int b[] = {0, 0};
        if(vec.empty()){
            ansy *=2;ansy%=MOD;
            continue;
        }
        for(auto p : vec){
            int x = p.X, s = p.Y;
            b[(s>0)^((x+y)&1)]++;
        }
        if(b[0] > 0 && b[1] > 0){
            ext = 0;
            ansy = 0;
            break;
        }
    }
    ansy *= Pow(2, m-(int(mpy.size()))); ansy%=MOD;
    cout << ((ansx + ansy)%MOD - ext + MOD) %MOD;
    ///cout << clock() - t << "ms" << endl;
    return 0;

}

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 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 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct

Subtask #2
42.0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 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 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 452 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 43 ms 3788 KB Output is correct
17 Correct 44 ms 3764 KB Output is correct
18 Correct 45 ms 3800 KB Output is correct
19 Correct 42 ms 3652 KB Output is correct
20 Correct 44 ms 3652 KB Output is correct

Subtask #3
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 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 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 452 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 43 ms 3788 KB Output is correct
17 Correct 44 ms 3764 KB Output is correct
18 Correct 45 ms 3800 KB Output is correct
19 Correct 42 ms 3652 KB Output is correct
20 Correct 44 ms 3652 KB Output is correct
21 Correct 214 ms 15104 KB Output is correct
22 Correct 0 ms 316 KB Output is correct
23 Correct 184 ms 15092 KB Output is correct
24 Correct 199 ms 15000 KB Output is correct
25 Correct 173 ms 15016 KB Output is correct
26 Correct 200 ms 20356 KB Output is correct
27 Correct 180 ms 20304 KB Output is correct
28 Correct 225 ms 20432 KB Output is correct
29 Correct 205 ms 20388 KB Output is correct
30 Correct 268 ms 24276 KB Output is correct