Submission #1370294
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)--)
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 |
100 |
Code Size |
2038 Byte |
Status |
AC |
Exec Time |
3302 ms |
Memory |
131456 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Score / Max Score |
0 / 0 |
30 / 30 |
70 / 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 |
688 ms |
131328 KB |
sample-02.txt |
AC |
354 ms |
131328 KB |
sample-03.txt |
AC |
364 ms |
131328 KB |
sample-04.txt |
AC |
303 ms |
131200 KB |
test-1-01.txt |
AC |
608 ms |
131328 KB |
test-1-02.txt |
AC |
629 ms |
131328 KB |
test-1-03.txt |
AC |
729 ms |
131328 KB |
test-1-04.txt |
AC |
607 ms |
131328 KB |
test-1-05.txt |
AC |
373 ms |
131328 KB |
test-1-06.txt |
AC |
877 ms |
131328 KB |
test-1-07.txt |
AC |
929 ms |
131328 KB |
test-1-08.txt |
AC |
509 ms |
131328 KB |
test-1-09.txt |
AC |
739 ms |
131328 KB |
test-1-10.txt |
AC |
312 ms |
131328 KB |
test-1-11.txt |
AC |
325 ms |
131328 KB |
test-1-12.txt |
AC |
700 ms |
131328 KB |
test-1-13.txt |
AC |
335 ms |
131328 KB |
test-1-14.txt |
AC |
613 ms |
131328 KB |
test-1-15.txt |
AC |
1045 ms |
131328 KB |
test-2-01.txt |
AC |
2148 ms |
131328 KB |
test-2-02.txt |
AC |
1477 ms |
131328 KB |
test-2-03.txt |
AC |
1344 ms |
131328 KB |
test-2-04.txt |
AC |
1754 ms |
131328 KB |
test-2-05.txt |
AC |
1995 ms |
131328 KB |
test-2-06.txt |
AC |
2933 ms |
131328 KB |
test-2-07.txt |
AC |
3144 ms |
131456 KB |
test-2-08.txt |
AC |
3302 ms |
131328 KB |
test-2-09.txt |
AC |
2717 ms |
131328 KB |
test-2-10.txt |
AC |
3183 ms |
131328 KB |