Submission #1066698

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066698		kunzaZa183	Plus Minus (BOI17_plusminus)	C++17	12 / 100	2 ms	604 KiB

plusminus

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
	//cin.tie(0)->sync_with_stdio(0);

	int n,m,k;
	cin>>n>>m>>k;

	//plus = 0, minus = 1

	vector<tuple<int,int,char>> vtiic(k);
	vector<vector<int>> row(n,vector<int>(2,1)),col(m,vector<int>(2,1));
	vector<int> sumr(n),sumc(m);
	for(int i = 0; i < k; i++) {
		auto &[a,b,c] = vtiic[i];
		cin>>c>>a>>b;
		a--,b--;
		if(c=='+') {
			row[a][1 - b%2] = 0;
			col[b][1 - a%2] = 0;
		} else {
			row[a][b%2] = 0;
			col[b][a%2] = 0;
		}
	}

	const int mod = 1e9+7;
	function<int(int, int)> logpow = [&](int a, int b) { 
		if(b==0)
			return 1ll;
		int x = logpow(a,b/2);
		if(b%2==1)
			return x * x % mod * a % mod;
		return x * x % mod;
	};

	for(int i =0; i < n;i++){
		sumr[i] = accumulate(row[i].begin(),row[i].end(),0);
//		cout<<sumr[i]<<'\n';
	}
	for(int i = 0; i < m;i++) {
		sumc[i] = accumulate(col[i].begin(),col[i].end(),0);
//		cout<<sumc[i]<<'\n';
	}
	vector<int> sufrow(n + 1),sufcol(m + 1);
	sufrow[n] = 1,sufcol[m] = 1;
	

	for(int i = n-1;i>=0;i--) {
		sufrow[i] = sufrow[i+1] * sumr[i];
		sufrow[i] %= mod;
	}

	for(int i = m-1;i>=0;i--) {
		sufcol[i] = sufcol[i+1] * sumc[i];
		sufcol[i] %= mod;
		//cout<<sufcol[i]<<" "<<i<<"\n";
	}

	//+even +odd
	vector<int> ok;
	ok.push_back(1);
	ok.push_back(1);


	int small = 0;
	for(int i = 0; i < n - 1;i++) {
		int coef = 0;
		if(i%2==0){
			if(row[i][0] && ok[0] && row[i+1][0])
				coef++;
			if(row[i][1] && ok[1] && row[i+1][1])
				coef++;
		} else {
			if(row[i][0] && row[i+1][0] && ok[1])
				coef++;
			if(row[i][1] && row[i+1][1] && ok[0])
				coef++;
		}

		small += coef * sufrow[i+2] % mod;
		small %= mod;

		if(sumr[i] == 1){
			if(i%2==0) {
				if(row[i][0])
					ok[1] = 0;
				else
					ok[0] = 0;
			} else {
				if(row[i][0])
					ok[0] = 0;
				else
					ok[1] = 0;
			}
		} else if(sumr[i] == 0) {
			ok[0] = 0,ok[1] = 0;
		}
	}

	ok = vector<int>(2,1);
	for(int i = 0; i < m - 1;i++) {
		int coef = 0;
		if(i%2==0){
			if(col[i][0] && col[i+1][0] && ok[1])
				coef++;
			if(col[i][1] && col[i+1][1] && ok[0])
				coef++;
		} else {
			if(col[i][0] && col[i+1][0] && ok[1])
				coef++;
			if(col[i][1] && col[i+1][1] && ok[0])
				coef++;
		}

		small += coef * sufcol[i+2] % mod;
		small %= mod;

		if(sumc[i] == 1){
			if(i%2==0) {
				if(col[i][0])
					ok[1] = 0;
				else
					ok[0] = 0;
			} else {
				if(col[i][0])
					ok[0] = 0;
				else
					ok[1] = 0;
			}
		} else if (sumc[i]==0) {
			ok[0] = 0,ok[1] = 0;
		}
	}

	ok = vector<int>(2,1);
	for(int i = 0; i < k;i++){
		auto [a,b,c] = vtiic[i];
		if((a + b) % 2 == 0) {
			if(c=='+')
				ok[1] = 0;
			else
				ok[0] = 0;
		} else {
			if(c=='+')
				ok[0] = 0;
			else
				ok[1] = 0 ;
		}
	}

	small += accumulate(ok.begin(),ok.end(),0);
	small %= mod;

	cout<<small<<"\n";

//	cout<<"DEBUG\n";
//	for(auto a:sufrow)
//		cout<<a<<"\n";
//	cout<<"\n";
//	for(auto a:sufcol)
//		cout<<a<<"\n";
}

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