# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
876956 | boris_mihov | Beautiful row (IZhO12_beauty) | C++17 | 1 ms | 456 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 <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
typedef long long llong;
const int MAXN = 20 + 10;
const int MAXB = (1 << 20) + 10;
int n;
int a[MAXN];
int binary[MAXN];
int ternary[MAXN];
llong dp[MAXN][MAXN];
bool bl[MAXN][MAXN];
llong f(int mask, int last)
{
if (__builtin_popcount(mask) == n)
{
return 1;
}
if (bl[mask][last])
{
return dp[mask][last];
}
bl[mask][last] = true;
for (int next = 1 ; next <= n ; ++next)
{
if (mask & (1 << next - 1))
{
continue;
}
if (last == 0 || binary[last] == binary[next] || ternary[last] == ternary[next])
{
dp[mask][last] += f(mask | (1 << next - 1), next);
}
}
return dp[mask][last];
}
void solve()
{
for (int i = 1 ; i <= n ; ++i)
{
binary[i] = __builtin_popcount(a[i]);
int curr = a[i];
while (curr > 0)
{
ternary[i] += (curr % 3) == 1;
curr /= 3;
}
}
std::cout << f(0, 0) << '\n';
}
void input()
{
std::cin >> n;
for (int i = 1 ; i <= n ; ++i)
{
std::cin >> a[i];
}
}
void fastIOI()
{
std::ios_base :: sync_with_stdio(0);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
}
int main()
{
fastIOI();
input();
solve();
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |