oj.uz

답안 #404801

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
404801 2021-05-15T03:11:13 Z rama_pang Plus Minus (BOI17_plusminus) C++17
100 / 100
 140 ms 11716 KB 
#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int N, M, K;
  cin >> N >> M >> K;

  // Solution:
  // Note that, if there is a cell (a, b) == (a + 1, b),
  // and  acell (c, d) == (c, d + 1), it is impossible.
  //
  // Proof:
  // If (a, b) == (a + 1, b), then (a, x) == (a + 1, x)
  // for all x, and if their b's parity is different they
  // have different signs. So, if (a, b) == (a + 1, b),
  // this implies (c, d) == (c + 1, d), (c, d) == (c, d +1).
  // However, we cannot have 3 equal signs in 2 * 2 square.
  //
  // If there is (a, b) == (a + 1, b), then that means
  // all rows have alternating signs (and we can ignore columns
  // condition). So the answer is 2^{free_row} for this case.
  //
  // Thus, we only need to keep track whether the row and column
  // is free, as well as the checkerboard pattern.
  //
  // Time complexity: O(K log K).

  const int mod = 1e9 + 7;
  const auto power = [&](int a, int x) {
    int z = 1;
    while (x) {
      if (x & 1) z = 1ll * z * a % mod;
      a = 1ll * a * a % mod;
      x /= 2;
    }
    return z;
  };

  map<int, int> R, C;
  bool freeRow = true;
  bool freeCol = true;
  bool checkerBoard1 = true;
  bool checkerBoard2 = true;

  while (K--) {
    char ch;
    cin >> ch;
    int t = ch == '+' ? 1 : -1;
    int r, c;
    cin >> r >> c;

    // If in a row, sign is not alternating, then row is dependent on column
    freeRow &= R[r] == 0 || R[r] == t * (c % 2 == 0 ? 1 : -1); R[r] = t * (c % 2 == 0 ? 1 : -1);

    // If in a column, sign is not alternating, then column is dependent on row
    freeCol &= C[c] == 0 || C[c] == t * (r % 2 == 0 ? 1 : -1); C[c] = t * (r % 2 == 0 ? 1 : -1);

    checkerBoard1 &= (t * ((r + c) % 2 == 0 ? 1 : -1)) == +1;
    checkerBoard2 &= (t * ((r + c) % 2 == 0 ? 1 : -1)) == -1;
  }

  int ans = 0;
  ans += freeRow ? power(2, N - R.size()) : 0;
  ans += freeCol ? power(2, M - C.size()) : 0;
  ans -= freeRow && freeCol && checkerBoard1;
  ans -= freeRow && freeCol && checkerBoard2;
  ans %= mod;

  cout << ans << '\n';
  return 0;
}

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 312 KB Output is correct

Subtask #2
42.0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 312 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 61 ms 1276 KB Output is correct
17 Correct 61 ms 1220 KB Output is correct
18 Correct 62 ms 1348 KB Output is correct
19 Correct 71 ms 1264 KB Output is correct
20 Correct 68 ms 1260 KB Output is correct

Subtask #3
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 312 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 61 ms 1276 KB Output is correct
17 Correct 61 ms 1220 KB Output is correct
18 Correct 62 ms 1348 KB Output is correct
19 Correct 71 ms 1264 KB Output is correct
20 Correct 68 ms 1260 KB Output is correct
21 Correct 119 ms 7284 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 115 ms 7268 KB Output is correct
24 Correct 116 ms 7252 KB Output is correct
25 Correct 119 ms 7220 KB Output is correct
26 Correct 113 ms 9832 KB Output is correct
27 Correct 128 ms 9820 KB Output is correct
28 Correct 110 ms 9912 KB Output is correct
29 Correct 132 ms 9920 KB Output is correct
30 Correct 140 ms 11716 KB Output is correct