Submission #329023

#TimeUsernameProblemLanguageResultExecution timeMemory
329023gustasonBeautiful row (IZhO12_beauty)C++14
100 / 100
863 ms164548 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; ll dp[(1<<20)][20]; bool check(int a, int b) { int bina = __builtin_popcount(a); int binb = __builtin_popcount(b); if (bina == binb) return true; int tera = 0, terb = 0; while(a > 0) { if (a % 3 == 1) tera++; a /= 3; } while(b > 0) { if (b % 3 == 1) terb++; b /= 3; } return tera == terb; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; int a[n]; bool mat[n][n]; for(int i = 0; i < n; i++) { cin >> a[i]; dp[0][i] = 1; } for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { //if (i == j) continue; mat[i][j] = check(a[i], a[j]); } } for(int mask = 0; mask < (1 << n); mask++) { for(int i = 0; i < n; i++) { if (!(mask&(1<<i))) continue; for(int j = 0; j < n; j++) { if (!(mask&(1<<j))) continue; if (!mat[i][j]) continue; dp[mask][i] += dp[mask^(1<<i)][j]; } } } ll ans = 0LL; for(int i = 0; i < n; i++) { ans += dp[(1 << n)-1][i]; } cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...