oj.uz

Submission #389289

# Submission time Handle Problem Language Result Execution time Memory
389289 2021-04-14T02:20:17 Z goldooonam Plus Minus (BOI17_plusminus) C++14
0 / 100
 1 ms 204 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];
node Datay[N];

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

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

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -