제출 #1223891

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1223891		Hanksburger	아름다운 순열 (IZhO12_beauty)	C++20	100 / 100	782 ms	164392 KiB

beauty

#include <bits/stdc++.h>
#define int long long
using namespace std;
int dp[1048576][20], a[20];
vector<int> adj[20];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, ans=0;
    cin >> n;
    for (int i=0; i<n; i++)
        cin >> a[i];
    for (int i=0; i<n; i++)
    {
        for (int j=i+1; j<n; j++)
        {
            int cnt2=0, cnt3=0, power=1;
            for (int k=0; k<30; k++)
            {
                if (a[i]&(1<<k))
                    cnt2++;
                if (a[j]&(1<<k))
                    cnt2--;
            }
            for (int k=0; k<19; k++)
            {
                if (a[i]%(power*3)/power==1)
                    cnt3++;
                if (a[j]%(power*3)/power==1)
                    cnt3--;
                power*=3;
            }
            if (!cnt2 || !cnt3)
            {
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
        }
    }
    for (int i=1; i<(1<<n); i++)
    {
        vector<int> vec;
        for (int j=0; j<n; j++)
            if (i&(1<<j))
                vec.push_back(j);
        if (vec.size()==1)
        {
            dp[i][vec[0]]=1;
            continue;
        }
        for (int u:vec)
            for (int v:adj[u])
                if (i&(1<<v))
                    dp[i][u]+=dp[i^(1<<u)][v];
    }
    for (int i=0; i<n; i++)
        ans+=dp[(1<<n)-1][i];
    cout << ans;
}

• Subtask 1: 100 / 100