oj.uz

Submission #896538

# Submission time Handle Problem Language Result Execution time Memory
896538 2024-01-01T16:00:46 Z borisAngelov Beautiful row (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

# Verdict Execution time Memory 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