oj.uz

Submission #639700

# Submission time Handle Problem Language Result Execution time Memory
639700 2022-09-11T07:04:25 Z classic Beautiful row (IZhO12_beauty) C++14
100 / 100
 838 ms 172744 KB 
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> cnt2(n), cnt3(n);
    function<int(int)> calc = [](int x) {
        int ret = 0;
        while (x) {
            ret += (x % 3 == 1);
            x /= 3;
        }
        return ret;
    };
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        cnt2[i] = __builtin_popcount(a);
        cnt3[i] = calc(a);
    }
    vector<vector<long long>> dp(n, vector<long long>(1 << n));
    for (int i = 0; i < n; i++) {
        dp[i][1 << i] = 1;
    }
    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 (cnt2[i] == cnt2[j] || cnt3[i] == cnt3[j]) {
                    dp[i][mask] += dp[j][mask ^ (1 << i)];
                }
            }
        }
    }
    long long res = 0;
    for (int i = 0; i < n; i++) {
        res += dp[i][(1 << n) - 1];
    }
    cout << res;
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 220 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 316 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 320 KB Output is correct
10 Correct 1 ms 320 KB Output is correct
11 Correct 7 ms 2260 KB Output is correct
12 Correct 8 ms 2260 KB Output is correct
13 Correct 36 ms 9024 KB Output is correct
14 Correct 164 ms 39288 KB Output is correct
15 Correct 184 ms 39292 KB Output is correct
16 Correct 181 ms 39352 KB Output is correct
17 Correct 185 ms 39356 KB Output is correct
18 Correct 170 ms 39380 KB Output is correct
19 Correct 838 ms 172744 KB Output is correct
20 Correct 835 ms 172700 KB Output is correct