oj.uz

Submission #714815

# Submission time Handle Problem Language Result Execution time Memory
714815 2023-03-25T09:59:58 Z ajab_01 Plus Minus (BOI17_plusminus) C++17
0 / 100
 1 ms 340 KB 
#include<bits/stdc++.h>
using namespace std;

#define int long long

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
int c[N] , x[N] , y[N] , n , m , k;
set<pair<int , int> > st , s;
int ch = 1 , flg = 1;

long long power(int a , int b){
	if(!b) return 1;
	long long tmp = power(a , b / 2);
	tmp = tmp * tmp % MOD;
	if(b & 1) tmp = tmp * a % MOD;
	return tmp;
}

int32_t main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m >> k;
	for(int i = 0 ; i < k ; i++){
		char cc;
		cin >> cc >> x[i] >> y[i];
		c[i] = (cc == '+' ? 1 : 0);
	}

	for(int i = 0 ; i < k ; i++){
		auto it = st.lower_bound({x[i] , -1});
		if(it == st.end()){
			st.insert({x[i] , ((y[i] + c[i]) & 1)});
			continue;
		}

		pair<int , int> p = *it;

		if(p.second != ((y[i] + c[i]) & 1)){
			ch = 0;
			break;
		}
	}

	for(int i = 0 ; i < k ; i++){
		auto it = s.lower_bound({y[i] , -1});
		if(it == s.end()){
			s.insert({y[i] , ((x[i] + c[i]) & 1)});
			continue;
		}

		pair<int , int> p = *it;

		if(p.second != ((x[i] + c[i]) & 1)){
			flg = 0;
			break;
		}
	}

	long long ans = power(2 , n - (int)st.size())  * ch + power(2 , m - (int)s.size()) * flg % MOD;
	ans += MOD;
	flg = ch = 1;
	for(int i = 0 ; i < k ; i++){
		if((x[i] + y[i] + c[i]) & 1)
			flg = 0;
		else
			ch = 0;
	}
	cout << (ans - flg - ch) % MOD << '\n';
	return 0;
}

Subtask #1
0 / 12.0

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

Subtask #2
0 / 42.0

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

Subtask #3
0 / 46.0

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