Submission #1092121

#TimeUsernameProblemLanguageResultExecution timeMemory
1092121juicyBeautiful row (IZhO12_beauty)C++17
100 / 100
819 ms172800 KiB
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "debug.h" #else #define debug(...) 42 #endif int C2(int x) { return __builtin_popcount(x); } int C3(int x) { int cnt = 0; while (x) { cnt += x % 3 == 1; x /= 3; } return cnt; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> a(n); for (int &x : a) { cin >> x; } vector b(n, vector<bool>(n)); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { b[i][j] = C2(a[i]) == C2(a[j]) || C3(a[i]) == C3(a[j]); } } vector dp(n, vector<long long>(1 << n, 0)); for (int i = 0; i < n; ++i) { dp[i][1 << i] = 1; } for (int m = 0; m < 1 << n; ++m) { for (int i = 0; i < n; ++i) { if (dp[i][m]) { for (int j = 0; j < n; ++j) { if (!(m >> j & 1) && b[i][j]) { dp[j][m + (1 << j)] += dp[i][m]; } } } } } long long res = 0; for (int i = 0; i < n; ++i) { res += dp[i][(1 << n) - 1]; } cout << res; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...