#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;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
420 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
420 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
2 ms |
604 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
604 KB |
Output is correct |
15 |
Correct |
1 ms |
604 KB |
Output is correct |
16 |
Correct |
52 ms |
1276 KB |
Output is correct |
17 |
Correct |
42 ms |
1112 KB |
Output is correct |
18 |
Correct |
43 ms |
1280 KB |
Output is correct |
19 |
Correct |
47 ms |
1104 KB |
Output is correct |
20 |
Correct |
49 ms |
1108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
420 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
2 ms |
604 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
604 KB |
Output is correct |
15 |
Correct |
1 ms |
604 KB |
Output is correct |
16 |
Correct |
52 ms |
1276 KB |
Output is correct |
17 |
Correct |
42 ms |
1112 KB |
Output is correct |
18 |
Correct |
43 ms |
1280 KB |
Output is correct |
19 |
Correct |
47 ms |
1104 KB |
Output is correct |
20 |
Correct |
49 ms |
1108 KB |
Output is correct |
21 |
Correct |
299 ms |
29780 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
229 ms |
28756 KB |
Output is correct |
24 |
Correct |
206 ms |
28300 KB |
Output is correct |
25 |
Correct |
205 ms |
28292 KB |
Output is correct |
26 |
Correct |
210 ms |
33400 KB |
Output is correct |
27 |
Correct |
314 ms |
34452 KB |
Output is correct |
28 |
Correct |
259 ms |
34436 KB |
Output is correct |
29 |
Correct |
327 ms |
34428 KB |
Output is correct |
30 |
Correct |
439 ms |
41140 KB |
Output is correct |