Submission #879196

#	Time	Username	Problem	Language	Result	Execution time	Memory
879196		StefanSebez	Plus Minus (BOI17_plusminus)	C++14	100 / 100	98 ms	6228 KiB

plusminus

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
const int mod=1e9+7;
map<int,int>mapa;
ll Plus(ll a,ll b)
{
    a%=mod,b%=mod;
    ll x=a+b;x%=mod;return x;
}
ll Puta(ll a,ll b)
{
    a%=mod,b%=mod;
    ll x=a*b;x%=mod;return x;
}
ll Pow(ll a,ll b)
{
    if(b==0) return 1;
    ll x=Pow(a,b/2);
    if(b%2==0) return Puta(x,x);
    else return Puta(Puta(x,x),a);
}
int main()
{
    int n,m,k;scanf("%i%i%i",&n,&m,&k);
    pair<pair<int,int>,int>a[k+10];
    bool bul1=true,bul2=true;
    for(int i=1;i<=k;i++)
    {
        char c;cin>>c;
        int t=1;if(c=='+') t=2;
        scanf("%i%i",&a[i].fi.fi,&a[i].fi.se);
        if((a[i].fi.fi+a[i].fi.se+t-1)%2==0) bul1=false;
        else bul2=false;
        a[i].se=t;
    }
    ll res=0;
    sort(a+1,a+k+1);
    bool bul=true;
    int ct=n;
    for(int i=1;i<=k;i++)
    {
        int t=((a[i].fi.se-1)%2+a[i].se-1)%2+1;
        if((mapa[a[i].fi.fi]==1 && t==2) || (mapa[a[i].fi.fi]==2 && t==1)) bul=false;
        if(mapa[a[i].fi.fi]==0) ct--;
        mapa[a[i].fi.fi]=t;
    }
    //ll e=1;
    //for(int i=1;i<=ct;i++) e=Puta(e,2);
    if(bul) res=Plus(res,Pow(2,ct));
    for(int i=1;i<=k;i++)
    {
        swap(a[i].fi.fi,a[i].fi.se);
    }
    mapa.clear();
    sort(a+1,a+k+1);
    bul=true;
    ct=m;
    for(int i=1;i<=k;i++)
    {
        int t=((a[i].fi.se-1)%2+a[i].se-1)%2+1;
        if((mapa[a[i].fi.fi]==1 && t==2) || (mapa[a[i].fi.fi]==2 && t==1)) bul=false;
        if(mapa[a[i].fi.fi]==0) ct--;
        mapa[a[i].fi.fi]=t;
    }
    //printf("%i\n",ct);
    //e=1;
    //for(int i=1;i<=ct;i++) e=Puta(e,2);
    if(bul) res=Plus(res,Pow(2,ct));
    if(bul1==true) res--;
    if(bul2==true) res--;
    if(res<0) res+=mod;
    printf("%lld\n",res);
    return 0;
}

Compilation message (stderr)

plusminus.cpp: In function 'int main()':
plusminus.cpp:27:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     int n,m,k;scanf("%i%i%i",&n,&m,&k);
      |               ~~~~~^~~~~~~~~~~~~~~~~~~
plusminus.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |         scanf("%i%i",&a[i].fi.fi,&a[i].fi.se);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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