Submission #1370288
Source Code Expand
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
using namespace std;
#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define int long long int
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
typedef pair<int, int> pii;
typedef long long ll;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
constexpr ll INF = 1001001001001001LL;
constexpr ll MOD = 1000000007LL;
int dp[1<<25], pos[26];
bool valid(int bit, int p) {
if(bit >> p & 1) return false;
int x = p/5, y = p%5;
if(x > 0 && x < 4 && ((bit >> (p-5))^(bit >> (p+5))) & 1) return false;
if(y > 0 && y < 4 && ((bit >> (p-1))^(bit >> (p+1))) & 1) return false;
return true;
}
signed main() {
memset(pos, -1, sizeof(pos));
vector<int> v;
rep(i,0,25) {
int n; cin >> n;
if(n) pos[n] = i;
else v.push_back(i);
}
dp[0] = 1;
rep(bit,0,1<<25) {
int i = __builtin_popcount(bit) + 1;
if(pos[i] != -1) {
if(valid(bit, pos[i])) {
int nbit = bit | (1 << pos[i]);
(dp[nbit] += dp[bit]) %= MOD;
}
}
else {
for(auto to : v) {
if(valid(bit, to)) {
int nbit = bit | (1 << to);
(dp[nbit] += dp[bit]) %= MOD;
}
}
}
}
cout << dp[(1<<25)-1] << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
D - 25個の整数 |
User |
tsutaj |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2065 Byte |
Status |
MLE |
Exec Time |
4264 ms |
Memory |
262400 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Score / Max Score |
0 / 0 |
0 / 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 |
MLE |
1063 ms |
262400 KB |
sample-02.txt |
MLE |
432 ms |
262400 KB |
sample-03.txt |
MLE |
442 ms |
262400 KB |
sample-04.txt |
MLE |
363 ms |
262144 KB |
test-1-01.txt |
MLE |
794 ms |
262400 KB |
test-1-02.txt |
MLE |
767 ms |
262400 KB |
test-1-03.txt |
MLE |
948 ms |
262400 KB |
test-1-04.txt |
MLE |
765 ms |
262400 KB |
test-1-05.txt |
MLE |
457 ms |
262400 KB |
test-1-06.txt |
MLE |
1090 ms |
262400 KB |
test-1-07.txt |
MLE |
1193 ms |
262400 KB |
test-1-08.txt |
MLE |
628 ms |
262400 KB |
test-1-09.txt |
MLE |
862 ms |
262400 KB |
test-1-10.txt |
MLE |
375 ms |
262400 KB |
test-1-11.txt |
MLE |
397 ms |
262400 KB |
test-1-12.txt |
MLE |
827 ms |
262400 KB |
test-1-13.txt |
MLE |
407 ms |
262400 KB |
test-1-14.txt |
MLE |
723 ms |
262400 KB |
test-1-15.txt |
MLE |
1259 ms |
262400 KB |
test-2-01.txt |
MLE |
2511 ms |
262400 KB |
test-2-02.txt |
MLE |
1748 ms |
262400 KB |
test-2-03.txt |
MLE |
1681 ms |
262400 KB |
test-2-04.txt |
MLE |
2221 ms |
262400 KB |
test-2-05.txt |
MLE |
2562 ms |
262400 KB |
test-2-06.txt |
MLE |
3587 ms |
262400 KB |
test-2-07.txt |
MLE |
3983 ms |
262400 KB |
test-2-08.txt |
MLE |
4264 ms |
262400 KB |
test-2-09.txt |
MLE |
3324 ms |
262400 KB |
test-2-10.txt |
MLE |
4047 ms |
262400 KB |