Submission #1685862


Source Code Expand

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
const int MOD = 1000000007;
int A[25];
int fix[26]; // すでに指定されている数字の場所
int dp[1<<25];
vector<int> v;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  FOR(i,0,26) fix[i] = -1;
  FOR(i,0,25) {
    cin >> A[i];
    if(A[i] == 0) v.push_back(i);
    else fix[A[i]] = i;
  }
  // 1,2,3...の順に数字を置いていく
  dp[0] = 1;
  FOR(mask,0,(1<<25)-1) {
    if(dp[mask] <= 0) continue;
    int b = __builtin_popcount(mask) + 1; // 次におく数字
    // 場所がすでに指定されている
    if(fix[b] >= 0) {
      int r = fix[b]; // 場所
      int y = r / 5, x = r % 5; // (y, x)に直す
      // まだ置かれていない
      if((mask & (1 << r)) == 0) {
        // 端っこでない && すでに数字が隣(片方)に置かれていたらだめ
        if(y > 0 && y < 4 && ((mask >> (r - 5)) ^ (mask >> (r + 5))) & 1) continue;
        if(x > 0 && x < 4 && ((mask >> (r - 1)) ^ (mask >> (r + 1))) & 1) continue;
        dp[mask ^ (1 << r)] += dp[mask];
        dp[mask ^ (1 << r)] %= MOD;
      }
    } else {
      // toにおく
      for(int r : v) {
        int y = r / 5, x = r % 5;
        // まだ置かれていない
        if((mask & (1 << r)) == 0) {
          // 端っこでない && すでに数字が隣に置かれていたらだめ
          if(y > 0 && y < 4 && ((mask >> (r - 5)) ^ (mask >> (r + 5))) & 1) continue;
          if(x > 0 && x < 4 && ((mask >> (r - 1)) ^ (mask >> (r + 1))) & 1) continue;
          dp[mask ^ (1 << r)] += dp[mask];
          dp[mask ^ (1 << r)] %= MOD;
        }
      }
    }
  }
  cout << dp[(1<<25)-1] << endl;
  return 0;
}

Submission Info

Submission Time
Task D - 25個の整数
User nenuon
Language C++14 (GCC 5.4.1)
Score 100
Code Size 2121 Byte
Status AC
Exec Time 110 ms
Memory 113280 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 27 ms 12544 KB
sample-02.txt AC 29 ms 20736 KB
sample-03.txt AC 24 ms 256 KB
sample-04.txt AC 27 ms 12544 KB
test-1-01.txt AC 27 ms 12544 KB
test-1-02.txt AC 28 ms 14592 KB
test-1-03.txt AC 28 ms 16640 KB
test-1-04.txt AC 45 ms 69888 KB
test-1-05.txt AC 28 ms 16640 KB
test-1-06.txt AC 28 ms 16640 KB
test-1-07.txt AC 24 ms 2304 KB
test-1-08.txt AC 34 ms 39168 KB
test-1-09.txt AC 27 ms 12544 KB
test-1-10.txt AC 27 ms 12544 KB
test-1-11.txt AC 27 ms 12544 KB
test-1-12.txt AC 29 ms 18688 KB
test-1-13.txt AC 27 ms 12544 KB
test-1-14.txt AC 29 ms 18688 KB
test-1-15.txt AC 31 ms 24832 KB
test-2-01.txt AC 34 ms 33024 KB
test-2-02.txt AC 31 ms 24960 KB
test-2-03.txt AC 33 ms 30976 KB
test-2-04.txt AC 60 ms 113152 KB
test-2-05.txt AC 49 ms 70272 KB
test-2-06.txt AC 86 ms 68224 KB
test-2-07.txt AC 78 ms 92416 KB
test-2-08.txt AC 98 ms 113280 KB
test-2-09.txt AC 80 ms 74624 KB
test-2-10.txt AC 110 ms 78336 KB