# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
527664 | theshadow_04 | Beautiful row (IZhO12_beauty) | C++14 | 8 ms | 1868 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.
// annotshy
#include <bits/stdc++.h>
#define Task "beauty"
#define F first
#define S second
using namespace std;
const int maxn = 100005;
int n, a[maxn];
int dp[(1 << 20) + 5][25], match[25][25];
int binary_1(int x) {
int res = 0;
while(x) {
res += (x % 2 == 1);
x /= 2;
}
return res;
}
int ternary_1(int x) {
int res = 0;
while(x) {
res += (x % 3 == 1);
x /= 3;
}
return res;
}
bool ok(int x, int y) {
if(binary_1(x) == binary_1(y)) return 1;
if(ternary_1(x) == ternary_1(y)) return 1;
return 0;
}
void Solve(int Test) {
cin >> n;
for(int i = 1; i <= n; ++ i) cin >> a[i];
for(int i = 1; i <= n; ++ i) {
for(int j = i + 1; j <= n; ++ j) {
match[i][j] = match[j][i] = ok(a[i], a[j]);
}
dp[(1 << (i - 1))][i] = 1;
}
for(int mask = 0; mask < (1 << n); ++ mask) {
for(int i = 1; i <= n; ++ i) {
if(!(mask >> (i - 1) & 1)) continue;
for(int j = 1; j <= n; ++ j) {
if(!match[i][j]) continue;
if(!(mask >> (j - 1) & 1)) continue;
dp[mask][i] += dp[mask ^ (1 << (i - 1))][j];
}
}
}
int res = 0;
for(int i = 1; i <= n; ++ i) res += dp[(1 << n) - 1][i];
cout << res << "\n";
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
if(fopen(Task".in", "r")) {
freopen(Task".in", "r", stdin);
freopen(Task".out", "w", stdout);
}
int test = 1;
// cin >> test;
for(int i = 1; i <= test; ++ i) {
Solve(i);
}
}
/*no pain no gain*/
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |