Submission #83713

#	Time	Username	Problem	Language	Result	Execution time	Memory
83713		mra2322001	Beautiful row (IZhO12_beauty)	C++14	0 / 100	3049 ms	165116 KiB

beauty

#include <bits/stdc++.h>
#define f0(i, n) for(int i(0); i < (n); i++)
#define f1(i, n) for(int i(1); i <= n; i++)
#define bit(x, y) (((x) >> (y)) & (1ll))

using namespace std;
typedef long long ll;
const int N = 21;

int n, a[N], b2[N], b3[N];
ll f[20][1ll << 20];

ll calc(int i, int s){
    if(f[i][s] != -1) return f[i][s];
    if(s==(1ll << (n)) - 1){
        f[i][s] = 1;
        return 1;
    }
    ll ans = 0;
    for(int j = 0; j < n; j++){
        if(bit(s, j)) continue;
        if(b2[i + 1] != b2[j + 1] && b3[i + 1] != b3[j + 1]) continue;
        ans = ans + calc(j, s + (1ll << j));
    }
    f[i][s] = ans;
    return ans;
}

int main(){
    ios_base::sync_with_stdio(0);

    cin >> n;
    f1(i, n){
        cin >> a[i];
        b2[i] = __builtin_popcount(a[i]);
        while(a[i]){
            int x = a[i]%3;
            b3[i] += (x==1);
            a[i] /= 3;
        }
    }
    memset(f, -1, sizeof(f));
    ll ans = 0;
    f1(i, n) ans = ans + calc(i - 1, (1ll << (i - 1)));

    cout << ans;
}

• Subtask 1: 0 / 100