Submission #906579

#	Time	Username	Problem	Language	Result	Execution time	Memory
906579		NemanjaSo2005	Plus Minus (BOI17_plusminus)	C++17	100 / 100	129 ms	8412 KiB

plusminus

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll N,M,K;
const int maxn=1e5+5;
const ll MOD=1e9+7;
map<int,int> mapa;
int X[maxn],Y[maxn],sta[maxn];
ll stepen(ll a,int koji=MOD-2){
   if(koji==0)
      return 1;
   if(koji==1)
      return a;
   ll ret=stepen(a,koji/2);
   ret=(ret*ret)%MOD;
   if(koji&1)
      ret=(ret*a)%MOD;
   return ret;
}
ll broj(){
   mapa.clear();
   for(int i=1;i<=K;i++){
      int bibio=(Y[i]&1)^sta[i];
      if(mapa.find(X[i])==mapa.end())
         mapa[X[i]]=bibio;
      else
         if(mapa[X[i]]!=bibio)
            return 0;
   }
   //cout<<M<<" "<<mapa.size()<<endl;
   return stepen(2,N-mapa.size());
}
void flip(){
   swap(N,M);
   for(int i=1;i<=K;i++)
      swap(X[i],Y[i]);
}
int checkboard(int x){
   for(int i=1;i<=K;i++)
      if(x^(Y[i]&1)^(X[i]&1)^sta[i])
         return 0;
   return 1;
}
int main(){
   cin>>N>>M>>K;
   for(int i=1;i<=K;i++){
      char c;
      cin>>c>>X[i]>>Y[i];
      sta[i]=(c=='+');
   }
   ll res=0;
   res+=broj();
   flip();
   res+=broj();
   res-=checkboard(0);
   res-=checkboard(1);
   cout<<res%MOD<<"\n";
   return 0;
}

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