oj.uz

Submission #879198

# Submission time Handle Problem Language Result Execution time Memory
879198 2023-11-26T18:27:36 Z sofija6 Plus Minus (BOI17_plusminus) C++14
0 / 100
 1 ms 348 KB 
#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;
    }
    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((x+y)&1);
            cplus[x].insert((x+y)&1);
            continue;
        }
        rminus[x].insert((x+y)&1);
        cminus[x].insert((x+y)&1);
    }
    if (Check_Rows())
        ans+=Exp(2,n-rows.size());
    if (Check_Columns())
        ans+=Exp(2,m-cols.size());
    ans-=Check_Chess(1,0)+Check_Chess(0,1);
    cout << ans;
    return 0;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -