Submission #1120455

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120455		mmdrzada	Plus Minus (BOI17_plusminus)	C++17	100 / 100	246 ms	28392 KiB

plusminus

#include <bits/stdc++.h>
 
using namespace std;

typedef vector<int> vi;
typedef vector<char> vc;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
 
#define sep ' '
#define F first
#define S second
#define fastIO   ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define kill(x) {cout << x << endl;return;}
#define sz(x) int(x.size())
#define SP(x) setprecision(x) 
#define mod(x) (1ll*x%M+M)%M
#define pq priority_queue
#define mid (l+r)/2
// #define mid2 (l+r+1)/2
#define pll pair<ll, ll>
#define REP(i, k) for (int i = 0 ; i < k ; i ++)
#define MP make_pair
#define int ll

const int M = 1e9+7;
const int N = 1000+1;
int n, m, k;

int my_pow(int x, int y) {
	int res = 1;
	while(y) {
		if (y&1) res = 1ll*res*x%M;
		x = 1ll*x*x%M;
		y /= 2;
	}
	return res;
}

void solve() {
	cin >> n >> m >> k;
	bool bad0 = false, bad1 = false;
	vi rows, cols;
	map<int, bool> Rbad01, Rbad10, Cbad01, Cbad10;
	for(int i = 0 ; i < k ; i ++) {
		char c; int x, y; cin >> c >> x >> y; x--, y--;
		rows.pb(x), cols.pb(y);
		bool t = c == '+';
		
		if ((x+y)%2 == 0) {
			if (t) bad0 = true;
			else bad1 = true;
		} else {
			if (t) bad1 = true;
			else bad0 = true;
		}
		
		
		if (y%2 == 0) {
			if (t)
				Rbad01[x] = true;
			else
				Rbad10[x] = true;
		} else {
			if (t)
				Rbad10[x] = true;
			else
				Rbad01[x] = true;
		}
		if (x%2 == 0) {
			if (t) {
				Cbad01[y] = true;
			} else {
				Cbad10[y] = true;
			}
		} else {
			if (t) {
				Cbad10[y] = true;
			} else {
				Cbad01[y] = true;
			}
		}
	}
	int cnt_r = 0, cnt_c = 0;
	int R = 1, C = 1;
	
	sort(rows.begin(), rows.end());
	for(int i = 0 ; i < rows.size(); i ++) {
		if (i == 0 || rows[i] != rows[i-1]) {
			cnt_r++;
			R = 1ll*R*(2-Rbad01[rows[i]]-Rbad10[rows[i]])%M;
		}
	}
	sort(cols.begin(), cols.end());
	for(int i = 0 ; i < cols.size(); i ++) {
		if (i == 0 || cols[i] != cols[i-1]) {
			cnt_c++;
			C = 1ll*C*(2-Cbad01[cols[i]]-Cbad10[cols[i]])%M;
		}
	}
	R = 1ll*R*my_pow(2, n-cnt_r)%M;
	C = 1ll*C*my_pow(2, m-cnt_c)%M;
	cout << mod(0ll+R+C-(!bad0)-(!bad1)) << endl;
}

// check MAXN
int32_t main() {
	fastIO;
	solve();
	
	return 0;
}

Compilation message (stderr)

plusminus.cpp: In function 'void solve()':
plusminus.cpp:91:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |  for(int i = 0 ; i < rows.size(); i ++) {
      |                  ~~^~~~~~~~~~~~~
plusminus.cpp:98:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |  for(int i = 0 ; i < cols.size(); i ++) {
      |                  ~~^~~~~~~~~~~~~

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