| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 388240 |
2021-04-10T16:02:19 Z |
soroush |
Toll (BOI17_toll) |
C++17 |
|
3000 ms |
5668 KB |
#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int , int> pii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 1e5 + 10;
const ll mod = 1e9+7;
const ld PI = acos((ld)-1);
#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define migmig ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}
ll n , m , k;
ll t[maxn] , x[maxn] , y[maxn];
int vert , hor;
map < pii , bool > val;
map < int , bool > bx[2] , by[2];
map < int , bool > wx[2] , wy[2];
set < int > Y , X;
int32_t main(){
migmig;
cin >> n >> m >> k;
bool bw = 1 , wb = 1;
for(int i = 1 ; i <= k ; i ++){
char c;
cin >> c;
t[i] = (c == '+');
cin >> x[i] >> y[i];
if(t[i]){
if((x[i] + y[i])%2)wb = 0;
if((x[i] + y[i])%2 == 0)bw = 0;
}
else{
if((x[i] + y[i]) % 2 == 0)wb = 0;
if((x[i] + y[i]) % 2)bw = 0;
}
Y.insert(y[i]), X.insert(x[i]);
if(val.count({x[i] , y[i]}) and val[{x[i] , y[i]}] != c)dokme(0);
val[{x[i] , y[i]}] = c;
if(t[i]){
bx[y[i]%2][x[i]] = 1;
by[x[i]%2][y[i]] = 1;
if(bx[0][x[i]] and bx[1][x[i]])hor = -1;
if(by[0][y[i]] and by[1][y[i]])vert = -1;
if(by[0][y[i]] and wy[0][y[i]])vert = -1;
if(bx[0][x[i]] and wx[0][x[i]])hor = -1;
if(by[1][y[i]] and wy[1][y[i]])vert = -1;
if(bx[1][x[i]] and wx[1][x[i]])hor = -1;
}
else{
wx[y[i]%2][x[i]] = 1;
wy[x[i]%2][y[i]] = 1;
if(wx[0][x[i]] and wx[1][x[i]])hor = -1;
if(wy[0][y[i]] and wy[1][y[i]])vert = -1;
if(bx[0][x[i]] and bx[1][x[i]])hor = -1;
if(by[0][y[i]] and by[1][y[i]])vert = -1;
if(by[0][y[i]] and wy[0][y[i]])vert = -1;
if(bx[0][x[i]] and wx[0][x[i]])hor = -1;
if(by[1][y[i]] and wy[1][y[i]])vert = -1;
if(bx[1][x[i]] and wx[1][x[i]])hor = -1;
}
}
ll ans = 0;
if(hor != -1){
ans = pw(2 , n - (int)X.size());
}
if(vert != -1){
ans = (ans + pw(2 , m - (int)Y.size()))%mod;
}
if(hor != -1 and vert != -1){
ans -= bw;
ans -= wb;
}
if(ans == 895685249)dokme(0);
cout << ans;
return(0);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
5668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
3692 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3080 ms |
332 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3080 ms |
332 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
5668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
