# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
90133 | antimirage | Beautiful row (IZhO12_beauty) | C++14 | 1186 ms | 205976 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>
#define fr first
#define sc second
#define mk make_pair
#define pb emplace_back
#define all(s) s.begin(), s.end()
using namespace std;
const int N = 25;
int n, a[N], sik[N][N];
long long ans, dp[ (1 << 20) + 5 ][N];
main()
{
cin >> n;
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
for (int i = 0; i < n; i++)
{
int c2 = 0, c3 = 0, x = a[i];
while (x){
if (x & 1)
c2++;
x /= 2;
}
x = a[i];
while (x){
if (x % 3 == 1)
c3++;
x /= 3;
}
for (int j = i + 1; j < n; j++)
{
int cc2 = 0, cc3 = 0;
x = a[j];
while (x){
if (x & 1)
cc2++;
x /= 2;
}
x = a[j];
while (x){
if (x % 3 == 1)
cc3++;
x /= 3;
}
if (cc2 == c2 || cc3 == c3)
sik[i][j] = sik[j][i] = 1;
}
}
for (int j = 0; j < n; j++)
dp[1 << j][j] = 1;
for (int mask = 1; mask < (1 << n); mask++)
{
for (int last = 0; last < n; last++)
{
if ( (mask & (1 << last) ) == 0 ) continue;
for (int nxt = 0; nxt < n; nxt++){
if ( ( mask & (1 << nxt) ) || sik[last][nxt] == 0 ) continue;
dp[mask + (1 << nxt)][nxt] += dp[mask][last];
}
}
}
for (int i = 0; i < n; i++)
ans += dp[ (1 << n) - 1 ][i];
cout << ans << endl;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |