Submission #2752609


Source Code Expand

#include <algorithm>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
using I = pair<int, int>;

/* clang-format off */
template <class T, size_t D> struct _vec { using type = vector<typename _vec<T, D - 1>::type>; };
template <class T> struct _vec<T, 1> { using type = vector<T>; };
template <class T, size_t D> using vec = typename _vec<T, D>::type;
template <class T> vector<T> make_v(size_t size, const T& init) { return vector<T>(size, init); }
template <class... Ts> auto make_v(size_t size, Ts... rest) { return vector<decltype(make_v(rest...))>(size, make_v(rest...)); }
/* clang-format on */

const int N = 5;
const ll MOD = 1e9 + 7;

int main() {
  vec<int, 2> x = make_v(N, N, 0);
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      cin >> x[i][j];
    }
  }
  bool valid = true;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N - 2; j++) {
      int a = x[i][j], b = x[i][j + 1], c = x[i][j + 2];
      if (a && b && c && (b - a) * (c - b) > 0) {
        valid = false;
      }
    }
  }
  for (int j = 0; j < N; j++) {
    for (int i = 0; i < N - 2; i++) {
      int a = x[i][j], b = x[i + 1][j], c = x[i + 2][j];
      if (a && b && c && (b - a) * (c - b) > 0) {
        valid = false;
      }
    }
  }
  if (!valid) {
    cout << 0 << endl;
    return 0;
  }
  set<int> exists;
  vector<I> ps;
  vec<int, 2> mp = make_v(N, N, -1);
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if (x[i][j] > 0) {
        exists.insert(x[i][j]);
      } else {
        mp[i][j] = ps.size();
        ps.push_back(I(i, j));
      }
    }
  }
  vector<int> nums;
  for (int i = 1; i <= 25; i++) {
    if (!exists.count(i)) nums.push_back(i);
  }
  auto get = [&](int m, int i, int j) {
    int id = mp[i][j];
    if (id < 0) return x[i][j];
    return ((m >> id) & 1) ? 0 : 100;
  };
  int P = ps.size();
  vector<ll> dp(1 << P, 0);
  dp[0] = 1;
  for (int m = 0; m < (1 << P) - 1; m++) {
    int b = __builtin_popcount(m);
    int n = nums[b];
    for (int i = 0; i < P; i++) {
      if ((m >> i) & 1) continue;
      int y, x;
      tie(y, x) = ps[i];
      bool can = true;
      if (0 < y && y < N - 1) {
        can &= ((get(m, y - 1, x) < n) + (get(m, y + 1, x) < n)) != 1;
      }
      if (0 < x && x < N - 1) {
        can &= ((get(m, y, x - 1) < n) + (get(m, y, x + 1) < n)) != 1;
      }
      if (can) {
        (dp[m | (1 << i)] += dp[m]) %= MOD;
      }
    }
  }
  cout << dp.back() << endl;
  return 0;
}

Submission Info

Submission Time
Task D - 25個の整数
User kroton
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2727 Byte
Status WA
Exec Time 152 ms
Memory 8448 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 0 / 30 0 / 70
Status
AC × 4
AC × 10
WA × 9
AC × 10
WA × 19
Set Name Test Cases
Sample sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt
Subtask1 sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, test-1-01.txt, test-1-02.txt, test-1-03.txt, test-1-04.txt, test-1-05.txt, test-1-06.txt, test-1-07.txt, test-1-08.txt, test-1-09.txt, test-1-10.txt, test-1-11.txt, test-1-12.txt, test-1-13.txt, test-1-14.txt, test-1-15.txt
Subtask2 sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, test-1-01.txt, test-1-02.txt, test-1-03.txt, test-1-04.txt, test-1-05.txt, test-1-06.txt, test-1-07.txt, test-1-08.txt, test-1-09.txt, test-1-10.txt, test-1-11.txt, test-1-12.txt, test-1-13.txt, test-1-14.txt, test-1-15.txt, test-2-01.txt, test-2-02.txt, test-2-03.txt, test-2-04.txt, test-2-05.txt, test-2-06.txt, test-2-07.txt, test-2-08.txt, test-2-09.txt, test-2-10.txt
Case Name Status Exec Time Memory
sample-01.txt AC 1 ms 256 KB
sample-02.txt AC 1 ms 256 KB
sample-03.txt AC 1 ms 256 KB
sample-04.txt AC 1 ms 256 KB
test-1-01.txt AC 1 ms 256 KB
test-1-02.txt WA 1 ms 256 KB
test-1-03.txt AC 1 ms 256 KB
test-1-04.txt WA 1 ms 256 KB
test-1-05.txt WA 1 ms 256 KB
test-1-06.txt WA 1 ms 256 KB
test-1-07.txt AC 1 ms 256 KB
test-1-08.txt WA 1 ms 256 KB
test-1-09.txt WA 1 ms 256 KB
test-1-10.txt AC 1 ms 256 KB
test-1-11.txt AC 1 ms 256 KB
test-1-12.txt WA 1 ms 256 KB
test-1-13.txt AC 1 ms 256 KB
test-1-14.txt WA 1 ms 256 KB
test-1-15.txt WA 1 ms 256 KB
test-2-01.txt WA 5 ms 512 KB
test-2-02.txt WA 2 ms 256 KB
test-2-03.txt WA 2 ms 256 KB
test-2-04.txt WA 9 ms 768 KB
test-2-05.txt WA 17 ms 1280 KB
test-2-06.txt WA 151 ms 8448 KB
test-2-07.txt WA 146 ms 8448 KB
test-2-08.txt WA 145 ms 8448 KB
test-2-09.txt WA 152 ms 8448 KB
test-2-10.txt WA 144 ms 8448 KB