Submission #1587810
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define each(i,a) for (auto&& i : a)
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define chmin(x,v) x = min(x, v)
#define chmax(x,v) x = max(x, v)
const ll linf = 1e18;
const int inf = 1e9;
const double eps = 1e-12;
const double pi = acos(-1);
template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
each(x,vec) is >> x;
return is;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
rep(i,vec.size()) {
if (i) os << " ";
os << vec[i];
}
return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector< vector<T> >& vec) {
rep(i,vec.size()) {
if (i) os << endl;
os << vec[i];
}
return os;
}
const ll mod = 1e9+7;
ll add(ll a, ll b) {
if (a + b >= mod) return a + b - mod;
return a + b;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
vector<vector<ll>> m(5, vector<ll>(5)); cin >> m;
vector<P> pos(25, P(-1, -1));
// vector<vector<ll>> nth(5, vector<ll>(5, -1));
rep(y, 5) rep(x, 5) if (m[y][x]) pos[m[y][x]-1] = P(x, y);
ll n = 0;
vector<ll> nth_value;
rep(i, 25) {
if (pos[i].first < 0) {
nth_value.pb(i);
++n;
}
// nth[pos[i].second][pos[i].first] = i;
}
vector<P> nth_pos;
vector<vector<ll>> nth_pos_r(5, vector<ll>(5, -1));
rep(y, 5) rep(x, 5) if (m[y][x] == 0) {
nth_pos_r[y][x] = nth_pos.size();
nth_pos.pb({x, y});
}
vector<ll> dp(1LL<<n, 0);
dp[0] = 1;
auto get = [&](ll f, ll val, ll x, ll y) {
if (x < 0 || x >= 5 || y < 0 || y >= 5) return linf;
if (nth_pos_r[y][x] < 0) return m[y][x]-1 < val ? 1LL : 0LL;
return f & (1LL<<nth_pos_r[y][x]) ? 1LL : 0LL;
};
auto check = [&](ll f, ll val, ll x, ll y) {
if (get(f, val, x-1, y) + get(f, val, x+1, y) == 1) return false;
if (get(f, val, x, y-1) + get(f, val, x, y+1) == 1) return false;
return true;
};
vector<ll> cunt(26, 0);
rep(i, 25) cunt[i+1] = cunt[i] + (pos[i].first < 0);
rep(i, 25) {
rep(j, 1LL<<n) {
if (cunt[i] != __builtin_popcount(j)) continue;
if (dp[j] == 0) continue;
ll val = i;
if (pos[i].first < 0) {
// cout << i << " " << j << endl;
rep(k, n) {
if ((1LL<<k) & j) continue;
ll x, y; tie(x, y) = nth_pos[k];
if (!check(j, val, x, y)) continue;
ll nj = j | (1LL<<k);
dp[nj] = add(dp[nj], dp[j]);
}
}
else {
ll x, y; tie(x, y) = pos[i];
if (!check(j, val, x, y)) dp[j] = 0;
}
}
}
cout << dp[(1LL<<n)-1] << endl;
}
Submission Info
Submission Time |
|
Task |
D - 25個の整数 |
User |
drafear |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
3421 Byte |
Status |
AC |
Exec Time |
156 ms |
Memory |
8448 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 |
1 ms |
256 KB |
sample-02.txt |
AC |
1 ms |
256 KB |
sample-03.txt |
AC |
1 ms |
256 KB |
sample-04.txt |
AC |
1 ms |
256 KB |
test-1-01.txt |
AC |
1 ms |
256 KB |
test-1-02.txt |
AC |
1 ms |
256 KB |
test-1-03.txt |
AC |
1 ms |
256 KB |
test-1-04.txt |
AC |
1 ms |
256 KB |
test-1-05.txt |
AC |
1 ms |
256 KB |
test-1-06.txt |
AC |
1 ms |
256 KB |
test-1-07.txt |
AC |
1 ms |
256 KB |
test-1-08.txt |
AC |
1 ms |
256 KB |
test-1-09.txt |
AC |
1 ms |
256 KB |
test-1-10.txt |
AC |
1 ms |
256 KB |
test-1-11.txt |
AC |
1 ms |
256 KB |
test-1-12.txt |
AC |
1 ms |
256 KB |
test-1-13.txt |
AC |
1 ms |
256 KB |
test-1-14.txt |
AC |
1 ms |
256 KB |
test-1-15.txt |
AC |
1 ms |
256 KB |
test-2-01.txt |
AC |
5 ms |
512 KB |
test-2-02.txt |
AC |
2 ms |
384 KB |
test-2-03.txt |
AC |
1 ms |
256 KB |
test-2-04.txt |
AC |
8 ms |
768 KB |
test-2-05.txt |
AC |
16 ms |
1280 KB |
test-2-06.txt |
AC |
137 ms |
8448 KB |
test-2-07.txt |
AC |
121 ms |
8448 KB |
test-2-08.txt |
AC |
132 ms |
8448 KB |
test-2-09.txt |
AC |
126 ms |
8448 KB |
test-2-10.txt |
AC |
156 ms |
8448 KB |