Submission #790636

#	Time	Username	Problem	Language	Result	Execution time	Memory
790636		1075508020060209tc	Plus Minus (BOI17_plusminus)	C++14	100 / 100	148 ms	28948 KiB

plusminus

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;
#define int long long
int mod=1e9+7;
int qpow(int x,int t){
if(t==0){return 1;}
if(t%2==1){return x*qpow(x,t-1)%mod;}
int xx=qpow(x,t/2);
return xx*xx%mod;
}
int H;int W;int n;
int ar[200005];int br[200005];int vl[200005];
vector<pair<int,int>>rw[300005];
vector<pair<int,int>>clm[300005];
int oar[200005];
int obr[200005];
int ovl[200005];

void lisanhua(){

vector<int>vc;
for(int i=1;i<=n;i++){
    vc.push_back(ar[i]);
    vc.push_back(br[i]);
}
sort(vc.begin(),vc.end());
for(int i=1;i<=n;i++){
    ar[i]=1+lower_bound(vc.begin(),vc.end(),ar[i])-vc.begin();
    br[i]=1+lower_bound(vc.begin(),vc.end(),br[i])-vc.begin();
    rw[ar[i]].push_back({obr[i],vl[i]});
    clm[br[i]].push_back({oar[i],vl[i]});
}
}
int ans;
void rwcount(){
int cnt=0;
for(int i=1;i<=n+n;i++){
    if(rw[i].size()==0){continue;}
    cnt++;
    int typ=(rw[i][0].first+rw[i][0].second)%2;
    for(int j=1;j<rw[i].size();j++){
        int v=(rw[i][j].first+rw[i][j].second)%2;
        if(v!=typ){return;}
    }
}
ans+=qpow(2,H-cnt);
}

void clmcount(){
int cnt=0;
for(int i=1;i<=n+n;i++){
    if(clm[i].size()==0){continue;}
    cnt++;
    int typ=(clm[i][0].first+clm[i][0].second)%2;
    for(int j=1;j<clm[i].size();j++){
        int v=(clm[i][j].first+clm[i][j].second)%2;
        if(v!=typ){return;}
    }
}
ans+=qpow(2,W-cnt);


}

signed main()
{
    cin>>H>>W>>n;
    for(int i=1;i<=n;i++){
        char c;
        cin>>c>>ar[i]>>br[i];
        if(c=='+'){vl[i]=1;}else{
            vl[i]=0;
        }
        oar[i]=ar[i];
        obr[i]=br[i];
        ovl[i]=vl[i];
    }
    lisanhua();
    ans=0;
    rwcount();
    clmcount();
    if(n==0){
        cout<<(ans-2+mod)%mod;return 0;
    }
 //   cout<<ans<<" ";
    int ok=1;
    for(int i=1;i<=n;i++){
        int typ=(oar[i]+obr[i]+ovl[i])%2;
        int ch=(oar[1]+obr[1]+ovl[1])%2;
        if(ch!=typ){
            ok=0;
        }
      //  cout<<ch<<" "<<typ<<endl;
    }
    if(ok){
        ans--;
        ans+=mod;
        ans%=mod;
    }
    cout<<ans<<endl;
}

Compilation message (stderr)

plusminus.cpp: In function 'void rwcount()':
plusminus.cpp:43:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(int j=1;j<rw[i].size();j++){
      |                 ~^~~~~~~~~~~~~
plusminus.cpp: In function 'void clmcount()':
plusminus.cpp:57:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(int j=1;j<clm[i].size();j++){
      |                 ~^~~~~~~~~~~~~~

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