Submission #1176730

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176730		raphaelp	아름다운 순열 (IZhO12_beauty)	C++20	100 / 100	866 ms	172872 KiB

beauty

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long N;
    cin >> N;
    vector<long long> Tab(N);
    for (long long i = 0; i < N; i++)
    {
        cin >> Tab[i];
    }
    vector<long long> Bin(N), Ter(N);
    for (long long i = 0; i < N; i++)
    {
        long long x = Tab[i];
        while (x)
        {
            Bin[i] += x % 2;
            x /= 2;
        }
        x = Tab[i];
        while (x)
        {
            if (x % 3 == 1)
                Ter[i]++;
            x /= 3;
        }
    }
    vector<vector<long long>> dp(N, vector<long long>(1 << N));
    for (long long i = 0; i < N; i++)
        dp[i][(1 << i)] = 1;
    for (long long i = 0; i < (1 << N); i++)
    {
        for (long long j = 0; j < N; j++)
        {
            if (dp[j][i] == 0)
                continue;
            for (long long k = 0; k < N; k++)
            {
                if (i & (1 << k))
                    continue;
                if (Bin[j] == Bin[k] || Ter[j] == Ter[k])
                    dp[k][i | (1 << k)] += dp[j][i];
            }
        }
    }
    long long tot = 0;
    for (long long i = 0; i < N; i++)
    {
        tot += dp[i][(1 << N) - 1];
    }
    cout << tot;
}

• Subtask 1: 100 / 100