Submission #685607

#	Time	Username	Problem	Language	Result	Execution time	Memory
685607		Ronin13	Beautiful row (IZhO12_beauty)	C++14	100 / 100	813 ms	164432 KiB

beauty

#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 / 100