Submission #89818

#	Time	Username	Problem	Language	Result	Execution time	Memory
89818		Vardanyan	Beautiful row (IZhO12_beauty)	C++14	100 / 100	1214 ms	181304 KiB

beauty

#include <bits/stdc++.h>
using namespace std;
const int N = 22;
int a[N];
bool d[N][N];
bool check(int x,int y){
    int xx,yy;
    xx = yy = 0;
    for(int i = 0;i<32;i++){
        if((x>>i)&1) xx++;
        if((y>>i)&1) yy++;
    }
    if(xx == yy) return true;
    xx = yy = 0;
    while(x!=0){
        if(x%3 == 1) xx++;
        x/=3;
    }
    while(y!=0){
        if(y%3 == 1) yy++;
        y/=3;
    }
    return xx == yy;
}
long long dp[(1<<N)][N];
int main(){
    int n;
    cin>>n;
    for(int i = 0;i<n;i++) cin>>a[i];
    for(int i = 0;i<n;i++){
        for(int j = i+1;j<n;j++){
            if(check(a[i],a[j])){
                d[i][j] = d[j][i] = 1;
            }
        }
        dp[(1<<i)][i] = 1;
    }
    for(int mask = 1;mask<(1<<n);mask++){
        for(int lst = 0;lst<n;lst++){
            if(!((mask>>lst)&1)) continue;
            for(int i = 0;i<n;i++){
                if((mask>>i)&1) continue;
                if(d[lst][i]){
                    dp[mask|(1<<i)][i]+=dp[mask][lst];
                }
            }
        }
    }
    long long ans = 0;
    for(int lst = 0;lst<n;lst++) ans+=dp[(1<<n)-1][lst];
    cout<<ans<<endl;
    return 0;
}

• Subtask 1: 100 / 100