제출 #90169

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
90169		popovicirobert	아름다운 순열 (IZhO12_beauty)	C++14	100 / 100	725 ms	164892 KiB

beauty

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44

using namespace std;

const int MAXN = 20;

ll dp[1 << MAXN][MAXN];
int cnt2[MAXN], cnt3[MAXN];

inline int get2(int x) {
    return __builtin_popcount(x);
}

inline int get3(int x) {
    int cnt = 0;
    while(x > 0) {
        cnt += ((x % 3) == 1);
        x /= 3;
    }
    return cnt;
}

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for(i = 0; i < n; i++) {
        int x;
        cin >> x;
        cnt2[i] = get2(x);
        cnt3[i] = get3(x);
    }
    for(int conf = 1; conf < (1 << n); conf++) {
        if((conf & (conf - 1)) == 0) {
            int bit = 0;
            while((conf & (1 << bit)) == 0) {
                bit++;
            }
            dp[conf][bit] = 1;
        }
        else {
            vector <int> cur;
            for(int bit = 0; bit < n; bit++) {
                if(conf & (1 << bit)) {
                    cur.push_back(bit);
                }
            }
            int sz = cur.size();
            for(int a = 0; a < sz; a++) {
                for(int b = 0; b < sz; b++) {
                    if(a != b && (cnt2[cur[a]] == cnt2[cur[b]] || cnt3[cur[a]] == cnt3[cur[b]])) {
                        dp[conf][cur[a]] += dp[conf ^ (1 << cur[a])][cur[b]];
                    }
                }
            }
        }
    }
    ll ans = 0;
    for(i = 0; i < n; i++) {
        ans += dp[(1 << n) - 1][i];
    }
    cout << ans;
    //cin.close();
    //cout.close();
    return 0;
}

• Subtask 1: 100 / 100