Submission #1307008

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307008		ballbreaker	Beautiful row (IZhO12_beauty)	C++20	100 / 100	866 ms	164560 KiB

beauty

#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
    int n;
    cin >> n;
    int a[n];
    int dp[(1 << n)][n] = {};
    bool was[n][n] = {};
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        dp[(1 << i)][i] = 1;
    }
    sort(a, a + n);
    int cnt2[n] = {};
    int cnt3[n] = {};
    for (int i = 0; i < n; i++) {
        int pr = 1;
        int u = a[i];
        while (u >= pr) {
            if ((u / pr) % 3 == 1) {
                cnt3[i]++;
            }
            pr *= 3;
        }
        for (int j = 0; j < 31; j++) {
            if ((a[i] >> j) & 1) {
                cnt2[i]++;
            }
        }
        // cout << cnt2[i] << ' '  << cnt3[i] << endl;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            was[i][j] = (cnt3[i] == cnt3[j] || cnt2[i] == cnt2[j]);
            if (was[i][j]) {
                // cout << i << ' ' << j << endl;
            }
        }
    }
    for (int i = 0; i < (1 << n); i++) {
        if (__builtin_popcountll(i) < 2) {
            continue;
        }
        for (int j = 0; j < n; j++) {
            if ((i >> j) & 1) {
                for (int k = 0; k < n; k++) {
                    if (k != j && (i >> k) & 1 && was[k][j]) {
                        dp[i][j] += dp[i - (1 << j)][k];
                    }
                }
                // cout << i << ' ' << j << ' ' << dp[i][j] << endl;
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans += dp[(1 << n) - 1][i];
    }
    cout << ans;

}

Compilation message (stderr)

beauty.cpp:4:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    4 | main() {
      | ^~~~

• Subtask 1: 100 / 100