oj.uz

답안 #969717

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
969717 2024-04-25T13:36:20 Z VMaksimoski008 아름다운 순열 (IZhO12_beauty) C++17
0 / 100
 10 ms 27084 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int check(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;

int main() {
    cin >> n;

    int v[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]) || check(v[i]) == check(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
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 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 6588 KB Output is correct
5 Correct 1 ms 6488 KB Output is correct
6 Correct 2 ms 19140 KB Output is correct
7 Correct 2 ms 18780 KB Output is correct
8 Correct 3 ms 18780 KB Output is correct
9 Correct 3 ms 18780 KB Output is correct
10 Correct 2 ms 18780 KB Output is correct
11 Incorrect 10 ms 27084 KB Output isn't correct
12 Halted 0 ms 0 KB -