oj.uz

답안 #969761

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
969761 2024-04-25T14:39:45 Z VMaksimoski008 아름다운 순열 (IZhO12_beauty) C++17
100 / 100
 822 ms 158544 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

int C(int x) {
    int cnt = 0;
    while(x) {
        if(x % 3 == 1) cnt++;
        x /= 3;
    }
    return cnt;
}

int cnt(int x) { return __builtin_popcount(x); }

int dp[20][1<<20], n, ans, v[20];

int32_t main() {
    cin >> n;
    for(int i=0; i<n; i++) cin >> v[i];

    vector<int> graph[n];
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            if(i != j && (cnt(v[i]) == cnt(v[j]) || C(v[i]) == C(v[j])))
                graph[i].push_back(j);

    for(int i=0; i<n; i++) dp[i][1<<i] = 1;

    for(int s=1; s<(1<<n); s++) {
        for(int i=0; i<n; i++) {
            if((s & (1 << i)) == 0) continue;
            for(int &j : graph[i])
                if(s & (1 << j)) dp[i][s] += dp[j][s^(1<<i)];
        }
    }

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

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 6492 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 3 ms 18780 KB Output is correct
9 Correct 2 ms 18780 KB Output is correct
10 Correct 2 ms 18780 KB Output is correct
11 Correct 11 ms 27192 KB Output is correct
12 Correct 9 ms 27228 KB Output is correct
13 Correct 49 ms 62136 KB Output is correct
14 Correct 150 ms 66284 KB Output is correct
15 Correct 167 ms 66268 KB Output is correct
16 Correct 132 ms 64936 KB Output is correct
17 Correct 143 ms 66268 KB Output is correct
18 Correct 110 ms 65108 KB Output is correct
19 Correct 756 ms 158152 KB Output is correct
20 Correct 822 ms 158544 KB Output is correct