Submission #2753117


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;

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

int main() {
  vector<int> init(N * N);
  for (int i = 0; i < N * N; i++) cin >> init[i], --init[i];
  vector<int> num(N * N, -1), id(N * N, -1), ps;
  for (int i = 0; i < N * N; i++) {
    int n = init[i];
    if (n < 0) {
      id[i] = ps.size();
      ps.push_back(i);
    } else {
      num[n] = i;
    }
  }
  auto at = [&](int mask, int n, int i) {
    if (id[i] >= 0) return ((mask >> id[i]) & 1) == 1;
    return init[i] < n;
  };
  auto check = [&](int mask, int n, int i) {
    int y = i / N, x = i % N;
    if (0 < y && y < N - 1) {
      if (at(mask, n, (y - 1) * N + x) ^ at(mask, n, (y + 1) * N + x)) {
        return false;
      }
    }
    if (0 < x && x < N - 1) {
      if (at(mask, n, y * N + (x - 1)) ^ at(mask, n, y * N + (x + 1))) {
        return false;
      }
    }
    return true;
  };
  int P = ps.size();
  vector<ll> dp(1 << P, 0);
  dp[0] = 1;
  for (int n = 0; n < N * N; n++) {
    int frees = 0;
    for (int m = 0; m < n; m++)
      if (num[m] < 0) frees++;
    vector<ll> ndp(1 << P, 0);
    for (int mask = 0; mask < (1 << P); mask++) {
      if (__builtin_popcount(mask) != frees) continue;
      if (num[n] >= 0) {
        if (check(mask, n, num[n])) {
          (ndp[mask] += dp[mask]) %= MOD;
        }
      } else {
        for (int j = 0; j < P; j++) {
          if ((mask >> j) & 1) continue;
          if (check(mask, n, ps[j])) {
            (ndp[mask | (1 << j)] += dp[mask]) %= MOD;
          }
        }
      }
    }
    dp = ndp;
  }
  cout << dp.back() << endl;
  return 0;
}

Submission Info

Submission Time
Task D - 25個の整数
User kroton
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1874 Byte
Status AC
Exec Time 271 ms
Memory 16764 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 30 / 30 70 / 70
Status
AC × 4
AC × 19
AC × 29
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 AC 1 ms 256 KB
test-1-03.txt AC 1 ms 256 KB
test-1-04.txt AC 1 ms 256 KB
test-1-05.txt AC 1 ms 256 KB
test-1-06.txt AC 1 ms 256 KB
test-1-07.txt AC 1 ms 256 KB
test-1-08.txt AC 1 ms 256 KB
test-1-09.txt AC 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 AC 1 ms 256 KB
test-1-13.txt AC 1 ms 256 KB
test-1-14.txt AC 1 ms 256 KB
test-1-15.txt AC 1 ms 256 KB
test-2-01.txt AC 9 ms 768 KB
test-2-02.txt AC 3 ms 384 KB
test-2-03.txt AC 2 ms 256 KB
test-2-04.txt AC 17 ms 1280 KB
test-2-05.txt AC 33 ms 2304 KB
test-2-06.txt AC 270 ms 16640 KB
test-2-07.txt AC 271 ms 16764 KB
test-2-08.txt AC 265 ms 16640 KB
test-2-09.txt AC 271 ms 16640 KB
test-2-10.txt AC 263 ms 16640 KB