Submission #1261116

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261116		medaa	Beautiful row (IZhO12_beauty)	C++20	100 / 100	2584 ms	172872 KiB

beauty

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'

int ones_bin(int x){
    int c = 0;
    while(x){
        c += x % 2;
        x /= 2;
    }
    return c;
}
int ones_tern(int x){
    int c = 0;
    while(x){
        c += (x % 3 == 1);
        x /= 3;
    }
    return c;
}
void SOLVE() {
    int n; cin >> n;
    vector<pair<int, int>> a(n);
    for(int i = 0, x; i < n; i++){
        cin >> x;
        a[i] = {ones_bin(x), ones_tern(x)};
    }
    vector<vector<int>> graph(n, vector<int>(n));
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            if(a[i].first == a[j].first || a[i].second == a[j].second){
                graph[i][j] = 1;
                graph[j][i] = 1;
            }
        }
    }

    vector<vector<ll>> dp(n, vector<ll>(1 << n, -1));
    function<ll(int, int)> solve =[&] (int node, int mask){
        if(mask == (1 << n) - 1) return 1LL;
        ll & ret = dp[node][mask];
        if(~ret) return ret;
        ret = 0;
        for(int j = 0; j < n; j++){
            if(graph[node][j] && ((mask >> j) & 1 ^ 1)) ret += solve(j, mask | (1 << j));
        }
        return ret;
    };

    ll answer = 0;
    for(int i = 0; i < n; i++){
        answer += solve(i, 1 << i);
    }
    cout << answer << endl;
}
signed main(){
    ios_base::sync_with_stdio(false); cout.tie(nullptr); cin.tie(nullptr);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int o_o = 1; //cin >> o_o;
    while(o_o --) SOLVE();
    return 0;
}

• Subtask 1: 100 / 100