Submission #968800

#	Time	Username	Problem	Language	Result	Execution time	Memory
968800		12345678	Beautiful row (IZhO12_beauty)	C++17	100 / 100	838 ms	133580 KiB

beauty

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=21, kx=(1<<20)+5;

ll n, a[nx], dp[nx][kx], x[nx], y[nx], res;
vector<int> d[nx];

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=0; i<n; i++)
    {
        cin>>a[i];
        int tmp=a[i];
        while (tmp>0) x[i]+=((tmp%2)==1), tmp/=2;
        tmp=a[i];
        while (tmp>0) y[i]+=((tmp%3)==1), tmp/=3;
    }
    for (int i=0; i<n; i++) for (int j=i+1; j<n; j++) if (x[i]==x[j]||y[i]==y[j]) d[i].push_back(j), d[j].push_back(i); //cout<<"edge "<<i<<' '<<j<<'\n';
    for (int i=1; i<(1<<n); i++)
    {
        for (int u=0; u<n; u++)
        {
            if (!(i&(1<<u))) continue;
            if (__builtin_popcount(i)==1)
            {
                dp[u][i]=1;
                continue;
            }
            for (auto v:d[u])
            {
                if (i&(1<<v))
                {
                    dp[u][i]+=dp[v][i^(1<<u)];
                }
            }
            //cout<<"debug "<<i<<' '<<u<<' '<<dp[u][i]<<'\n';
        }
    }
    for (int i=0; i<n; i++) res+=dp[i][(1<<n)-1];
    cout<<res;
}

• Subtask 1: 100 / 100