Submission #876959

#	Time	Username	Problem	Language	Result	Execution time	Memory
876959		boris_mihov	Beautiful row (IZhO12_beauty)	C++17	100 / 100	2258 ms	194348 KiB

beauty

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 21;
const int MAXB = (1 << 20);

int n;
int a[MAXN];
int binary[MAXN];
int ternary[MAXN];
llong dp[MAXB][MAXN];
bool bl[MAXB][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)

beauty.cpp: In function 'llong f(int, int)':
beauty.cpp:33:31: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   33 |         if (mask & (1 << next - 1))
      |                          ~~~~~^~~
beauty.cpp:40:51: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   40 |             dp[mask][last] += f(mask | (1 << next - 1), next);
      |                                              ~~~~~^~~

• Subtask 1: 100 / 100