Submission #434064


Source Code Expand

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)

using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef pair<int, int> PI;
const ll mod = 1e9 + 7;

int x[5][5];



ll rec(int p, int up[5], int obl, int used) {
  if(p == 25) {
    return 1;
  }
  //cout << "p=" << p << hex << "obl= " << obl << " used=" << used << endl;
  int c = p / 5;
  int d = p % 5;
  // decides what is x[c][d]
  ll s = 0;
  int lo = 1, hi = 25;
  if (d >= 2) {
    if (up[d - 2] > up[d - 1]) {
      lo = max(lo, up[d - 1] + 1);
    }
    if (up[d - 2] < up[d - 1]) {
      hi = min(hi, up[d - 1] - 1);
    }
  }
  if (c >= 2) {
    if (obl & (1 << d)) { // must not be bigger than up[d]
      hi = min(hi, up[d] - 1);
    } else {
      lo = max(lo, up[d] + 1);
    }
  }
  if (x[c][d] >= 1) {
    if (lo > x[c][d] || x[c][d] > hi) {
      return 0;
    }
    int w = x[c][d] - 1;
    int ou = up[d];
    up[d] = x[c][d];
    int newobl = obl & ~(1 << d);
    if (ou < up[d]) {
      newobl |= 1 << d;
    }
    ll r = rec(p + 1, up, newobl, used);
    up[d] = ou;
    return r;
  }
  REP(i, lo - 1, hi) {
    if ((used & (1 <<i)) == 0) {
      int ou = up[d];
      up[d] = i + 1;
      int newobl = obl & ~(1 << d);
      if (ou < up[d]) {
	newobl |= 1 << d;
      }
      ll r = rec(p + 1, up, newobl, used | (1 << i));
      up[d] = ou;
      s += r;
      s %= mod;
    }
  }
  return s;
  
}


int main(void){
  int u = 0;
  REP(i, 0, 5) {
    REP(j, 0, 5) {
      cin >> x[i][j];
      if (x[i][j] >= 1) {
	u |= 1 << (x[i][j] - 1);
      }
    }
  }
  int up[5]={};
  int res = rec(0, up, 0, u);
  cout << res << endl;
}

Submission Info

Submission Time
Task D - 25個の整数
User kobae964
Language C++ (GCC 4.9.2)
Score 30
Code Size 2159 Byte
Status TLE
Exec Time 5034 ms
Memory 924 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 30 / 30 0 / 70
Status
AC × 4
AC × 19
AC × 20
TLE × 9
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 25 ms 924 KB
sample-02.txt AC 31 ms 796 KB
sample-03.txt AC 25 ms 676 KB
sample-04.txt AC 25 ms 924 KB
test-1-01.txt AC 25 ms 916 KB
test-1-02.txt AC 25 ms 792 KB
test-1-03.txt AC 25 ms 792 KB
test-1-04.txt AC 25 ms 924 KB
test-1-05.txt AC 26 ms 920 KB
test-1-06.txt AC 26 ms 796 KB
test-1-07.txt AC 22 ms 796 KB
test-1-08.txt AC 24 ms 804 KB
test-1-09.txt AC 23 ms 676 KB
test-1-10.txt AC 23 ms 800 KB
test-1-11.txt AC 23 ms 672 KB
test-1-12.txt AC 23 ms 924 KB
test-1-13.txt AC 23 ms 920 KB
test-1-14.txt AC 23 ms 796 KB
test-1-15.txt AC 23 ms 744 KB
test-2-01.txt TLE 5031 ms 856 KB
test-2-02.txt TLE 5032 ms 800 KB
test-2-03.txt AC 369 ms 804 KB
test-2-04.txt TLE 5032 ms 864 KB
test-2-05.txt TLE 5033 ms 924 KB
test-2-06.txt TLE 5031 ms 800 KB
test-2-07.txt TLE 5033 ms 800 KB
test-2-08.txt TLE 5034 ms 792 KB
test-2-09.txt TLE 5034 ms 812 KB
test-2-10.txt TLE 5031 ms 800 KB