oj.uz

Submission #857595

# Submission time Handle Problem Language Result Execution time Memory
857595 2023-10-06T12:38:38 Z Mohamed_Kachef06 Beautiful row (IZhO12_beauty) C++17
100 / 100
 1584 ms 164692 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 3 ms 18780 KB Output is correct
7 Correct 3 ms 18780 KB Output is correct
8 Correct 4 ms 18780 KB Output is correct
9 Correct 2 ms 18780 KB Output is correct
10 Correct 3 ms 18780 KB Output is correct
11 Correct 15 ms 27260 KB Output is correct
12 Correct 15 ms 27224 KB Output is correct
13 Correct 61 ms 64008 KB Output is correct
14 Correct 300 ms 72192 KB Output is correct
15 Correct 274 ms 72192 KB Output is correct
16 Correct 296 ms 72272 KB Output is correct
17 Correct 298 ms 72276 KB Output is correct
18 Correct 299 ms 72192 KB Output is correct
19 Correct 1584 ms 164692 KB Output is correct
20 Correct 1459 ms 164560 KB Output is correct