oj.uz

Submission #876957

# Submission time Handle Problem Language Result Execution time Memory
876957 2023-11-22T15:00:14 Z boris_mihov Beautiful row (IZhO12_beauty) C++17
0 / 100
 430 ms 262144 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[MAXB][MAXN];
bool bl[MAXB][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 2396 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 2396 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 4560 KB Output is correct
11 Correct 11 ms 7108 KB Output is correct
12 Correct 9 ms 6492 KB Output is correct
13 Correct 57 ms 19632 KB Output is correct
14 Correct 430 ms 71568 KB Output is correct
15 Correct 381 ms 71748 KB Output is correct
16 Correct 278 ms 71640 KB Output is correct
17 Correct 351 ms 71768 KB Output is correct
18 Correct 215 ms 71508 KB Output is correct
19 Runtime error 64 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -