제출 #867654

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
867654		sleepntsheep	아름다운 순열 (IZhO12_beauty)	C++17	100 / 100	317 ms	164436 KiB

beauty

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>

using namespace std;
#define ALL(x) x.begin(), x.end()
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
using ll = long long;
#define N 20
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,sse3,sse4,popcnt,fma")

int n, a[N], b3[N], d[N][N];
ll ans, dp[1<<N][N];

inline int beautiful(int i, int j) { return (__builtin_popcount(a[i]) == __builtin_popcount(a[j])) || b3[i] == b3[j]; }

int main()
{
    ShinLena;
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
        for (int x = a[i]; x; b3[i] += (x % 3) == 1, x /= 3);
        dp[0][i] = 1;
    }
    for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) d[i][j] = beautiful(i, j);
    for (int k = 0; k < (1 << n); ++k)
    {
        for (int j = 0; j < n; ++j)
        {
            if (!(k&(1<<j))) continue;
            for (int l = 0; l < n; ++l)
                dp[k][j] += ((k >> l) & 1) * d[j][l] * dp[k&~(1<<j)][l];
        }
    }

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

    return 0;
}

• Subtask 1: 100 / 100