oj.uz

Submission #342987

# Submission time Handle Problem Language Result Execution time Memory
342987 2021-01-03T10:31:50 Z apostoldaniel854 Beautiful row (IZhO12_beauty) C++14
100 / 100
 838 ms 164588 KB 
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"
using ll = long long;

const int MAX_N = 20;
bool good[MAX_N][MAX_N];
int a[MAX_N];

ll dp[1 << MAX_N][MAX_N];
int get (int x, int k) {
    int cnt = 0;
    while (x) {
        if (x % k == 1)
            cnt++;
        x /= k;
    }
    return cnt;
}
bool check (int x, int y) {
    return (get (x, 3) == get (y, 3)) || (get (x, 2) == get (y, 2));
}
int main () {
    ios::sync_with_stdio (false);
    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 = 0; j < n; j++)
            good[i][j] = check (a[i], a[j]);
    for (int mask = 0; mask < (1 << n); mask++) {
        if (mask == 0) {
            for (int j = 0; j < n; j++)
                dp[1 << j][j] = 1;
        }
        else {
            for (int j = 0; j < n; j++)
                if (mask & (1 << j))
                    for (int k = 0; k < n; k++)
                        if (not (mask & (1 << k)) && good[j][k])
                            dp[mask ^ (1 << k)][k] += dp[mask][j];
        }
    }
    ll ans = 0;
    for (int i = 0; i < n; i++)
        ans += dp[(1 << n) - 1][i];
    cout << ans << "\n";
    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 0 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 8 ms 2924 KB Output is correct
12 Correct 8 ms 2924 KB Output is correct
13 Correct 44 ms 10604 KB Output is correct
14 Correct 175 ms 41324 KB Output is correct
15 Correct 157 ms 41324 KB Output is correct
16 Correct 182 ms 41344 KB Output is correct
17 Correct 186 ms 41324 KB Output is correct
18 Correct 187 ms 41324 KB Output is correct
19 Correct 838 ms 164588 KB Output is correct
20 Correct 712 ms 164552 KB Output is correct