Submission #132720

#	Time	Username	Problem	Language	Result	Execution time	Memory
132720		youngyojun	Plus Minus (BOI17_plusminus)	C++11	100 / 100	66 ms	3704 KiB

plusminus

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MOD = 1000000007;
const int MAXN = 100055;

ll pw(ll n, ll k) {
	ll r = 1; for(; k; k >>= 1) {
		if(k&1) r = n * r % MOD;
		n = n * n % MOD;
	}
	return r;
}

int O[MAXN];
int A[MAXN], B[MAXN];
bitset<MAXN> C;

ll Ans;
int H, W, N;

void process() {
	iota(O, O+N+1, 0);
	sort(O+1, O+N+1, [&](int a, int b) {
		return A[a] < A[b];
	});

	int cnt = 0;
	for(int s = 1, e; s <= N; cnt++, s = e) {
		for(e = s+1; e <= N && A[O[e]] == A[O[s]]; e++);
		bool isOdd = false, isEven = false;
		for(int oi = s, i, t; oi < e; oi++) {
			i = O[oi];
			t = A[i] + B[i] + (C[i] ? 1 : 0);
			((t&1) ? isOdd : isEven) = true;
		}
		if(isOdd && isEven) return;
	}
	Ans += pw(2, H-cnt);
	if(MOD <= Ans) Ans -= MOD;
}

void minusOne() {
	bool isOdd = false, isEven = false;
	for(int i = 1, t; i <= N; i++) {
		t = A[i] + B[i] + (C[i] ? 1 : 0);
		((t&1) ? isOdd : isEven) = true;
	}
	if(isOdd != isEven) Ans--;
	if(Ans < 0) Ans = MOD-1;
}

int main() {
	scanf("%d%d%d", &H, &W, &N);
	for(int i = 1; i <= N; i++) {
		char c;
		scanf(" %c%d%d", &c, &A[i], &B[i]);
		C[i] = '+' == c;
	}
	if(!N) {
		cout << (pw(2, H) + pw(2, W) - 2) % MOD << endl;
		return 0;
	}

	process();
	swap(H, W);
	for(int i = 1; i <= N; i++) swap(A[i], B[i]);
	process();
	
	minusOne();

	cout << Ans << endl;
	return 0;
}

Compilation message (stderr)

plusminus.cpp: In function 'int main()':
plusminus.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &H, &W, &N);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
plusminus.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c%d%d", &c, &A[i], &B[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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