Submission #896538

#TimeUsernameProblemLanguageResultExecution timeMemory
896538borisAngelovBeautiful row (IZhO12_beauty)C++17
100 / 100
1860 ms231356 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 20; const int maxMask = (1 << maxn); int n; int a[maxn + 5]; bool areNeighbours[maxn + 5][maxn + 5]; long long dp[maxMask + 5][maxn + 5]; bool bl[maxMask + 5][maxn + 5]; int cnt2(int x) { int res = 0; while (x != 0) { if (x % 2 == 1) { ++res; } x /= 2; } return res; } int cnt3(int x) { int res = 0; while (x != 0) { if (x % 3 == 1) { ++res; } x /= 3; } return res; } bool check(int x, int y) { int x2 = cnt2(x); int x3 = cnt3(x); int y2 = cnt2(y); int y3 = cnt3(y); return x2 == y2 || x3 == y3; } long long f(int mask, int last) { if (mask == (1 << n) - 1) { return 1; } if (bl[mask][last] == true) { return dp[mask][last]; } bl[mask][last] = true; long long result = 0; for (int i = 0; i < n; ++i) { if ((mask & (1 << i)) == 0 && areNeighbours[i][last] == true) { result += f((mask | (1 << i)), i); } } return dp[mask][last] = result; } void fastIO() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); } int main() { fastIO(); cin >> n; for (int i = 0; i < n; ++i) { cin >> a[i]; } for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (i != j && check(a[i], a[j]) == true) { areNeighbours[i][j] = true; } } } long long ans = 0; for (int i = 0; i < n; ++i) { ans += f((1 << i), i); } cout << ans << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...