Submission #568544

#	Time	Username	Problem	Language	Result	Execution time	Memory
568544		Waratpp123	Plus Minus (BOI17_plusminus)	C++14	100 / 100	62 ms	13260 KiB

plusminus

#include<bits/stdc++.h>
using namespace std;
char a[100010];
long long pi[100010],pj[100010],mod=1000000007;
unordered_map<long long,long long> mi,mj;
long long p(long long i){
    if(i==0) return 1;
    long long t=p(i/2);
    if(i%2==0) return (t*t)%mod;
    return (((2*t)%mod)*t)%mod;
}
int main(){
    long long i,j,n,m,k,ch0=0,ch1=0;
    long long ans=0,cnt=0;
    scanf("%lld %lld %lld",&n,&m,&k);
    for(i=1;i<=k;i++){
        scanf(" %c %lld %lld",&a[i],&pi[i],&pj[i]);
        if(a[i]=='+'){
            if((pi[i]+pj[i])%2==0) ch0=1;
            else ch1=1;
        }else{
            if((pi[i]+pj[i])%2==0) ch1=1;
            else ch0=1;
        }
    }
    for(i=1;i<=k;i++){
        if(a[i]=='+'){
            if(mi[pi[i]]==0){
                mi[pi[i]]=1+(pj[i]%2);
                cnt++;
            }else{
                if(mi[pi[i]]!=(1+(pj[i]%2))){
                    cnt=-1;
                    break;
                }
            }
        }else{
            if(mi[pi[i]]==0){
                mi[pi[i]]=1+(1-pj[i]%2);
                cnt++;
            }else{
                if(mi[pi[i]]!=(1+(1-pj[i]%2))){
                    cnt=-1;
                    break;
                }
            }
        }
    }
    if(cnt!=-1) ans=(ans+(p(n-cnt)))%mod;
    cnt=0;
    for(i=1;i<=k;i++){
        if(a[i]=='+'){
            if(mj[pj[i]]==0){
                mj[pj[i]]=1+(pi[i]%2);
                cnt++;
            }else{
                if(mj[pj[i]]!=(1+(pi[i]%2))){
                    cnt=-1;
                    break;
                }
            }
        }else{
            if(mj[pj[i]]==0){
                mj[pj[i]]=1+(1-pi[i]%2);
                cnt++;
            }else{
                if(mj[pj[i]]!=(1+(1-pi[i]%2))){
                    cnt=-1;
                    break;
                }
            }
        }
    }
    if(cnt!=-1) ans=(ans+(p(m-cnt)))%mod;
    if(ch1==0) ans=(ans+mod-1)%mod;
    if(ch0==0) ans=(ans+mod-1)%mod;
    printf("%lld\n",ans);
return 0;
}

Compilation message (stderr)

plusminus.cpp: In function 'int main()':
plusminus.cpp:13:17: warning: unused variable 'j' [-Wunused-variable]
   13 |     long long i,j,n,m,k,ch0=0,ch1=0;
      |                 ^
plusminus.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     scanf("%lld %lld %lld",&n,&m,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
plusminus.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         scanf(" %c %lld %lld",&a[i],&pi[i],&pj[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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