oj.uz

Submission #867649

# Submission time Handle Problem Language Result Execution time Memory
867649 2023-10-29T04:23:45 Z sleepntsheep Beautiful row (IZhO12_beauty) C++17
100 / 100
 1211 ms 137964 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>

using namespace std;
#define ALL(x) x.begin(), x.end()
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
using ll = long long;
#define N 20

int n, a[N], b3[N];
ll ans, dp[N][1<<N];

inline int beautiful(int i, int j) { return (__builtin_popcount(a[i]) == __builtin_popcount(a[j])) || b3[i] == b3[j]; }

int main()
{
    ShinLena;
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
        for (int x = a[i]; x; b3[i] += (x % 3) == 1, x /= 3);
        dp[i][1<<i] = 1;
    }
    for (int k = 0; k < (1 << n); ++k)
    {
        for (int j = 0; j < n; ++j)
        {
            if (!(k&(1<<j))) continue;
            if (dp[j][k]) continue;
            for (int l = 0; l < n; ++l)
            {
                if (k & (1 << l))
                {
                    if (beautiful(j, l)) dp[j][k] += dp[l][k&~(1<<j)];
                }
            }
        }
    }

    for (int i = 0; i < n; ++i) ans += dp[i][(1<<n)-1];
    cout << ans;

    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 3 ms 18776 KB Output is correct
7 Correct 3 ms 18776 KB Output is correct
8 Correct 2 ms 18780 KB Output is correct
9 Correct 2 ms 18924 KB Output is correct
10 Correct 3 ms 18780 KB Output is correct
11 Correct 12 ms 27228 KB Output is correct
12 Correct 12 ms 27136 KB Output is correct
13 Correct 48 ms 35668 KB Output is correct
14 Correct 231 ms 59660 KB Output is correct
15 Correct 218 ms 59732 KB Output is correct
16 Correct 239 ms 59892 KB Output is correct
17 Correct 248 ms 59832 KB Output is correct
18 Correct 243 ms 59732 KB Output is correct
19 Correct 1211 ms 137672 KB Output is correct
20 Correct 1152 ms 137964 KB Output is correct