oj.uz

Submission #685607

# Submission time Handle Problem Language Result Execution time Memory
685607 2023-01-24T16:28:55 Z Ronin13 Beautiful row (IZhO12_beauty) C++14
100 / 100
 813 ms 164432 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;

int count_bin(int x){
    int cnt = 0;
    while(x){
        if(x & 1) cnt++;
        x >>= 1;
    }
    return cnt;
}

int count_tern(int x){
    int cnt = 0;
    while(x){
        if(x % 3 == 1)
            cnt++;
        x /= 3;
    }
    return cnt;
}

ll dp[(1 << 20)][20];

void solve(){
    int n; cin >> n;
    bool good[n + 1][n + 1];
    int a[n + 1];
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            good[i][j] = false;
            if(count_bin(a[i]) == count_bin(a[j])) good[i][j] = true;
            if(count_tern(a[i]) == count_tern(a[j])) good[i][j] = true;

        }
    }
    for(int i = 0; i < n; i++){
        dp[(1 << i)][i] = 1;
    }
    for(int i = 1; i < (1 << n); i++){
        if(__builtin_popcount(i) == 1) continue;
        for(int j = 0; j < n; j++){
            if(!(i & (1 << j))) continue;
            for(int k = 0; k < n; k++){
                if(!(i & (1 <<k))) continue;
                if(j == k) continue;
                if(good[j + 1][k + 1])dp[i][j] += dp[i ^ (1 << j)][k];
            }
        }
    }
    ll  ans = 0;
    for(int j = 0; j < n; j++){
        ans += dp[(1 << n) - 1][j];
    }
    cout << ans;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int test =1 ; //cin >> test;
    while(test--){
        solve();
    }
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 10 ms 2772 KB Output is correct
12 Correct 8 ms 2772 KB Output is correct
13 Correct 37 ms 10520 KB Output is correct
14 Correct 187 ms 41272 KB Output is correct
15 Correct 168 ms 41272 KB Output is correct
16 Correct 175 ms 41224 KB Output is correct
17 Correct 182 ms 41252 KB Output is correct
18 Correct 180 ms 41248 KB Output is correct
19 Correct 813 ms 164404 KB Output is correct
20 Correct 711 ms 164432 KB Output is correct