oj.uz

Submission #857579

# Submission time Handle Problem Language Result Execution time Memory
857579 2023-10-06T12:30:01 Z Mohamed_Kachef06 Beautiful row (IZhO12_beauty) C++17
0 / 100
 3000 ms 164696 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;
}

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];
    memset(dp , -1 , sizeof dp);
    pre();
    set<int> st; 
    for (int i = 0 ; i < n ; i++) st.insert(i);
    cout << brute(0 , 0 , st); 
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 164432 KB Output is correct
2 Correct 18 ms 164512 KB Output is correct
3 Correct 18 ms 164440 KB Output is correct
4 Correct 19 ms 164444 KB Output is correct
5 Correct 19 ms 164444 KB Output is correct
6 Correct 20 ms 164380 KB Output is correct
7 Correct 18 ms 164604 KB Output is correct
8 Correct 24 ms 164460 KB Output is correct
9 Correct 20 ms 164608 KB Output is correct
10 Correct 22 ms 164444 KB Output is correct
11 Correct 124 ms 164444 KB Output is correct
12 Correct 99 ms 164440 KB Output is correct
13 Correct 659 ms 164600 KB Output is correct
14 Execution timed out 3017 ms 164696 KB Time limit exceeded
15 Halted 0 ms 0 KB -