Submission #879212

#	Time	Username	Problem	Language	Result	Execution time	Memory
879212		sofija6	Plus Minus (BOI17_plusminus)	C++14	100 / 100	439 ms	41140 KiB

plusminus

#include <bits/stdc++.h>
#define ll long long
#define MOD 1000000007
using namespace std;
map<ll,set<ll> > rplus,cplus,rminus,cminus;
bool Check_Rows()
{
    set<pair<ll,ll> > s;
    for (auto i : rplus)
    {
        if (i.second.size()==2)
            return false;
        s.insert({i.first,*(i.second.begin())});
    }
    for (auto i : rminus)
    {
        if (i.second.size()==2 || s.count({i.first,*(i.second.begin())}))
            return false;
    }
    return true;
}
bool Check_Columns()
{
    set<pair<ll,ll> > s;
    for (auto i : cplus)
    {
        if (i.second.size()==2)
            return false;
        s.insert({i.first,*(i.second.begin())});
    }
    for (auto i : cminus)
    {
        if (i.second.size()==2 || s.count({i.first,*(i.second.begin())}))
            return false;
    }
    return true;
}
ll Exp(ll x,ll y)
{
    ll val[35];
    val[0]=x;
    for (ll i=1;i<31;i++)
        val[i]=(val[i-1]*val[i-1])%MOD;
    ll ans=1,cur=30;
    while (y)
    {
        if ((1<<cur)<=y)
        {
            y-=(1<<cur);
            ans=(ans*val[cur])%MOD;
        }
        cur--;
    }
    return ans;
}
bool Check_Chess(ll x,ll y)
{
    if (!Check_Rows() || !Check_Columns())
        return false;
    for (auto i : rplus)
    {
        if ((i.first&1) && *(i.second.begin())!=x)
            return false;
        if (!(i.first&1) && *(i.second.begin())!=y)
            return false;
    }
    for (auto i : rminus)
    {
        if ((i.first&1) && *(i.second.begin())!=y)
            return false;
        if (!(i.first&1) && *(i.second.begin())!=x)
            return false;
    }
    return true;
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n,m,k,x,y,ans=0;
    set<ll> rows,cols;
    char c;
    cin >> n >> m >> k;
    for (ll i=1;i<=k;i++)
    {
        cin >> c >> x >> y;
        rows.insert(x);
        cols.insert(y);
        if (c=='+')
        {
            rplus[x].insert(y&1);
            cplus[y].insert(x&1);
            continue;
        }
        rminus[x].insert(y&1);
        cminus[y].insert(x&1);
    }
    if (Check_Rows())
        ans+=Exp(2,n-rows.size());
    if (Check_Columns())
        ans+=Exp(2,m-cols.size());
    ans=(ans-Check_Chess(1,0)-Check_Chess(0,1)+MOD)%MOD;
    cout << ans;
    return 0;
}

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