제출 #1275889

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1275889		sadraallami	Plus Minus (BOI17_plusminus)	C++20	100 / 100	298 ms	24696 KiB

plusminus

//وَمَكَروا وَمَكَرَ اللَّهُ ۖ وَاللَّهُ خَيرُ الماكِرينَ
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<vector<ll>> mat;
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define fast (ios_base::sync_with_stdio(false), cin.tie(NULL));
#define print(n) for(ll i:n){std::cout << i << ' ';}std::cout << endl;
ll pw(ll a,ll b,ll md=1e9+7){ll res=1;b=max(b,0ll);while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res%md);}
const ll maxn=2e5+10;
const ll mod=1e9+7;
const ll sq=500;
const ll lg=30;
const ll inf=1e18;
int vis[maxn];
vector<ll> adj[maxn];
ll n,m,k;
map<ll,ll> x,y;
int main(){
    fast;
    bool ax=true,ay=true;
    set<ll> cx,cy;
    vector<pair<char,pair<ll,ll>>> inp;
    cin>>n>>m>>k;
    for(ll i=0;i<k;i++){
        char c;ll f=0;
        ll a1,a2;
        cin>>c>>a1>>a2;
        inp.pb({c,{a1,a2}});
        cx.insert(a1);
        cy.insert(a2);
        if(c=='+')f=1;
        if(x.count(a1)){
            if(x[a1]!=f^(a2&1))ax=false;
        }
        else x[a1]=f^(a2&1);
        if(y.count(a2)){
            if(y[a2]!=f^(a1&1))ay=false;
        }
        else y[a2]=f^(a1&1);
    }
    ll ans=0;
    if(ax){
        ans+=pw(2,n-cx.size());
    }
    if(ay){
        ans+=pw(2,m-cy.size());
    }
    ll cnt=0;
    for(ll t=0;t<2;t++){
        bool check=true;
        for(auto f:inp){
            char c=f.ff;
            ll a1=f.ss.ff,a2=f.ss.ss;
            int val=(c=='+');
            if(val!=(t^((a1+a2)&1)))check=false;
        }
        if(check)cnt++;
    }
    ans=(ans-cnt+mod)%mod;
    cout<< ans << endl;
}

• Subtask 1: 12 / 12
• Subtask 2: 42 / 42
• Subtask 3: 46 / 46