제출 #389595

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
389595		goldooonam	Plus Minus (BOI17_plusminus)	C++14	100 / 100	128 ms	7108 KiB

plusminus

//-------------------------------------
//| -<{ 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 / 12
• Subtask 2: 42 / 42
• Subtask 3: 46 / 46