Submission #388214

#	Time	Username	Problem	Language	Result	Execution time	Memory
388214		negar_a	Plus Minus (BOI17_plusminus)	C++14	100 / 100	524 ms	37028 KiB

plusminus

//!yrt tsuj uoy srettam gnihton no emoc
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define pii pair <int, int>
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define F first
#define S second

vector <int> r, c;
map <int, vector <int>> row, col;
map <int, map <int, int>> mat;
ll ans = 0, mod = 1e9 + 7;

ll pw(ll a, ll b){
	ll res = 1;
	while(b){
		if(b & 1){
			res = (res * a) % mod;
		}
		a = (a * a) % mod;
		b /= 2;
	}
	return res % mod;
}

int main(){
	fast_io;
	int n, m, k;
	cin >> n >> m >> k;
	for(int i = 0; i < k; i ++){
		char ch;
		int x, y;
		cin >> ch >> x >> y;
		row[x].pb(y);
		col[y].pb(x);
		mat[x][y] = (ch == '+') - (ch == '-');
		r.pb(x); c.pb(y);
	}
	sort(r.begin(), r.end());
	sort(c.begin(), c.end());
	r.resize(distance(r.begin(), unique(r.begin(), r.end())));
	c.resize(distance(c.begin(), unique(c.begin(), c.end())));
	//fact! : ya satr ha yeki dar mioonan ya sootoon ha!
	bool f1 = true, f2 = true;
	int v1 = -1;
	for(int i : c){
		set <int> x;
		for(int j : col[i]){
			x.insert(((i + j) & 1) ^ (mat[j][i] == 1));
		}
		if((int)x.size() >= 2){
			f1 = false;	
		}
	}
	for(int i : r){
		set <int> x;
		for(int j : row[i]){
			x.insert(((i + j) & 1) ^ (mat[i][j] == 1));
		}
		if((int)x.size() >= 2){
			f2 = false;	
		}
	}
	int x = r.size(), y = c.size();
	if(f1){
//		cout << "f1!" << endl;
		ans += pw(2, m - y);
		ans %= mod;
	}
	if(f2){
//		cout << "f2!" << endl;
		ans += pw(2, n - x);
		ans %= mod;
	}
	if(f2 && f1){
//		cout << "f3!" << endl;
		ans --;
	}
	if(k == 0){
		ans --;
	}
	ans = (ans + mod) % mod;
	cout << ans;
	
	return 0;
}

Compilation message (stderr)

plusminus.cpp: In function 'int main()':
plusminus.cpp:50:6: warning: unused variable 'v1' [-Wunused-variable]
   50 |  int v1 = -1;
      |      ^~

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