Submission #1187198

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187198		Ludissey	Plus Minus (BOI17_plusminus)	C++20	0 / 100	0 ms	320 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;
    vector<int> canHdouble(N+2,-1); // where + is 0 or 1
    vector<int> canVdouble(M+2,-1);
    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]==-1) canHdouble[points[i].y]=(points[i].x+(points[i].s==-1))%2;
        else if(canHdouble[points[i].y]!=(points[i].x+(points[i].s==-1))%2) canHdouble[points[i].y]=-2;

        if (canVdouble[points[i].x]==-1) canVdouble[points[i].x]=(points[i].y+(points[i].s==-1))%2;
        else if(canVdouble[points[i].x]!=(points[i].y+(points[i].s==-1))%2) canVdouble[points[i].x]=-2;
        st[points[i].s].insert({a,b});
        
        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--;
        }
    }
    for (int i = 0; i < K; i++)
    {
        int x=points[i].x, y=points[i].y;
        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()){
            if(canVdouble[x]!=-1&&canVdouble[x]!=points[i].s){
                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()){
            if(canHdouble[y]!=-1&&canHdouble[y]!=points[i].s){
                cout << 0 << "\n";
                return 0;
            }
        }
    }
    
    int sum=checkerN+checkerP+(fast_pow(2,R)-(checkerN||checkerP))+(fast_pow(2,C)-(checkerN||checkerP));
    cout << sum << "\n";
    return 0;
}

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