Submission #445090

#	Time	Username	Problem	Language	Result	Execution time	Memory
445090		leaked	Plus Minus (BOI17_plusminus)	C++14	100 / 100	144 ms	12908 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;
void paint(map<int,int> &mp,int x,int c,bool &is){
    if(mp.count(x)){
        if(mp[x]!=c) is=1;
        return;
    }
    mp[x]=c;
}
void add(int &a,int b){
    a+=b;
    if(a>=M) a-=M;
    else if(a<0) a+=M;
}
int mult(int a,int b){
    return 1ll*a*b%M;
}
int binpow(int a,int b){
    int ans=1;
    while(b){
        if(b&1) ans=mult(ans,a);
        b>>=1;a=mult(a,a);
    }
    return ans;
}
signed main(){
    fast_ioi;
    int n,m,k;
    map<int,int>x,y;
    cin>>n>>m>>k;
    vec<array<int,3>>a(k);
    for(int i=0;i<k;i++){
        int f,s;char c;
        cin>>c>>f>>s;
        if(c=='+') a[i]={f,s,1};
        else a[i]={f,s,0};
    }
    bool k1=0,k2=0;
    for(auto &z : a){
        paint(x,z[0],(z[1]%2)^z[2],k1);
        paint(y,z[1],(z[0]%2)^z[2],k2);
    }
    if(k1 && k2) cout<<0;
    else{
    int ans=0;
    if(!k1){
        add(ans,binpow(2,n-sz(x)));
//        cerr<<binpow(2,n-sz(x))<<endl;
    }
    if(!k2){
        add(ans,binpow(2,m-sz(y)));
//        cerr<<binpow(2,m-sz(y))<<endl;
    }
    if(!k1 && !k2)add(ans,-1);
    if(!sz(x) && !sz(y)) add(ans,-1);
    cout<<ans;
    }
    return 0;
}

/*
7 3
0
1
0
1
3
5
0

*/

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