Submission #83717

#	Time	Username	Problem	Language	Result	Execution time	Memory
83717		mra2322001	Beautiful row (IZhO12_beauty)	C++14	100 / 100	2660 ms	164948 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 log lr

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

int n, a[N], b2[N], b3[N];
int log[1ll << 20];
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;
    }
    int cur = (1ll << n) - 1 - s;

    ll ans = 0;
    ///for(; state > 0; state ^= state & -state){
    for(cur; cur > 0; cur ^= cur & -cur){
        int j = log[cur & -cur];
        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);

    f0(i, 20){
        log[1ll << i] = i;
    }
    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;
}

Compilation message (stderr)

beauty.cpp: In function 'll calc(int, int)':
beauty.cpp:24:12: warning: statement has no effect [-Wunused-value]
     for(cur; cur > 0; cur ^= cur & -cur){
            ^

• Subtask 1: 100 / 100