제출 #1357768

#제출 시각아이디문제언어결과실행 시간메모리
1357768retr0foxxPlus Minus (BOI17_plusminus)C++20
0 / 100
2 ms4932 KiB
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

#define int long long 
#define MOD (int)(1e9+7)
#define pii std::pair<int, int>
#define MAXK 200000

int powmod(int x, int p)
{
	int res = 1;
	while (p)
	{
		if (p & 1)
			res = res*x % MOD;
		
		x = x*x % MOD;
		p /= 2;
	}
	return res;
}

struct info_t
{
	pii pos;
	char value;
};

info_t data[MAXK+5];
int sort[2][MAXK+5];
int n, m, k;

int count_colternate()
{
	int column_count = k > 0;
	int consistent = 1;
	for (int i = 2; i <= k; ++i)
	{
		int idx = sort[1][i], pvidx = sort[1][i-1];
		pii &pos = data[idx].pos;
		pii &pvpos = data[pvidx].pos;
		consistent = consistent && (pos.second != pvpos.second || ((pos.first - pvpos.first) & 1 ? data[idx].value != data[pvidx].value : data[idx].value == data[pvidx].value));
		column_count += pos.second != pvpos.second;
	}
	if (!consistent)
		return 0;
	
	return powmod(2, m - column_count);
}

int count_rowternate()
{
	int row_count = k > 0;
	int consistent = 1;
	for (int i = 2; i <= k; ++i)
	{
		int idx = sort[0][i], pvidx = sort[0][i-1];
		pii &pos = data[idx].pos;
		pii &pvpos = data[pvidx].pos;
		consistent = consistent && (pos.first != pvpos.first || ((pos.second - pvpos.second) & 1 ? data[idx].value != data[pvidx].value : data[idx].value == data[pvidx].value));
		row_count += pos.first != pvpos.first;
	}
	if (!consistent)
		return 0;

	return powmod(2, n - row_count);
}

signed main()
{
	std::cin >> n >> m >> k;
	
	for (int i = 1; i <= k; ++i)
	{
		char value;
		std::cin >> value >> data[i].pos.first >> data[i].pos.second;
		data[i].value = value == '+' ? 1 : -1;
		
		sort[0][i] = sort[1][i] = i;
	}
	
	std::sort(sort[0]+1, sort[0]+1+k, [](const int &i, const int &j){ return data[i].pos < data[j].pos; });
	std::sort(sort[1]+1, sort[1]+1+k, [](const int &i, const int &j){ return pii(data[i].pos.second, data[i].pos.first) < pii(data[i].pos.second, data[i].pos.first); });
		
	int res = count_colternate() + count_rowternate();
	int consistent[2] = {1,1};
	
	for (int i = 1; i <= k; ++i)
	{
		info_t &cur = data[i];
		if ((cur.pos.first + cur.pos.second) & 1)
		{
			consistent[0] = consistent[0] && cur.value == 1;
			consistent[1] = consistent[1] && cur.value == -1;
		}
		else
		{
			consistent[0] = consistent[0] && cur.value == -1;
			consistent[1] = consistent[1] && cur.value == 1;
		}
	}
	res -= consistent[0] + consistent[1];
	std::cout << res << "\n";
	return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…