oj.uz

답안 #389595

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
389595 2021-04-14T08:30:43 Z goldooonam Plus Minus (BOI17_plusminus) C++14
100 / 100
 128 ms 7108 KB 
//-------------------------------------
//| -<{ Besme llahe Rahmane Rahim }>- |
//-------------------------------------
#include <bits/stdc++.h>
#define pb push_back
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define sz(x) (int)(x).size()
#define all(c) (c).begin(),(c).end()
using namespace std;
typedef long long ll;

//----------New Code!----------
const int N = 100005;
const ll mod = 1000000007;
ll n, m, k;

struct node{int c;ll x;ll y;};
node Datax[N]; // Sorted By Row  Number
node Datay[N]; // Sorted By Col. Number

bool cmpx(node u, node v){return u.x < v.x;}
bool cmpy(node u, node v){return u.y < v.y;}

void read(){
    cin >> n >> m >> k;
    for(int i = 0; i < k; i++)
    {
        char c;
        cin >> c;
        Datax[i].c = c == '+';
        cin >> Datax[i].x >> Datax[i].y;
        Datay[i] = Datax[i];
    }
    sort(Datax, Datax+k, cmpx);
    sort(Datay, Datay+k, cmpy);
}

ll p(ll x, ll y){
    if(y == 0LL)
        return 1LL;
    ll t = p(x, y/2);
    t = (t * t)%mod;
    if(y%2)
        t = (t * x)%mod;
    return t;
}

ll solve(){
    ll C[2], R[2], kr = 0, kc = 0, ans = 0;
    bool fail1 = false, fail2 = false;
    if(k)
        kr = kc = 1;
    for(int i = 1; i < k; i++)
    {
        if(Datax[i].x != Datax[i-1].x)
            kr++;
        if(Datay[i].y != Datay[i-1].y)
            kc++;
    }
    for(int i = 0; i < k; i++)
    {
        if((i==0) || (i > 0 && Datax[i].x != Datax[i-1].x))
        {
            C[Datax[i].y%2] = Datax[i].c;
            C[1-(Datax[i].y%2)] = 1-Datax[i].c;
        }
        if(Datax[i].c != C[Datax[i].y%2])
            fail1 = true;
    }
    //------------------------------------------------------
    for(int i = 0; i < k; i++)
    {
        if((i==0) || (i > 0 && Datay[i].y != Datay[i-1].y))
        {
            R[Datay[i].x%2] = Datay[i].c;
            R[1-(Datay[i].x%2)] = 1-Datay[i].c;
        }
        if(Datay[i].c != R[Datay[i].x%2])
            fail2 = true;
    }
    if(!fail1) ans = p(2, n-kr);
    if(!fail2) ans += p(2, m-kc);
    bool b1 = true, b2 = true;
    for(int i = 0; i < k; i++)
        if(Datax[i].c != (Datax[i].x + Datax[i].y)%2)
            b1 = false;
    for(int i = 0; i < k; i++)
        if(Datax[i].c != 1-(Datax[i].x + Datax[i].y)%2)
            b2 = false;
    ans -= b1+b2;
    if(ans < 0) ans += mod;
    return ans%mod;
}

int main(){
    read();
    cout << solve();
    return 0;
}

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 280 KB Output is correct
2 Correct 1 ms 204 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 304 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 0 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 1 ms 204 KB Output is correct

Subtask #2
42.0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 280 KB Output is correct
2 Correct 1 ms 204 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 304 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 0 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 1 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 2 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 84 ms 5940 KB Output is correct
17 Correct 83 ms 5956 KB Output is correct
18 Correct 82 ms 5808 KB Output is correct
19 Correct 85 ms 5840 KB Output is correct
20 Correct 85 ms 5828 KB Output is correct

Subtask #3
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 280 KB Output is correct
2 Correct 1 ms 204 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 304 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 0 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 1 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 2 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 84 ms 5940 KB Output is correct
17 Correct 83 ms 5956 KB Output is correct
18 Correct 82 ms 5808 KB Output is correct
19 Correct 85 ms 5840 KB Output is correct
20 Correct 85 ms 5828 KB Output is correct
21 Correct 102 ms 6236 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 103 ms 6260 KB Output is correct
24 Correct 104 ms 6212 KB Output is correct
25 Correct 113 ms 6244 KB Output is correct
26 Correct 107 ms 5956 KB Output is correct
27 Correct 105 ms 5956 KB Output is correct
28 Correct 105 ms 5984 KB Output is correct
29 Correct 113 ms 6036 KB Output is correct
30 Correct 128 ms 7108 KB Output is correct