Submission #716440

#	Time	Username	Problem	Language	Result	Execution time	Memory
716440		vjudge1	Beautiful row (IZhO12_beauty)	C++17	0 / 100	766 ms	164420 KiB

beauty

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <bitset>
#include <cmath>
#include <queue>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
struct segment{int l, r, id;
int size(){return r-l+1;}};
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ent "\n"

const int maxn = 1e6 + 1;
const ll INF = (1ll<<61);
const int MOD = 1e9 + 7;
const int inf = (1<<30);
const int maxl = 20;
const int P = 31;

int n;
int a[maxn];
int b[maxn];
ll dp[maxn][maxl];

void test(){
    cin >> n;
    for(int i = 0; i < n; i++){
        int x; cin >> x;
        a[i] = __builtin_popcount(x);
        while(x){
            b[i] += x % 3 == 1;
            x /= 3;
        }
    }
    for(int i = 1; i < (1<<n); i++){
        if(__builtin_popcount(i) == 1){
            for(int j = 0; j < n; j++){
                if(i & (1<<j)) dp[i][j] = 1;
            }
        } else{
            for(int j = 0; j < n; j++){
                if(i & (1<<j)){
                    for(int k = 0; k < n; k++){
                        if(j == k) continue;
                        if(!(i & (1<<k))) continue;
                        if(a[j] != a[k] && b[j] != b[k]) continue;
                        dp[i][j] += dp[i ^ (1<<j)][k];
                    }
                }
            }
        }
    }
    ll ans = 0;
    for(int i = 0; i < n; i++){
        ans += dp[(1<<n) - 1][i];
    }
    cout << ans;
}

int main(){
    ios_base::sync_with_stdio(0); 
    cin.tie(0), cout.tie(0);
    int t; t = 1;
    while(t--) test();
}

• Subtask 1: 0 / 100