Submission #881117

#	Time	Username	Problem	Language	Result	Execution time	Memory
881117		alexdd	Beautiful row (IZhO12_beauty)	C++17	100 / 100	875 ms	164692 KiB

beauty

#include<iostream>
#include<algorithm>
using namespace std;
int n;
int cnt2[25];
int cnt3[25];
long long dp[1100000][20];
int calc_cnt2(int x)
{
    int rez=0;
    for(int i=0;i<30;i++)
    {
        if(((1<<i)&x))
            rez++;
    }
    return rez;
}
int calc_cnt3(int x)
{
    int rez=0;
    while(x>0)
    {
        if(x%3==1)
            rez++;
        x/=3;
    }
    return rez;
}
signed main()
{
    cin>>n;
    int a;
    for(int i=0;i<n;i++)
    {
        cin>>a;
        cnt2[i] = calc_cnt2(a);
        cnt3[i] = calc_cnt3(a);
    }
    for(int config=1;config<(1<<n);config++)
    {
        for(int cur=0;cur<n;cur++)
        {
            if(((1<<cur)&config)==0)
                continue;
            int cate=0;
            for(int ult=0;ult<n;ult++)
            {
                if(ult!=cur && ((1<<ult)&config))
                {
                    cate++;
                    if(cnt2[ult]==cnt2[cur] || cnt3[ult]==cnt3[cur])
                    {
                        dp[config][cur] += dp[config-(1<<cur)][ult];
                    }
                }
            }
            if(cate==0)
                dp[config][cur] = 1;
        }
    }
    long long sum=0;
    for(int ult=0;ult<n;ult++)
        sum += dp[(1<<n)-1][ult];
    cout<<sum;
    return 0;
}

• Subtask 1: 100 / 100