# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1112209 | Kirill22 | Beautiful row (IZhO12_beauty) | C++17 | 796 ms | 172880 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h"
using namespace std;
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<vector<int>> g(n, vector<int> (n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (__builtin_popcount(a[i]) == __builtin_popcount(a[j])) {
g[i][j] = 1;
}
int x = a[i], y = a[j], s = 0;
while (x > 0) {
s += x % 3 == 1;
x /= 3;
}
while (y > 0) {
s -= y % 3 == 1;
y /= 3;
}
if (s == 0) {
g[i][j] = 1;
}
}
}
vector<vector<long long>> dp(n, vector<long long> (1 << n));
for (int i = 0; i < n; i++) {
dp[i][1 << i] = 1;
}
for (int msk = 0; msk < (1 << n); msk++) {
for (int v = 0; v < n; v++) {
for (int u = 0; u < n; u++) {
if (msk >> v & 1) {
if (!(msk >> u & 1)) {
if (g[v][u]) {
dp[u][msk + (1 << u)] += dp[v][msk];
}
}
}
}
}
}
long long ans = 0;
for (int v = 0; v < n; v++) {
ans += dp[v].back();
}
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |