Submission #1413514


Source Code Expand

#include <iostream>
#define REP(i, a, n) for(int i = ((int) a); i < ((int) n); i++)
#define MOD 1000000007
using namespace std;

int X[25], P[25];
int dp[1 << 25];

bool ok(int s, int p) {
  int y = p / 5, x = p % 5;
  bool f1 = y > 0 && (s & (1 << ((y - 1) * 5 + x)));
  bool f2 = y < 4 && (s & (1 << ((y + 1) * 5 + x)));
  bool f3 = x > 0 && (s & (1 << (y * 5 + (x - 1))));
  bool f4 = x < 4 && (s & (1 << (y * 5 + (x + 1))));
  if(0 < y && y < 4 && f1 ^ f2) return false;
  if(0 < x && x < 4 && f3 ^ f4) return false;
  return true;
}

int dfs(int s, int n) {
  if(dp[s] >= 0) return dp[s];
  if(n == 25) return dp[s] = 1LL;

  int ret = 0;
  REP(i, 0, 25) {
    if(s & (1 << i)) continue;
    if(P[n] != -1 && P[n] != i) continue;
    if(ok(s, i)) (ret += dfs(s | (1 << i), n + 1)) %= MOD;
  }

  return dp[s] = ret;
}

int main(void) {
  REP(i, 0, 25) P[i] = -1;
  REP(i, 0, 25) {
    cin >> X[i];
    X[i]--;
    if(X[i] >= 0) P[X[i]] = i;
  }

  REP(i, 0, 1 << 25) dp[i] = -1;
  cout << dfs(0, 0) << endl;

  return 0;
}

Submission Info

Submission Time
Task D - 25個の整数
User kshinya
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1074 Byte
Status AC
Exec Time 400 ms
Memory 131328 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 39 ms 131328 KB
sample-02.txt AC 201 ms 131328 KB
sample-03.txt AC 39 ms 131328 KB
sample-04.txt AC 39 ms 131328 KB
test-1-01.txt AC 39 ms 131328 KB
test-1-02.txt AC 39 ms 131328 KB
test-1-03.txt AC 39 ms 131328 KB
test-1-04.txt AC 39 ms 131328 KB
test-1-05.txt AC 39 ms 131328 KB
test-1-06.txt AC 40 ms 131328 KB
test-1-07.txt AC 39 ms 131328 KB
test-1-08.txt AC 39 ms 131328 KB
test-1-09.txt AC 39 ms 131328 KB
test-1-10.txt AC 39 ms 131328 KB
test-1-11.txt AC 39 ms 131328 KB
test-1-12.txt AC 41 ms 131328 KB
test-1-13.txt AC 39 ms 131328 KB
test-1-14.txt AC 40 ms 131328 KB
test-1-15.txt AC 40 ms 131328 KB
test-2-01.txt AC 50 ms 131328 KB
test-2-02.txt AC 86 ms 131328 KB
test-2-03.txt AC 40 ms 131328 KB
test-2-04.txt AC 48 ms 131328 KB
test-2-05.txt AC 148 ms 131328 KB
test-2-06.txt AC 399 ms 131328 KB
test-2-07.txt AC 123 ms 131328 KB
test-2-08.txt AC 227 ms 131328 KB
test-2-09.txt AC 400 ms 131328 KB
test-2-10.txt AC 334 ms 131328 KB