oj.uz

Submission #963380

# Submission time Handle Problem Language Result Execution time Memory
963380 2024-04-14T22:32:14 Z biank Beautiful row (IZhO12_beauty) C++14
100 / 100
 1247 ms 131080 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int countOnes(int a, int b) {
    int c = 0;
    while (a > 0) {
        if (a % b == 1) c++;
        a /= b;
    }
    return c;
}

const int MAX_N = 20;

int a[MAX_N], c[MAX_N][MAX_N];
ll dp[MAX_N][1 << MAX_N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            c[i][j] = countOnes(a[i], 2) == countOnes(a[j], 2) ||
                      countOnes(a[i], 3) == countOnes(a[j], 3);
        }
    }
    for (int mask = 1; mask < 1 << n; mask++) {
        if (__builtin_popcount(mask) < 2) {
            int i = __builtin_ctz(mask);
            dp[i][mask] = 1;
            continue;
        }
        for (int x = mask; x > 0; x -= x&-x) {
            int i = __builtin_ctz(x);
            for (int y = x ^ (1 << i); y > 0; y -= y&-y) {
                int j = __builtin_ctz(y);
                if (c[i][j]) {
                    dp[i][mask] += dp[j][mask ^ (1 << i)];
                    dp[j][mask] += dp[i][mask ^ (1 << j)];
                }
            }
        }
    }
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ans += dp[i][(1 << n) - 1];
    }
    cout << ans << '\n';
    
    
    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 4444 KB Output is correct
3 Correct 1 ms 6552 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 2 ms 18780 KB Output is correct
7 Correct 3 ms 18780 KB Output is correct
8 Correct 2 ms 18780 KB Output is correct
9 Correct 3 ms 18780 KB Output is correct
10 Correct 2 ms 18776 KB Output is correct
11 Correct 8 ms 27228 KB Output is correct
12 Correct 6 ms 27228 KB Output is correct
13 Correct 29 ms 40860 KB Output is correct
14 Correct 168 ms 57172 KB Output is correct
15 Correct 204 ms 57096 KB Output is correct
16 Correct 135 ms 57240 KB Output is correct
17 Correct 161 ms 57168 KB Output is correct
18 Correct 109 ms 57148 KB Output is correct
19 Correct 948 ms 131080 KB Output is correct
20 Correct 1247 ms 131040 KB Output is correct