Submission #388240

#	Time	Username	Problem	Language	Result	Execution time	Memory
388240		soroush	Toll (BOI17_toll)	C++17	0 / 100	3080 ms	5668 KiB

toll

#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);
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 10
• Subtask 3: 0 / 8
• Subtask 4: 0 / 31
• Subtask 5: 0 / 44