Submission #1191763

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191763		Petrix	Beautiful row (IZhO12_beauty)	C++20	0 / 100	3100 ms	171728 KiB

beauty

#include <iostream>
using namespace std;

#define int long long

int dp[2000000][21];
int v[21];

bool vf(int a,int b){
    int cnt1=0,cnt2=0;
    if(__builtin_popcount(a)==__builtin_popcount(b)) return 1;
    while(a){
        if(a%3==1) cnt1++;
        a/=3;
    }
    while(b){
        if(b%3==1) cnt2++;
        b/=3;
    }
    return (cnt1==cnt2);
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,i,j,next,bit,nr,rasp=0;
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>v[i];
        dp[1<<(i-1)][i]=1;
    }
    for(nr=1;nr<=n;nr++){
        for(j=1;j<=n;j++){
            for(bit=0;bit<(1<<n)-1;bit++){
                if(!(bit&(1<<(j-1))) || __builtin_popcount(bit)!=nr) continue;
                ////cout<<j<<" "<<bit<<" "<<dp[bit][j]<<"\n";
                for(next=1;next<=n;next++){
                    if((1<<(next-1)&bit) || !vf(v[j],v[next])) continue;
                    dp[(1<<(next-1)|bit)][next]+=dp[bit][j];
                }
            }
        }
    }
    for(i=1;i<=n;i++){
        rasp+=dp[(1<<n)-1][i];
    }
    cout<<rasp;
    return 0;
}

• Subtask 1: 0 / 100