oj.uz

Submission #329023

# Submission time Handle Problem Language Result Execution time Memory
329023 2020-11-18T18:03:45 Z gustason Beautiful row (IZhO12_beauty) C++14
100 / 100
 863 ms 164548 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll dp[(1<<20)][20];
bool check(int a, int b) {
    int bina = __builtin_popcount(a);
    int binb = __builtin_popcount(b);
    if (bina == binb) return true;

    int tera = 0, terb = 0;
    while(a > 0) {
        if (a % 3 == 1) tera++;
        a /= 3;
    }
    while(b > 0) {
        if (b % 3 == 1) terb++;
        b /= 3;
    }
    return tera == terb;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    int a[n];
    bool mat[n][n];
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        dp[0][i] = 1;
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            //if (i == j) continue;
            mat[i][j] = check(a[i], a[j]);
        }
    }

    for(int mask = 0; mask < (1 << n); mask++) {
        for(int i = 0; i < n; i++) {
            if (!(mask&(1<<i))) continue;
            for(int j = 0; j < n; j++) {
                if (!(mask&(1<<j))) continue;
                if (!mat[i][j]) continue;
                dp[mask][i] += dp[mask^(1<<i)][j];
            }
        }
    }

    ll ans = 0LL;
    for(int i = 0; i < n; i++) {
        ans += dp[(1 << n)-1][i];
    }
    cout << ans;
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 9 ms 2924 KB Output is correct
12 Correct 8 ms 2924 KB Output is correct
13 Correct 38 ms 10732 KB Output is correct
14 Correct 208 ms 41324 KB Output is correct
15 Correct 147 ms 41324 KB Output is correct
16 Correct 183 ms 41324 KB Output is correct
17 Correct 191 ms 41324 KB Output is correct
18 Correct 187 ms 41324 KB Output is correct
19 Correct 863 ms 164532 KB Output is correct
20 Correct 697 ms 164548 KB Output is correct