Submission #698231

#	Time	Username	Problem	Language	Result	Execution time	Memory
698231		Fidisk	Plus Minus (BOI17_plusminus)	C++14	0 / 100	1 ms	340 KiB

plusminus

#include <bits/stdc++.h>
using namespace std;

#define edge(xxxx,yyyy) ((xxxx)*(m+5)+(yyyy))
#define oo 1e9
#define fi first
#define se second
#define sp(iiii) setprecision(iiii)
#define IO ios_base::sync_with_stdio(false); cin.tie(0)
#define ms(aaaa,xxxx) memset(aaaa,xxxx,sizeof(aaaa))
#define cntbit(xxxx) __builtin_popcount(xxxx)
#define getbit(xxxx,aaaa) (((xxxx)>>((aaaa)-1))&1)
#define totbit(xxxx) (32-__builtin_clz(xxxx))
#define totbitll(xxxx) (64-__builtin_clzll(ll(xxxx)))

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<pair<int,int>,int> piii;
typedef pair<long long,long long> pll;
typedef pair<pair<long long,long long>,long long> plll;
typedef pair<pair<long long,long long>,pair<long long,long long>> pllll;
typedef pair<pair<long long,long long>,bool> pllb;

const ll base=333333349;
const ll mod=1e9+7;
const ld eps=1e-5;
const ll maxn=50009;

map<ll,ll> cnt,cnt2;
ll sl,res,n,m,sl2,s[500009],x[500009],y[500009],t1,t2,t3,i,k;
char ch;

ll GTN(ll x,ll y) {
    if (y==0) {
        return 1;
    }
    else {
        ll tmp=GTN(x,y/2);
        if (y%2==0) {
            return (tmp*tmp)%mod;
        }
        else {
            return (((tmp*tmp)%mod)*x)%mod;
        }
    }
}

int main(){
    IO;
    cin>>n>>m>>k;
    for (i=1;i<=k;i++) {
        cin>>ch>>x[i]>>y[i];
        if (ch=='+') {
            s[i]=1;
        }
        else {
            s[i]=0;
        }
        if (x[i]==1&&y[i]==1) {
            t1=s[i]+1;
        }
        else if (x[i]==2&&y[i]==1) {
            t2=s[i]+1;
        }
        else if (x[i]==1&&y[i]==2) {
            t3=s[i]+1;
        }
    }
    for (i=1;i<=k;i++) {
        if (cnt[x[i]]-1!=(s[i]^(1&y[i]))) {
            sl=n;
            break;
        }
        else {
            sl++;
            cnt[x[i]]=(s[i]^(1&y[i]))+1;;
        }
    }
    cnt.clear();
    for (i=1;i<=k;i++) {
        if (cnt[y[i]]-1!=(s[i]^(1&x[i]))) {
            sl2=m;
            break;
        }
        else {
            sl2++;
            cnt[y[i]]=(s[i]^(1&x[i]))+1;
        }
    }
    cnt.clear();
    res=(res+GTN(2,n-sl))%mod;
    res=(res+GTN(2,m-sl2))%mod;
    for (i=1;i<=k;i++) {
        if (cnt[x[i]]-1!=(s[i]^(1&y[i]))) {
            cout<<res<<'\n';
            return 0;
        }
        else {
            sl++;
            cnt[x[i]]=(s[i]^(1&y[i]))+1;;
        }
    }
    cnt.clear();
    for (i=1;i<=k;i++) {
        if (cnt[y[i]]-1!=(s[i]^(1&x[i]))) {
            cout<<res<<'\n';
            return 0;
        }
        else {
            sl2++;
            cnt[y[i]]=(s[i]^(1&x[i]))+1;
        }
    }
    cnt.clear();
    if (t1==0) {
        if (t2==0&&t3==0) {
            res=(res-2+mod)%mod;
        }
        else if (t2!=0&&t3!=0) {
            if (t2==t3) {
                res=(res-1+mod)%mod;
            }
            else {

            }
        }
        else {
            res=(res-1+mod)%mod;
        }
    }
    else {
        res=(res-1+mod)%mod;
    }
    cout<<res<<'\n';
}

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