Submission #742405

#	Time	Username	Problem	Language	Result	Execution time	Memory
742405		anha3k25cvp	Beautiful row (IZhO12_beauty)	C++14	100 / 100	552 ms	205584 KiB

beauty

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define dl double
#define st first
#define nd second
#define II pair <int, int>

using namespace std;

const int N = 5 + 1e5;
const int inf = 7 + 1e9;

vector <int> a;
vector <vector <int>> cnt, b;
vector <vector <ll>> f;

int cal2(int x) {
    int ans = 0;
    while (x > 0) {
        if (x % 2 == 1)
            ans ++;
        x /= 2;
    }
    return ans;
}

int cal3(int x) {
    int ans = 0;
    while (x > 0) {
        if (x % 3 == 1)
            ans ++;
        x /= 3;
    }
    return ans;
}

int main() {
#define TASKNAME "beauty"
    ios_base::sync_with_stdio (0);
    cin.tie (0);
    if ( fopen( TASKNAME".inp", "r" ) ) {
        freopen (TASKNAME".inp", "r", stdin);
        freopen (TASKNAME".out", "w", stdout);
    }
    int n;
    cin >> n;
    a.assign(n, 0);
    for (int i = 0; i < n; i ++)
        cin >> a[i];
    cnt.assign(n, vector <int> (4, 0));
    for (int i = 0; i < n; i ++) {
        cnt[i][2] = cal2(a[i]);
        cnt[i][3] = cal3(a[i]);
    }
    b.assign(n, vector <int> (n, 0));
    for (int i = 0; i < n; i ++)
        for (int j = i + 1; j < n; j ++)
            if (cnt[i][2] == cnt[j][2] || cnt[i][3] == cnt[j][3]) {
                b[i][j] = 1;
                b[j][i] = 1;
            }
    f.assign(1 << n, vector <ll> (n, 0));
    for (int i = 0; i < n; i ++)
        f[1 << i][i] = 1;
    for (int mask = 1; mask < (1 << n); mask ++)
        for (int si = mask; si > 0; si ^= si & -si) {
            int i = __builtin_ctz(si & -si);
            for (int sj = ((1 << n) - 1) ^ mask; sj > 0; sj ^= sj & -sj) {
                int j = __builtin_ctz(sj & -sj);
                if (b[i][j])
                    f[mask | 1 << j][j] += f[mask][i];
            }
        }
    ll ans = 0;
    for (int i = 0; i < n; i ++)
        ans += f[(1 << n) - 1][i];
    cout << ans;
    return 0;
}

Compilation message (stderr)

beauty.cpp: In function 'int main()':
beauty.cpp:43:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         freopen (TASKNAME".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
beauty.cpp:44:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         freopen (TASKNAME".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100