oj.uz

Submission #876956

# Submission time Handle Problem Language Result Execution time Memory
876956 2023-11-22T14:59:50 Z boris_mihov Beautiful row (IZhO12_beauty) C++17
0 / 100
 1 ms 456 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 20 + 10;
const int MAXB = (1 << 20) + 10;

int n;
int a[MAXN];
int binary[MAXN];
int ternary[MAXN];
llong dp[MAXN][MAXN];
bool bl[MAXN][MAXN];

llong f(int mask, int last)
{
    if (__builtin_popcount(mask) == n)
    {
        return 1;
    }

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

    bl[mask][last] = true;
    for (int next = 1 ; next <= n ; ++next)
    {
        if (mask & (1 << next - 1))
        {
            continue;
        }

        if (last == 0 || binary[last] == binary[next] || ternary[last] == ternary[next])
        {
            dp[mask][last] += f(mask | (1 << next - 1), next);
        }
    }

    return dp[mask][last];
}

void solve()
{
    for (int i = 1 ; i <= n ; ++i)
    {
        binary[i] = __builtin_popcount(a[i]);
        int curr = a[i];

        while (curr > 0)
        {
            ternary[i] += (curr % 3) == 1;
            curr /= 3;
        }
    }

    std::cout << f(0, 0) << '\n';
}

void input()
{
    std::cin >> n;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> a[i];
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

Compilation message

beauty.cpp: In function 'llong f(int, int)':
beauty.cpp:33:31: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   33 |         if (mask & (1 << next - 1))
      |                          ~~~~~^~~
beauty.cpp:40:51: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   40 |             dp[mask][last] += f(mask | (1 << next - 1), next);
      |                                              ~~~~~^~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 456 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Runtime error 1 ms 456 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -