Submission #857595

#	Time	Username	Problem	Language	Result	Execution time	Memory
857595		Mohamed_Kachef06	Beautiful row (IZhO12_beauty)	C++17	100 / 100	1584 ms	164692 KiB

beauty

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define A first
#define B second

int n ,  a[20] , dp[20][1<<20] , co[20][20]; 

int fact(int i , int b){
    int x = a[i];
    int ans =0 ;
    while(x > 0){
        if (x%b == 1) ans++;
        x/=b;
    }
    return ans;
}

void pre(){
    for (int i = 0 ; i < n ; i++) {
        for (int j = 0 ; j < i ; j++){
            int a = fact(i ,2), b = fact(i , 3) , c = fact(j ,2 ) , d= fact(j , 3);
            if (a == c || b == d)  { co[i][j] = 1; co[j][i] = 1;}
        }
    }
}

// int brute(int last , int mask , set<int> &st){
//     if ( mask == (1<<n) - 1) return 1;
//     if (~dp[last][mask]) return dp[last][mask];
//     int ans = 0 ;
//     for (auto i = st.begin() ; i!=st.end() ; i++){
//         if (!(mask & (1<<*i))){ 
//           if (mask == 0 || co[last][*i]) {
//             set<int> b = st;
//             b.erase(*i);
//             ans += brute(*i , (mask | 1<<*i) , b);
//           }
//         }
//     }
//     return dp[last][mask] =  ans;
// }

void brute(){
    
    for (int mask = (1<<n) - 1 ; mask >= 0 ; mask--){
        for (int last = n-1 ; last >= 0 ; last--){
            if (mask == (1<<n) - 1) { dp[last][mask] = 1; continue; } 
            for (int i = 0 ; i < n ; i++) {
                if (!(mask & (1<<i))){
                    if (mask == 0 || co[last][i]){
                        dp[last][mask] += dp[i][mask | (1<<i)];
                    } 
                }
            }
        }
    }
    cout << dp[0][0];
}

signed main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 0 ; i < n ; i++) cin >> a[i];
    pre();
    brute();
}

• Subtask 1: 100 / 100