oj.uz

Submission #388213

# Submission time Handle Problem Language Result Execution time Memory
388213 2021-04-10T14:44:55 Z negar_a Plus Minus (BOI17_plusminus) C++14
0 / 100
 0 ms 204 KB 
//!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, f3 = 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;	
		}
		if(v1 != -1 && v1 != *x.begin()){
			f3 = false;
		}else{
			v1 = *x.begin();
		}
	}
	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(f3){
//		cout << "f3!" << endl;
		ans --;
	}
	if(k == 0){
		ans --;
	}
	ans = (ans + mod) % mod;
	cout << ans;
	
	return 0;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -