Submission #444615

#	Time	Username	Problem	Language	Result	Execution time	Memory
444615		leaked	Plus Minus (BOI17_plusminus)	C++14	0 / 100	0 ms	204 KiB

plusminus

#include <bits/stdc++.h>

#define vec vector
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.begin(),x.end()
#define sz(x) (int) x.size()
#define m_p make_pair
#define pw(x) (1LL<<x)
#define fast_ioi ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
auto rng=bind(uniform_int_distribution<int>(1,1000),mt19937(time(0)));
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<int,int> pii;
typedef long double ld;
const int M=1e9+7;
map<pii,int>mp;
int n,m;
bool check(int x,int y){
//    cerr<<"ALO "<<endl;
    for(int dx=-1;dx<1;dx++){
        for(int dy=-1;dy<1;dy++){
//            cout<<dx<<' '<<dy<<endl;
            int sx=x+dx,sy=y+dy;
            if(sx<=0 || sy<=0 || sx>=n || sy>=m) continue;
            vec<int>c(2,0);
            for(int i=0;i<2;i++){
                for(int j=0;j<2;j++){
                    if(mp.count({sx+i,sy+j})) c[mp[{sx+i,sy+j}]]++;
                }
            }
//            cout<<"NE"<<<<' '<endl;
            if(c[0]>2 || c[1]>2){
                return 0;
            }
        }
//        cout<<dx<<endl;
    }
    return 1;
}
int mult(int a,int b){
    return 1ll*a*b%M;
}
int binpow(int a,int b){
    int ans=1;
//    cout<<b<<endl;
    while(b){
        if(b&1) ans=mult(ans,a);
        b>>=1;a=mult(a,a);
    }
    return ans;
}
void paint(map<int,int> &gp,int x,int v){
    if(gp.count(x)){
        if(gp[x]!=v){
            cout<<0;
            exit(0);
        }
    }
    gp[x]=v;
}
signed main(){
    fast_ioi;
    int k;
    cin>>n>>m>>k;
    for(int i=0;i<k;i++){
        char c;int x,y;
        cin>>c>>x>>y;
        swap(x,y);
        int w=(c=='+'?1:0);
        mp[{x,y}]=w;
    }
    int ok=1;
    vec<pii>mm;
    for(auto &z : mp) mm.pb(z.f);
    for(auto &z : mm) ok&=check(z.f,z.s);
//    for(auto &z : mp) cerr<<z.f.f<<' '<<z.f.s<<' '<<z.s<<endl;
    map<int,int>mpx,mpy,xs,ys;
//    auto paint=[&](i)
    for(auto &z : mm){
//        pii z=q.f;
        xs[z.f]++;ys[z.s]++;
        if(mp.count({z.f,z.s+1}) && mp[{z.f,z.s+1}]==mp[{z.f,z.s}]) {
            int c=((z.f)%2)^mp[{z.f,z.s}];
//            cerr<<c<<endl;
            paint(mpy,z.s,c);
            paint(mpy,z.s+1,c);
        }
//        cerr<<mp.count({z.f+1,z.s})<<' '<<z.f<<' '<<z.s<<endl;
        if(mp.count({z.f+1,z.s}) && mp[{z.f+1,z.s}]==mp[{z.f,z.s}]){
            int c=((z.s)%2)^mp[{z.f,z.s}];
            paint(mpx,z.f,c);
            paint(mpx,z.f+1,c);
        }
    }
    for(auto &z : mm){
        if(mpx.count(z.f)){
            int c=((z.s)%2)^mp[{z.f,z.s}];
            paint(mpx,z.f,c);
        }
        if(mpy.count(z.s)){
            int c=((z.f)%2)^mp[{z.f,z.s}];
            paint(mpy,z.s,c);
        }
    }
//    cout<<sz(mpx)<<' '<<sz(mpy)<<' '<<ok<<endl;
    if((sz(mpx) && sz(mpy)) || !ok){
        cout<<0;
        return 0;
    }
    if(sz(mpx)){
        cout<<binpow(2,m-sz(mpx));
    }
    else if(sz(mpy)){
        cout<<binpow(2,n-sz(mpy));
    }
    else{
        cout<<binpow(2,n+m-sz(xs)-sz(ys));
    }
    return 0;
}

/*
7 3
0
1
0
1
3
5
0

*/

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