#include<bits/stdc++.h>
#define ll long long
using namespace std;
int const N = 1 << 23;
int n;
ll a[25], dp[N][25];
ll ans;
bool check1(int x, int y) {
int r1 = 0, r2 = 0;
while(x) {
r1 += x % 2;
x /= 2;
}
while(y) {
r2 += y % 2;
y /= 2;
}
if(r1 == r2) return true;
return false;
}
bool check2(int x, int y) {
int r1 = 0, r2 = 0;
while(x) {
r1 += (x % 3 == 1);
x /= 3;
}
while(y) {
r2 += (y % 3 == 1);
y /= 3;
}
if(r1 == r2) return true;
return false;
}
main() {
ios::sync_with_stdio(0);
cin.tie();
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
int mask = 1 << n;
mask--;
for(int i = 1; i <= mask; i++) {
for(int j = 0; j < n; j++) {
if(i >> j & 1) {
int x = i ^ (1 << j);
if(!x) {
dp[i][j + 1] = 1;
continue;
}
for(int z = 0; z < n; z++) {
if((x >> z) & 1) {
bool f1 = false, f2 = false;
f1 = check1(a[j + 1], a[z + 1]);
f2 = check2(a[j + 1], a[z + 1]);
if(f1 || f2) dp[i][j + 1] += dp[x][z + 1];
}
}
}
}
}
for(int j = 0; j < n; j++) ans += dp[mask][j + 1];
cout << ans << "\n";
}
Compilation message
beauty.cpp:35:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
35 | main() {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
0 ms |
364 KB |
Output is correct |
| 4 |
Correct |
0 ms |
364 KB |
Output is correct |
| 5 |
Correct |
0 ms |
364 KB |
Output is correct |
| 6 |
Correct |
2 ms |
492 KB |
Output is correct |
| 7 |
Correct |
3 ms |
492 KB |
Output is correct |
| 8 |
Correct |
2 ms |
492 KB |
Output is correct |
| 9 |
Correct |
2 ms |
492 KB |
Output is correct |
| 10 |
Correct |
5 ms |
492 KB |
Output is correct |
| 11 |
Correct |
145 ms |
3632 KB |
Output is correct |
| 12 |
Correct |
140 ms |
3564 KB |
Output is correct |
| 13 |
Correct |
719 ms |
13292 KB |
Output is correct |
| 14 |
Execution timed out |
3078 ms |
45648 KB |
Time limit exceeded |
| 15 |
Halted |
0 ms |
0 KB |
- |
