oj.uz

답안 #902535

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
902535 2024-01-10T15:20:09 Z tvladm2009 아름다운 순열 (IZhO12_beauty) C++17
100 / 100
 1051 ms 205652 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    vector<vector<ll>> dp(1 << 20, vector<ll>(n, 0));
    for (int i = 0; i < n; ++i) cin >> a[i];
    vector<int> bin(n), ter(n);
    for (int i = 0; i < n; ++i) {
        bin[i] = __builtin_popcount(a[i]);
        int n = a[i];
        while (n > 0) {
            if (n % 3 == 1) ++ter[i];
            n /= 3;
        }
    }
    for (int i = 0; i < n; ++i) dp[1 << i][i] = 1;
    for (int mask = 0; mask < (1 << n); ++mask) {
        if (__builtin_popcount(mask) == 1) continue;
        for (int b = 0; b < n; ++b) {
            if (mask & (1 << b)) {
                for (int b2 = 0; b2 < n; b2++) {
                    if (!(mask & (1 << b2))) continue;
                    if (b2 != b && (bin[b] == bin[b2] || ter[b] == ter[b2])) dp[mask][b] += dp[mask - (1 << b)][b2];
                }
            }
        }
    }
    ll ans = 0;
    for (int b = 0; b < n; ++b) {
        ans += dp[(1 << n) - 1][b];
    }
    cout << ans << endl;
    return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 57868 KB Output is correct
2 Correct 52 ms 57880 KB Output is correct
3 Correct 47 ms 74116 KB Output is correct
4 Correct 49 ms 74084 KB Output is correct
5 Correct 49 ms 74164 KB Output is correct
6 Correct 68 ms 123348 KB Output is correct
7 Correct 73 ms 123364 KB Output is correct
8 Correct 70 ms 123388 KB Output is correct
9 Correct 70 ms 123560 KB Output is correct
10 Correct 69 ms 123476 KB Output is correct
11 Correct 98 ms 156240 KB Output is correct
12 Correct 94 ms 156256 KB Output is correct
13 Correct 131 ms 172800 KB Output is correct
14 Correct 307 ms 189012 KB Output is correct
15 Correct 277 ms 189228 KB Output is correct
16 Correct 289 ms 189232 KB Output is correct
17 Correct 321 ms 189008 KB Output is correct
18 Correct 293 ms 189012 KB Output is correct
19 Correct 1051 ms 205652 KB Output is correct
20 Correct 961 ms 205652 KB Output is correct