Submission #1187769

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187769		Ludissey	Plus Minus (BOI17_plusminus)	C++20	12 / 100	1 ms	584 KiB

plusminus

#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;

const int MOD=1e9+7;

struct point {
    int s;
    int x,y;
    point() {}
    point(char c, int a, int b){
        if(c=='+') s=1;
        else s=0;
        y=a-1;
        x=b-1;
    }
};

int fast_pow(int x, int p){
    if(p==0) return 1;
    if(p==1) return x;
    if(p%2) return (x*fast_pow(x,p-1))%MOD;
    else {
        int fp=fast_pow(x,p/2);
        return (fp*fp)%MOD;
    }
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int N,M,K; cin >> N >> M >> K;
    if(K==0){
        cout << (fast_pow(2,N)+fast_pow(2,M)-2)%MOD << "\n";
        return 0;
    }
    map<int,int> canHdouble;
    map<int,int> canVdouble;
    vector<point> points(K);
    set<pair<int,int>> st[2];
    set<int> rem[2];
    int R=N;
    int C=M;
    bool checkerP=true;
    bool checkerN=true;
    for (int i = 0; i < K; i++)
    {
        char c; cin >> c;
        int a,b; cin >> a >> b;
        points[i]=point(c,a,b);
        int x=points[i].x, y=points[i].y;

        if (canHdouble[points[i].y]==0) canHdouble[points[i].y]=(points[i].x+points[i].s)%2+1;
        else if(canHdouble[points[i].y]!=(points[i].x+points[i].s)%2+1) canHdouble[points[i].y]=-2;

        if (canVdouble[points[i].x]==0) canVdouble[points[i].x]=(points[i].y+points[i].s)%2+1;
        else if(canVdouble[points[i].x]!=(points[i].y+points[i].s)%2+1) canVdouble[points[i].x]=-2;
        st[points[i].s].insert({x,y});
        
        if((x+y)%2!=points[i].s) checkerN=false;
        if((x+y)%2==points[i].s) checkerP=false;

        if(rem[0].find(x)==rem[0].end()){
            rem[0].insert(x);
            C--;
        }
        if(rem[1].find(y)==rem[1].end()){
            rem[1].insert(y);
            R--;
        }
    }
    bool cV=true;
    bool cH=true;
    bool c0=true;
    for (int i = 0; i < K; i++)
    {
        int x=points[i].x, y=points[i].y;
        if(x==0) c0=false;
        if(y==0) c0=false;
        if(st[points[i].s].find({x+1,y})!=st[points[i].s].end()||st[points[i].s].find({x-1,y})!=st[points[i].s].end()){
            cV=false;
            if(canVdouble[x]==-2){
                cout << 0 << "\n";
                return 0;
            }
        }
        if(st[points[i].s].find({x,y+1})!=st[points[i].s].end()||st[points[i].s].find({x,y-1})!=st[points[i].s].end()){
            cH=false;
            if(canHdouble[y]==-2){
                cout << 0 << "\n";
                return 0;
            }
        }
    }
    int cb=-1;
    for (int i = 0; i < K; i++)
    {
        int x=points[i].x, y=points[i].y;
        if(st[1-points[i].s].find({x+1,y+1})!=st[1-points[i].s].end()){
            if((canVdouble[x]==-2||canVdouble[x+1]==-2)&&(canHdouble[y]==-2||canHdouble[y+1]==-2)){
                cout << 0 << "\n";
                return 0;
            }else if(canVdouble[x]==-2||canVdouble[x+1]==-2){
                cH=false;
                cb=-2;
            } else if(canHdouble[y]==-2||canHdouble[y+1]==-2){
                cV=false;
                cb=-2;
            } else if(cb==-1){
                cb=1;
            }
        }
        if(st[1-points[i].s].find({x-1,y+1})!=st[1-points[i].s].end()){
            if((canVdouble[x]==-2||canVdouble[x-1]==-2)&&(canHdouble[y]==-2||canHdouble[y+1]==-2)){
                cout << 0 << "\n";
                return 0;
            }else if(canVdouble[x]==-2||canVdouble[x-1]==-2){
                cH=false;
                cb=-2;
            } else if(canHdouble[y]==-2||canHdouble[y+1]==-2){
                cV=false;
                cb=-2;
            }else if(cb==-1){
                cb=1;
            }
        }
    }
    int sum=(int)checkerN+(int)checkerP+(fast_pow(2,R)-(int)(cH));
    if(!cH&&!cV) sum=0;
    else if(!cV){
        sum=fast_pow(2,C);
    }else if(!cH){
        sum=fast_pow(2,R);
    }else if(cb==1){
        sum=fast_pow(2,R)+fast_pow(2,C);
    }else{
        sum=(int)checkerN+(int)checkerP+fast_pow(2,R)+fast_pow(2,C)-2-2*(R+C==N+M);
        cerr<<"hello";
    }
    cout << sum%MOD << "\n";
    return 0;
}

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