Submission #477631

#	Time	Username	Problem	Language	Result	Execution time	Memory
477631		lovrot	Plus Minus (BOI17_plusminus)	C++11	100 / 100	113 ms	8628 KiB

plusminus

#include <bits/stdc++.h> 

#define X first
#define Y second
#define ll long long 

using namespace std; 

const int MOD = 1000000007; 

int mult(ll x, ll y){ 
	return (ll) ((x % MOD) * (y % MOD)) % MOD;
}

int power(int x, int exp){ 
	int out = 1;
	while(exp){ 
		if(exp & 1)
			out = mult(out, x);

		x = mult(x, x);

		exp /= 2;
	}
	return out;
}

map<int, bool> m; 

int count(vector< pair<int, bool> > &r, vector< pair<int, bool> > &s, int rn, int sn, int n){ 
	m.clear();

	for(int i = 0; i < n; i ++){ 
		int x = r[i].X;
		int y = s[i].X;

		bool sign = r[i].Y;

		bool should; 

		if(!(x & 1)) should = sign; 
		else should = !sign;

		if(!m.count(y)) m[y] = should;
		else if (m[y] != should)	
			return 0;
	}

	return power(2, sn - m.size());
}

int main(){ 
	ios_base::sync_with_stdio(false);

	int rn, sn, n;

	cin >> rn >> sn;

	cin >> n; 

	bool board1 = true;
	bool board2 = true;

	vector<pair< int, bool >> r, s; 

	for(int i = 0; i < n; i ++){ 
		int x, y; 
		char c;

		cin >> c >> x >> y; x--; y--; 

		bool sign = (c == '+');

		board1 &= (!(!(x & 1) ^ !(y & 1)) == sign);
		board2 &= (!(!(x & 1) ^ !(y & 1)) == !sign);		
		
		r.push_back({x, sign});
		s.push_back({y, sign});	
	}
	//cout << "check: "<< (pow(2, 3) == 8) << "\n";
	//cout << count(r, s, rn, sn, n) << ' ' << count(s, r, sn, rn, n) << ' ' <<  board1 << ' ' << board2;
	//cout << "\n" << char(254) << "\n";

	cout << (ll) (count(r, s, rn, sn, n) + count(s, r, sn, rn, n) - board1 - board2) % MOD << "\n";

	//cout << power(2, 64);
	return 0;
}

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