Submission #339457

#	Time	Username	Problem	Language	Result	Execution time	Memory
339457		Vladikus004	Beautiful row (IZhO12_beauty)	C++14	100 / 100	2778 ms	164588 KiB

beauty

#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
//#pragma target("tune=native")
#pragma GCC target("avx2")
#define mp make_pair
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define inf 2e9
#define ff first
#define ss second
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;

const int N = 20;
vector <short int> v[N];
short int n;
int a[N];
short int c1[N], c2[N];

void get_cnt(int x, int ind){
    int _c1 = 0, _c2 = 0;
    int X = x;
    while (x){
        if (x % 2 == 1) _c1++;
        x>>=1;
    }
    x = X;
    while (x){
        if (x % 3 == 1) _c2++;
        x /= 3;
    }
    c1[ind] = _c1;
    c2[ind] = _c2;
    return;
}

ll dp[(1<<20)][20];

ll get_dp(int mask, short int lst){
    if (mask == ((1<<n)-1)) return 1;
    if (dp[mask][lst] != -1)
        return dp[mask][lst];
    ll ans = 0;
    for (auto u: v[lst]){
        if (mask & (1<<u)) continue;
        ans += get_dp(mask | (1<<u), u);
    }
    return dp[mask][lst] = ans;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//    freopen("input.txt", "r", stdin);
  
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++)
        get_cnt(a[i], i);
    for (int i = 0; i < n; i++){
        for (int j = i+1; j < n; j++){
            if (c1[i]==c1[j]||c2[i]==c2[j]){
                v[i].pb(j);
                v[j].pb(i);
            }
        }
    }
    ll ans = 0;
    memset(dp, -1, sizeof dp);
    for (int i = 0; i < n; i++){
        ans += get_dp((1<<i), i);
    }
    cout << ans;
    return 0;
}

• Subtask 1: 100 / 100