oj.uz

답안 #896538

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
896538 2024-01-01T16:00:46 Z borisAngelov 아름다운 순열 (IZhO12_beauty) C++17
100 / 100
 1860 ms 231356 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 20;
const int maxMask = (1 << maxn);

int n;

int a[maxn + 5];

bool areNeighbours[maxn + 5][maxn + 5];

long long dp[maxMask + 5][maxn + 5];
bool bl[maxMask + 5][maxn + 5];

int cnt2(int x)
{
    int res = 0;

    while (x != 0)
    {
        if (x % 2 == 1)
        {
            ++res;
        }

        x /= 2;
    }

    return res;
}

int cnt3(int x)
{
    int res = 0;

    while (x != 0)
    {
        if (x % 3 == 1)
        {
            ++res;
        }

        x /= 3;
    }

    return res;
}

bool check(int x, int y)
{
    int x2 = cnt2(x);
    int x3 = cnt3(x);
    int y2 = cnt2(y);
    int y3 = cnt3(y);

    return x2 == y2 || x3 == y3;
}

long long f(int mask, int last)
{
    if (mask == (1 << n) - 1)
    {
        return 1;
    }

    if (bl[mask][last] == true)
    {
        return dp[mask][last];
    }

    bl[mask][last] = true;

    long long result = 0;

    for (int i = 0; i < n; ++i)
    {
        if ((mask & (1 << i)) == 0 && areNeighbours[i][last] == true)
        {
            result += f((mask | (1 << i)), i);
        }
    }

    return dp[mask][last] = result;
}

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n;

    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
    }

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (i != j && check(a[i], a[j]) == true)
            {
                areNeighbours[i][j] = true;
            }
        }
    }

    long long ans = 0;

    for (int i = 0; i < n; ++i)
    {
        ans += f((1 << i), i);
    }

    cout << ans << endl;

    return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2540 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 9 ms 4976 KB Output is correct
12 Correct 7 ms 4952 KB Output is correct
13 Correct 50 ms 16468 KB Output is correct
14 Correct 307 ms 60212 KB Output is correct
15 Correct 301 ms 60212 KB Output is correct
16 Correct 211 ms 60216 KB Output is correct
17 Correct 279 ms 59996 KB Output is correct
18 Correct 178 ms 60084 KB Output is correct
19 Correct 1755 ms 231268 KB Output is correct
20 Correct 1860 ms 231356 KB Output is correct