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 |
|
|
|
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 |