Submission #4650151
Source Code Expand
#include "bits/stdc++.h" #define REP(i,n) for(ll i=0;i<ll(n);++i) #define RREP(i,n) for(ll i=ll(n)-1;i>=0;--i) #define FOR(i,m,n) for(ll i=m;i<ll(n);++i) #define RFOR(i,m,n) for(ll i=ll(n)-1;i>=ll(m);--i) #define ALL(v) (v).begin(),(v).end() #define UNIQUE(v) v.erase(unique(ALL(v)),v.end()); #define INF 1000000001ll #define MOD 1000000007ll #define EPS 1e-9 constexpr int dx[8] = { 1,1,0,-1,-1,-1,0,1 }; constexpr int dy[8] = { 0,1,1,1,0,-1,-1,-1 }; using namespace std; using ll = long long; using vi = vector<int>; using vl = vector<ll>; using vvi = vector<vi>; using vvl = vector<vl>; using pii = pair<int, int>; using pll = pair<ll, ll>; template <class T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; } template <class T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; } map<int, pii> mp; vvi v(5, vi(5)); int dfs(vi &dp, int b) { if (dp[b] != -1)return dp[b]; int num = __bultin_popcount(b); int ret = 0; if (mp.count(num + 1)) { int x, y; tie(x, y) = mp[num + 1]; bool ok = true; if (x != 0 && x != 4) { int cnt = 0; int k = (x - 1) * 5 + y; if (b&(1 << k))cnt++; k = (x + 1) * 5 + y; if (b&(1 << k))cnt++; if (cnt & 1)ok = false; } if (y != 0 && y != 4) { int cnt = 0; int k = x * 5 + y - 1; if (b&(1 << k))cnt++; k = x * 5 + y + 1; if (b&(1 << k))cnt++; if (cnt & 1)ok = false; } if (ok) { int k = 5 * x + y; ret += dfs(dp, b | (1 << k)); ret %= MOD; } } else { REP(x, 5)REP(y, 5) { int k = 5 * x + y; if (b&(1 << k) || v[x][y] != 0)continue; bool ok = true; if (x != 0 && x != 4) { int cnt = 0; int k = (x - 1) * 5 + y; if (b&(1 << k))cnt++; k = (x + 1) * 5 + y; if (b&(1 << k))cnt++; if (cnt & 1)ok = false; } if (y != 0 && y != 4) { int cnt = 0; int k = x * 5 + y - 1; if (b&(1 << k))cnt++; k = x * 5 + y + 1; if (b&(1 << k))cnt++; if (cnt & 1)ok = false; } if (ok) { int k = 5 * x + y; ret += dfs(dp, b | (1 << k)); ret %= MOD; } } } return dp[b] = ret; } int main() { cin.tie(0); ios::sync_with_stdio(false); REP(i, 5)REP(j, 5) { cin >> v[i][j]; if (v[i][j] != 0)mp[v[i][j]] = { i,j }; } vi dp(1 << 25, -1); dp.back() = 1; dfs(dp, 0); cout << dp[0] << endl; }
Submission Info
Submission Time | |
---|---|
Task | D - 25個の整数 |
User | etonagisa |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2418 Byte |
Status | CE |
Compile Error
./Main.cpp: In function ‘int dfs(vi&, int)’: ./Main.cpp:33:31: error: ‘__bultin_popcount’ was not declared in this scope int num = __bultin_popcount(b); ^