Submission #1077759

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077759		coolboy19521	Beautiful row (IZhO12_beauty)	C++17	100 / 100	1087 ms	180992 KiB

beauty

#include "bits/stdc++.h"
#define ll long long

using namespace std;

const int sz = 22;

ll dp[1 << sz][sz];
int tr[sz], tw[sz];
bool ok[sz][sz];
int a[sz];

int cO(int a, int b) {
    int r = 0;
    for (int c = a; c; c /= b)
        r += 1 == c % b;
    return r;
}

int main() {
    int n;
    cin >> n;

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

    for (int i = 0; i < n; i ++) {
        tw[i] = cO(a[i], 2);
        tr[i] = cO(a[i], 3);
    }

    for (int i = 0; i < n; i ++)
        for (int j = 0; j < n; j ++)
            ok[i][j] = tr[i] == tr[j] || tw[i] == tw[j];

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

    for (int i = 0; i < (1 << n); i ++) {
        for (int j = 0; j < n; j ++) {
            for (int k = 0; k < n; k ++) {
                if (j != k) if (i & (1 << j)) if (!(i & (1 << k))) if (ok[j][k])
                    dp[i | (1 << k)][k] += dp[i][j];
            }
        }
    }

    ll r = 0;

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

    cout << r << '\n';
}

• Subtask 1: 100 / 100