# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
132717 | youngyojun | Plus Minus (BOI17_plusminus) | C++11 | 2 ms | 256 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
process();
swap(H, W);
for(int i = 1; i <= N; i++) swap(A[i], B[i]);
process();
minusOne();
cout << Ans << endl;
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |