Submission #83716

#	Time	Username	Problem	Language	Result	Execution time	Memory
83716		mra2322001	Beautiful row (IZhO12_beauty)	C++14	0 / 100	3052 ms	263168 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++)

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

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

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;
    }
    ///int cur = (1ll << n) - 1 - s;
    ll ans = 0;
    ///for(; state > 0; state ^= state & -state){
    for(auto j:v[s]){
        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;
        }
    }
    v.resize((1ll << n));
    f0(i, (1ll << n)){
        f0(j, n){
            if((i >> j)&1) continue;
            v[i].emplace_back(j);
        }
    }
    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