Submission #969717

#	Time	Username	Problem	Language	Result	Execution time	Memory
969717		VMaksimoski008	Beautiful row (IZhO12_beauty)	C++17	0 / 100	10 ms	27084 KiB

beauty

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

int cnt(int x) { return __builtin_popcount(x); }

int dp[20][1<<20], n, ans;

int main() {
    cin >> n;

    int v[n];
    for(int i=0; i<n; i++) cin >> v[i];

    vector<int> graph[n];
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            if(i != j && (cnt(v[i]) == cnt(v[j]) || check(v[i]) == check(v[j])))
                graph[i].push_back(j);

    for(int i=0; i<n; i++) dp[i][1<<i] = 1;

    for(int s=1; s<(1<<n); s++) {
        for(int i=0; i<n; i++) {
            if((s & (1 << i)) == 0) continue;
            for(int &j : graph[i])
                if(s & (1 << j)) dp[i][s] += dp[j][s^(1<<i)];
        }
    }

    for(int i=0; i<n; i++) ans += dp[i][(1<<n)-1];
    cout << ans << '\n';
    return 0;
}

• Subtask 1: 0 / 100